Список (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();
}
Forward_list
Контейнер в виде однонаправленного списка. Поддерживает вставку и удаление элементов. Произвольный доступ медленный.
Очередь двухсторонняя (deque)
Последовательный индексированный контейнер. Быстрая вставка и удаление с обоих концов.
Контейнеры-адаптеры
Здесь часто используются контейнеры вида очередь и стек. Остальные типы практически не используются и лишь упомянуты.