2.2 Контейнеры с последовательным доступом

Популярны vector,list. Остальные типы практически не используются и будут лишь упомянуты.

2.2.1 Вектор (vector)

Обертка вокруг массива: поэтому к элементам можно достучаться и через смещения адресов. Расширение и сужение массива происходит автоматически: например, выделилось в векторе место на 4 элемента, а вы вставляете 5-й. Пересоздастся массив большего размера (с запасом), данные с предыдущего массива скопируются в новый, а также вставится новый элемент. В примере ниже разобраны наиболее популярные методы вектора. С остальными можете поиграться дома.

Пример:

#include "stdafx.h"

#include <vector>

#include <iostream>

using namespace std;

struct Point

{

Point(int x, int y) : X(x), Y(y)

{

}

Point() : X(0), Y(0)

{

}

int X;

int Y;

};

void DemonstrateVector()

{

// 1. Объявление вектора элементов какого-то типа.

vector<Point> points;

// 2. Добавление элементов

points.push_back(Point(13,22));

points.push_back(Point(22, 13));

// 3. Доступ к элементам

// 3.1 С проверкой индекса

cout << "Points[0].X = " << points.at(0).X;

// 3.2 Без проверки индекса

cout << "Points[0].X = " << points[0].X;

// 4. Проход по содержимому вектора

// 4.1 Через методы

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

{

cout << "Point " << i << ": X = " << points[i].X << ", Y = " << points[i].Y;

}

// 4.2 Через итератор

for (auto iterator = points.begin(); iterator != points.end(); ++iterator)

{

cout << "Point " << "X = " << iterator->X << ", Y = " << iterator->Y;

}

// 4.3 Через итератор, замаскированный в for.

for (auto &element: points)

{

cout << "Point " << "X = " << element.X << ", Y = " << element.Y;

}

// 5. Вставка элемента в произвольную позицию

// Поскольку вектор оборачивает массив, то вставка

// приведет к необходимости перемещения элементов.

// Также поддерживается вставка массивов, фрагментов других контейнеров (через итераторы).

points.insert(

points.begin() + 1,

Point(666, 666));

// 6. Удаление элемента с произвольной позиции. Производительность, как и у вставки.

points.erase(points.begin() + 1);

}

int _tmain(int argc, _TCHAR* argv[])

{

DemonstrateVector();

}

2.2.2 Список (list)

Поддерживает быстрое удаление и вставку. Быстрый произвольный доступ не поддерживается. Быстро работает только последовательный доступ. Обертка вокруг двусвязного списка: по нему можно ходить в обе стороны.

#include "stdafx.h"

#include <list>

#include <iostream>

using namespace std;

struct Point

{

Point(int x, int y) : X(x), Y(y)

{

}

Point() : X(0), Y(0)

{

}

int X;

int Y;

};

void DemonstrateList()

{

// 1. Объявление списка элементов какого-то типа.

list<Point> points;

// 2. Добавление элементов

// 2.1 Единичных элементов

points.push_back(Point(13, 22));

points.push_back(Point(22, 13));

// 2.2 Массивов (у векторов аналогичным способом вставка массивов происходит)

int array[4] = { 2, 6, 4, 8 };

points.insert(points.begin(),

array,

array + 4);

// 2.3 Содержимого другого контейнера (у векторов аналогичным способом вставка массивов происходит)

list<Point> otherContainer;

otherContainer.push_back(Point(2, 3));

points.insert(points.begin(),

otherContainer.begin(),

otherContainer.end());

// 3. Доступ к произвольному элементу:

// делается через извращение с advance, контейнер не рассчитан на это,

// если это надо, то нужно вектор использовать.

auto element13Iterator = points.begin();

advance(element13Iterator, 12);

cout << element13Iterator->X;

// 4. Проход по содержимому списка

// 4.1 Через итератор

for (auto iterator = points.begin(); iterator != points.end(); ++iterator)

{

cout << "Point " << "X = " << iterator->X << ", Y = " << iterator->Y;

}

// 4.2 Через итератор, замаскированный в for.

for (auto &element : points)

{

cout << "Point " << "X = " << element.X << ", Y = " << element.Y;

}

// 5. Вставка элемента в произвольную позицию

auto whereToInsert = points.begin();

advance(whereToInsert, 1);

points.insert(

whereToInsert,

Point(666, 666));

// 6. Удаление элемента с произвольной позиции.

auto whereToDelete = points.begin();

advance(whereToDelete, 1);

points.erase(whereToDelete);

// 7. Удаление элементов по критерию

auto pointIterator = points.begin();

while (pointIterator != points.end())

{

if (pointIterator->X > 13) // критерий удаления.

{

pointIterator = points.erase(pointIterator);

}

else

{

++pointIterator;

}

}

}

int _tmain(int argc, _TCHAR* argv[])

{

DemonstrateList();

}