Контейнеры

Массивы

Составные типы данных

Использование Lens

Создание переменной типа Lens (или экземпляра объекта Lens) осуществляется следующим образом:

Lens x;
x.setn(1.5f); // доступ к членам класса
Lens* y=&x;
float n=y->getn(); // доступ к членам класса по указателю - оператор ->
cout<<n;
cout<<x.m_n; // ошибка: m_n - private-член
cout<<y->m_n; // ошибка та же
cout<<y.m_n; // ошибка: y - указатель
cout<<x.getn(); // правильно
cout<<y->getn(); // правильно

	Гомогенные	Гетерогенные
Назначение	для хранения однотипных переменных	для хранения неоднородных разнотипных переменных
Пример	массив, строка, список, стек, очередь, набор, карта, дерево	структура, класс

Массивы с небольшим количеством элементов легко размещаются в статической памяти программы. Так же как и обычные переменные, массивы следует инициализировать сразу после объявления. Возможна инициализация массива при объявлении:

float v[3]={0.3f, 2.2f, 2.f}; // массив из трех элементов 0-го, 1-го, 2-го. Элементы нумеруются от 0 до размер-1
char symbols[]={'a', 'b', 'c', 'd', 'e'}; // количество элементов указывать не обязательно

Доступ к элементам осуществляется с помощью оператора [], а для двумерных массивов составного оператора []:

float m[3][2]; // двумерный массив 2х3. Элементы хранятся по строкам. По два элемента в трех строках.
.......
float sum=0.f;
for (int i=0;i<3; j++)
{
for(int j=0; j<2; i++)
{
sum+=m[i][j];
}
}

Но для массивов с большим количеством элементов намного эффективнее будет динамическое размещение (а для массивов с огромным количеством элементов по другому и нельзя, так как размер сегмента данных ограничен):

float *v; // объявляем указатель на массив
v=new float[1000]; // в переменной v хранится 0-й элемент массива
// после размещения в массиве "мусор" и сразу обязательно инициализировать все его элементы
for(int i=0; i<1000; i++)
{
v[i]=0.f;
}
.......
v++; // что это? указатель на 1-й элемент
v+100; // а это? указатель на 100-й элемент
.......
delete [] v; // обязательно освободить использованную память

Доступ к элементам массива осуществляется одинаково, независимо от того как он размещен в памяти.

float s[5];
float* d=new float[5];
.....// инициализация
float x=d[3]+s[3]; // эквивалентно x=*(d+3)+*(s+3);

Передача массива в функцию может осуществляться только по указателю на нулевой элемент с дополнительной информацией о количестве элементов в мaссиве:

double sum(double* m, int n)
{
double s=.0;
for(int i=0; i<n; ++i)
{
s+=m[i];
}
return s;
}

main()
{
double* m=new double[100];
...
cout<<sum(m,100);
}

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

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

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

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

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