2.2.3Forward_list

Контейнер в виде однонаправленного списка. Поддерживает вставку и удаление элементов. Произвольный доступ медленный.

2.2.4 Очередь двухсторонняя (deque)

Последовательный индексированный контейнер. Быстрая вставка и удаление с обоих концов.

2.3 Контейнеры-адаптеры

Здесь часто используются контейнеры вида очередь и стек. Остальные типы практически не используются и лишь упомянуты.

2.3.1 Очередь односторонняя (queue)

Очередь – контейнер предназначенный для FIFOработы с объектами. Наиболее типичные варианты использования очередей:

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

2. Планирование в многозадачных операционных системах: очевидно порядок, в котором ОС будет выполнять задачи, чем-то представлен, например очередью, элементы очереди – сведения о процессах.

3. В системах, где обрабатываются заявки/клиенты в очередях.

4. Печать документов.

Очевидно, что он должен поддерживать интерфейс вида – сколько в тебе элементов?, добавить элемент, удалить элемент.

#include "stdafx.h"

#include <queue>

#include <iostream>

using namespace std;

class Task

{

private:

int Id;

public:

Task(int id) : Id(id)

{

}

void Execute()

{

cout << "Task " << Id << " executed.\n";

}

};

void AddTasks(queue<Task>& tasks)

{

cout << "Adding tasks...\n";

tasks.push(Task(13));

tasks.emplace(666); // 13 indrectly converted to Task(13).

}

void ExecuteTasks(queue<Task>& tasks)

{

cout << "Executing tasks...\n";

while (!tasks.empty())

{

Task task = tasks.front();

tasks.pop(); // remove task from queue.

task.Execute();

}

}

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

{

std::queue<Task> tasks;

AddTasks(tasks);

ExecuteTasks(tasks);

getchar();

return 0;

}

2.3.2 Очередь с приоритетами (priority queue)

То же самое, что и очередь, но вводится понятие приоритета: при доставании из очереди достаются элементы с наивысшим приоритетом (очевидно, что оператор сравнения у объектов должен быть перегружен). Редко используется.

2.3.3 Стек (stack)

Стек реализует логику LIFO. Редко используется. Наиболее типичная форма применения –Undo/Redoв текстовых редакторах. Выполненные действия хранятся в виде каких-то объектов.

2.4 Контейнеры с доступом к случайным элементам

Из контейнеров с доступом к случайным элементам используется словарь.

2.4.1 Упорядоченное множество элементов (set)

Хранит упорядоченно набор уникальных элементов. Обертка вокруг бинарного дерева поиска. Очевидно, что поменять элемент в такой коллекции скорее всего нельзя, впрочем, можно удалять и добавлять элементы. Имеется вариация множества без сортировки unsorted_set. Поскольку множества – понятие из математики, то вstlтакже добавили возможность находить объединение, пересечение и удаление множеств.

template < class T, // set::key_type/value_type

class Compare = less<T>, // set::key_compare/value_compare

class Alloc = allocator<T> // set::allocator_type

> class set;

Как видите, если не указан класс-сравниватель элементов, то элементы упорядочиваются по возрастанию.

Когда используется set?

Setиспользуется, когда требуется хранить громадные коллекции объектов, в которых нужно часто проводить поиск, в которые часто вставляются и удаляются элементы. Если таких требований нет, то используются тип попроще –vector. Если сортировка требуется не всегда, то проще отсортировать вектор (std::sort(vector.begin(),vector.end())).

Пример

#include "stdafx.h"

#include <set>

#include <iostream>

#include <algorithm>

#include <iterator>

#include <string>

using namespace std;

template <typename TData>

void Print(const set<TData>& set, const char* delimiter)

{

cout << "Set content: ";

copy(

set.begin(),

set.end(),

ostream_iterator<TData>(std::cout, delimiter));

cout << endl;

}

void PrintSet(const set<int>& set)

{

// first way.

cout << "Set content: ";

for (auto setIterator = set.begin(); setIterator != set.end(); ++setIterator)

cout << *setIterator << " ";

cout << endl;

// second way.

cout << "Set content: ";

copy(

set.begin(),

set.end(),

ostream_iterator<int>(std::cout, " "));

cout << endl;

}

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

{

// unique elements.

int elements[] = { 1, 1, 13 };

set<int> elementsSet(elements, elements + 3); // only unuqie elements were added.

PrintSet(elementsSet);

// search

set<string> namesSet = { "Test", "Abba" };

Print(namesSet, "\n");

if (namesSet.find("Test") != namesSet.end())

cout << "Test is in set\n";

// add, remove elements

namesSet.erase("Test");

namesSet.insert("We need a hero");

Print(namesSet, ", ");

getchar();

return 0;

}