C++ lecture5

Рассмотрена реализация принципов ООП на языке С++ (кроме наследования и модульности, которые оставили напоследок). Уделяли основное внимание созданию классов, как АТД. Можно было также рассмотреть класс как расширение развития гетерогенных типов данных (таких как структуры). Структуры - гетерогенные типы данных, предназначенные для хранения разнородных, разнотипных данных. Класс, кроме хранения обеспечивает и обработку этих данных с помощью своих функций-членов.

Гомогенные типы данных (а в качестве примера - массив) также развивались с целью более эффективного решения различных задач. Это проявилось в создании и активном использовании различных гомогенных типов данных (т.е. структур данных предназначенных для хранения однотипных элементов). Часто используют термин контейнер для обозначения таких типов данных. (вектор, стек, очередь, список, ассоциативный массив, дерево). Все эти контейнеры предназначены для хранения однотипных данных, но организация этого хранения, извлечения и обработки элементов этих структур осуществлена по-разному.

Реализация всех этих структур данных (контейнеров) осуществлена в виде шаблонов классов и включена в стандарт языка С++. Их можно использовать в своих программах. Но знать, что такие структуры данных есть в вашем распоряжении, знать набор функций для работы с ними мне кажется недостаточно. Для эффективного использования контейнеров следует знать принципы их организации, а в некоторых случаях и реализации.

При организации контейнера требуется решить следующие принципиальные вопросы.

1. Каким образом осуществляется хранение элементов контейнера? Т.е. элементы должны быть расположены в памяти последовательно, непрерывным блоком, или они могут быть разбросаны по всей памяти.
2. Каким образом осуществляется доступ к элементам контейнера? По индексу или достаточно последовательного перебора.

Требования к элементам контейнеров

Что можно хранить в контейнерах? Безусловно значения всех встроенных типов данных. Если же требуется хранить в контейнере элементы АТД, то к АТД предъявляются особые требования.

Элементы в контейнере - это копии вставленных объектов.

1. Поэтому первое требование - возможность копирования АТД. Именно поэтому желательно, чтобы для АТД был реализован конструктор копирования или перегружен оператор присваивания. Это требование не будет таким строгим, если в контейнере хранить не сами объекты АТД, а указатели на них.
2. Некоторые контейнеры (ассоциативные массивы) организуют упорядоченное хранение элементов. Возможность упорядочить, отсортировать элементы должна быть у каждого контейнера. Для определения порядка используется оператор <. Таким образом, второе требование - перегруженный оператор <.

Перед тем как перейти к рассмотрению конкретных контейнеров, следует ввести понятие, общее для всех контейнеров - итератор. Итераторы являются общей концепцией обработки последовательности элементов, хранимых в любых контейнерах. Реализация итератора отличается для разных типов контейнеров, но работа с итератором, набор функций и операторов унифицирован.

Итератор - это указатель особого типа на элемент, хранящийся в контейнере. Применение оператора * приведет к разыменованию и получению доступа к значению элемента. А использование операторов ++ и - позволит получить указатель на следующий и предыдущий элемент хранимый в контейнере.

Вектор - одномерный массив проиндексированных элементов. Вектор представляет собой пример наиболее полного стандартного контейнера. Большинство операций применимых к векторам справедливо и для других контейнеров.

Для использования вектора стандартной библиотеки необходимо:

#include <vector>

using namespace std;

void main()

{

double x[100];

double* x=new double[10000];

vector<double> x(10000); // не обязательно так много, ведь при необходимости

// его размер можно изменить

x.resize(x.size()+1000); // функции члены класса vector

double sum=0;

for(int i=0; i<x.size(); i++)

{

sum+=x[i]; // доступ по индексу, хотя в данном случае индекс для

// выполнения этой операции совершенно неважен.

// Требуется выполнять обработку всех элементов массива

}

vector<double>::iterator i=x.begin();

while(i!=x.end())

{

sum+=*i;// доступ к элементам по итератору. При этом знать

// количество элементов не нужно. При работе со списком

// альтернативы нет, всегда работают с использованием итераторов.

}

sum=accumulate(x.begin(),x.end(),0.);// стандартная обобщенная функция

// (рассмотрим позже)

Для обеспечения универсальности и взаимозаменяемости контейнеры имеют несколько одинаковых методов:

• получение итераторов на первый элемент и конец контейнера begin(), end(), rbegin(), rend()
• получение информации о состоянии контейнера - количество элементов хранимых в контейнере size(), наличие элементов вообще empty()
• получение максимально возможного числа элементов max_size()
• удаление элементов clear(), erase()

В зависимости от того насколько похоже внутреннее устройство контейнеров и правила работы с ними те или иные контейнеры могут иметь еще несколько общих операций.

Например, стек и очередь имеют методы с одинаковыми именами, но они имеют разное смысловое значение:

vector - имеет самый богатый набор функций

• изменение размеров resize()
• изменение емкости reserve()
• определение емкости capacity()
• доступ к элементам по индексу и итератору operator[], at(), front(), back()
• вставка элементов в вектор insert(), push_back(), pop_back()
• инициализация элементов assign()

При реализации структур данных, предназначенных для организации такого хранения элементов, что они могут эффективно вставляться и удаляться в любом месте этой структуры и не требует доступа по индексу, целесообразно использовать списки. Это подходящая структура данных для хранения упорядоченной, но не проиндексированной информации. Например, вершины многоугольника, или ломаной линии, список графических примитивов описывающих оценку, список возможных значений какого-либо атрибута при реализации интерфейсов и т.п.

Возможны различные реализации списков.

Для того, чтобы понять как использовать такую структуру данных, в каких случаях использовать эту эффективную структуру рассмотрим возможную реализацию такого объекта как List. (простой двусвязный список)

Каждый элемент должен хранить ссылки на последующий и предыдущий элемент. Для того, чтобы отделить хранимые объекты от способа хранения вводится вспомогательный объект УЗЕЛ (Node)

Узел - объекты, который содержит ссылки на последующий и предыдущий элементы, а также значение данного элемента списка.

template <class PAR>

class Node

{

private:

PAR m_value;

Node* m_next;

Node* m_prev;

public:

Node(PAR value);

Node* next();

Node* prev();

Node* insert(Node* n);

Node* remove(Node* n);

};

// конструктор

template <class PAR>

Node::Node(PAR value)

{

m_next=this;

m_prev=this;

m_value=value;

}

// обычные селекторы

template <class PAR>

Node* Node::next()

{

return m_next;

}

template <class PAR>

Node* Node::prev()

{

return m_prev;

}

// вставка значения после данного узла

template <class PAR>

Node* Node::insert(Node* n)

{

n->m_next=m_next; // 1

n->m_prev=this; // 2

m_next->m_prev=n // 3

m_next=n // 4

return n;

}

// удаление узла из блока

template <class PAR>

Node* Node::remove()

{

m_prev->m_next=m_next; // 1

m_next->m_prev=m_prev; // 2

m_next=m_prev=this; // 3

return this;

}

template <class PAR>

class List

{

private:

Node<PAR>* m_head;

Node<PAR>* m_tale;

Node<PAR>* m_win;

int m_length;

public:

List();

~List();

PAR front();

PAR back();

void push_front(PAR& x);

void pop_front();

void push_back(PAR& x);

void pop_back();

int size();

bool empty();

PAR value();

PAR next();

PAR prev();

void remove();

void insert(PAR& x);

};

// конструктор

template <class PAR>

List<PAR>::List()

{

m_length=0;

m_head=new Node<PAR>();

m_tale=m_win=m_head;

}

// деструктор

template <class PAR>

List<PAR>::~List()

{

while(m_length > 0)

{

front();

remove();

}

delete m_head;

}

// вставка

template <class PAR>

void List<PAR>::insert(PAR& x)

{

m_win.insert(new Node(x));

}

// удаление

template <class PAR>

void List<PAR>::remove()

{

m_win.remove();

}

Библиотека STL предоставляет все возможные контейнеры, кроме деревьев. Это связано с тем, что при решении разных задач к деревьям предъявляются разнообразные требования и выработать обобщенный шаблон этой структуры данных достаточно сложно.

Все рассмотренные нами контейнеры эффективны для хранения элементов, включения и удаления элементов, преобразования порядка следования. Но они не эффективны для поиска. Для поиска нужного элемента следует перебрать все элементы хранящиеся в нем. Чтобы этого избежать следует хранить элементы в контейнеры упорядочено. Такое хранение позволяет организовать например двоичные деревья.

template <class T>

class TReeNode

{

private:

TreeNode* l_child;

TreeNode* r_child;

T value;

public:

TreeNode(T);

~TreeNode();

T value;

TreeNode* LeftChild();

TreeNode* RightChild();

}

Упорядоченное хранение можно организовать следующим образом: элементы можно располагать так, что для каждого элемента все элементы в левом поддереве будет меньше, а в правом поддереве будут больше этого элемента.

template <class T>

class BinaryTree

{

private:

TreeNode* root;

public:

SearchTree();

void insert(T);

}

compare(val1,val2)

{

if(val1 < val2)

{

return -1;

}

else if(val1 > val2)

{

return 1;

}

else

{

return 0;

}

}

SearchTree::find(T val)

{

TreeNode* n=root;

while(n)

{

int result=compare(val,n->val);

if(result < 0)

n=n->l_child;

else if(result > 0)

n=n->r_child;

else

return n->val;

}

return n;

}

void insert(T val)

{

if(root == NULL)

{

root=new TreeNode<T> (val);

return;

}

else

{

int result;

TreeNode<T> *p, *n=root;

while(n != 0)

{

p=n; // определяет положение элемента предок нового узла

result=compare(val,p->val);

if(result < 0)

n=p->l_chald;

else if(result > 0);

n=p->r_child;

else

return;

}

if(result < 0)

p->l_child=new TreeNode<T>(val);

else

p->r_child=new TreeNode<T>(val);

}

}

findMin()

{

TreeNode *n=findMin(root);

return(n ? n->val : 0);

}

findMin(TreeNode<T> *n)

{

if(n == 0)

return o;

while(n->l_child)

n=n->l_child;

return n;

}

Называют отображением или картой (map) или словарем (dictionary). Содержит связанные пары "ключ-значение" ("key-value"). Т.о. ассоциативный массив - это массив, для которого индекс может иметь нецелочисленное значение. Библиотека STL предоставляет такие ассоциативные контейнеры:

• map - ассоциативный массив, по ключу в контейнере хранится одно значение
• multimap - ассоциативный массив с повторяющимися ключами
• set - ассоциативный массив уникальных ключей без значений
• multiset - ассоциативный массив с повторяющимися ключами без значений

Ассоциативные контейнеры организуются как сбалансированное дерево узлов, значение которого представляет собой пару значений pair <const key, mapped_type>.

Перемещения с использованием итератора также справедливы как и для других контейнеров, но при разыменовании итератора ? экземпляр объекта pair.

Первый элемент пары first является ключом, а второй значением.

map <string, int> book;

map <string, int>:: iterator i;

for(i=book.begin(); i!=book.end();i++)

{

cout<<p->first<<" "<<p->second<<endl;

}

Но более типичная работа со значениями хранящимися в ассоциативном массиве - это доступ к элементам по ключу. При этом используется привычный оператор [].

Оператор индикации выполняет поиск по ключу, заданному в качестве индекса и возвращает соответствующее значение.

Если ключ не найден, то в ассоциативный массив вставляется элемент с этим ключом и значением по умолчанию (для встроенных типов 0).

map <string, float> m;

int x=m["Бублик"]; // т.к. массив пуст, то создается новая запись

// и инициализируется 0

m["Бублик"]=1.60f; // присваиваем значение записи с ключом

...

float total;

map <string, float>::iterator i;

for(i=m.begin(); i!=m.end(); i++)

{

total+=p->second;

cout<<p->first<<'t'<<p->second<<endl;

}

cout<<"- - - - - - - - - - - - n total t"<<total<<endl;

Элементы в ассоциативном массиве хранятся упорядоченно (отсортировано), поэтому будут выведены в лексикографическом порядке).

Общие методы для всех ассоциативных контейнеров:

find(key& key) - возвращает итератор, указывающий на элемент с заданным ключом

lower_bound(key) - начало последовательности элементов с ключом key

upper_bound(key) - конец последовательности элементов с ключом key

equal_range(key) - возвращает пару контейнеров first - начало, second - конец последовательности с ключом key

count(key) - находит количество элементов с ключом key