STL-контейнеры

компиляции и выполнения следующего кода?
#include
 using namespace std;

 class A {

int i;
public:
A() { cout << "in A::A()" << endl; i = 0; }
A operator = (A a) { cout << "in A::operator=(A)" << endl; i = a.i; }
};
 

int main() {
A a;
A b = a;
return 0;
}

Варианты ответа:
- возникнет ошибка времени выполнения
- in A::A() in A::operator=(A)
- in A::operator=(A)
- in A::A()
- возникнет ошибка компиляции

При A b = a; вызывается автоматически сгенерированный конструктор копирования, а не оператор присваивания, поэтому оператор присваивания ничего вывести не может, т.к. никогда не вызывается.

контейнеры,
итераторы,
алгоритмы,
объекты_функции,
адаптеры,
распределители (памяти).

– это не зависящая от структуры данных абстракция, позволяющая получать

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

следующее множество контейнерных классов:
Последовательные контейнеры:
vector – вектор
deque – дека

list – список
slist – односвязный список
bit_vector – vector

Ассоциативные контейнеры:
set – множество
map – отображение (словарь)
multiset – мультимножество
multimap – мультиотображение
hash_set – хешированное множество
hash_map – хешированное отображение (словарь)
hash_multiset – хешированное мультимножество
hash_multimap – хешированное мультиотображение
hash – хеш-функция

Упаковка строк (string package):
char_traits – трактовка символов
basic_string – базисная строка

Контейнерные адапторы:
stack - стек
queue – очередь
priority_queue – очередь с порядком

Прочие :
rope – специальная строка
bit_set – множество битов

В общем случае к итератору можно применять операции инкремента, разыменования

и сравнения. К некоторым итераторам применимы также операции декремента и указательная арифметика. Категория итератора определяется набором осмысленных операций, которые можно к нему применить.
В настоящее время в стандартной библиотеке определено пять категорий итераторов:
итератор ввода (input – InIter),
итератор вывода (output – OutIter),
однонаправленный итератор (forward – ForIter),
двунаправленный итератор (bidirectional – BiIter),
итератор с произвольным доступом (random access – RandIter).

функций, которые применяются к диапазонам, определяемым итераторами, и выполняют некоторые

операции над самими диапазонами или над хранящимися в них элементами.
Например, алгоритм std::distance() не разыменовывает переданные ему итераторы, а просто вычисляет число элементов в представленном с их помощью диапазоне.
Напротив, алгоритм std::transform() присваивает элементам из одного диапазона преобразованные значения элементов из другого диапазона.

std::vector v1 = . . . ;
std::vector v2(v1.size());
std::transform(v1.begin(), v1.end(), v2.begin(), ::abs);

есть operator()), является классом функтора. Объекты, созданные на основе таких

классов, называются объектами функций, или функторами. Как правило, в STL объекты функций могут свободно заменяться «обычными» функциями, поэтому под термином «объекты функций» часто объединяются как функции C++, так и функторы.
Можно сказать, что объектом_функцией, или функтором называется объект, который можно вызывать. Объекты_функции используются прежде всего в сочетании с алгоритмами, где встречаются в виде предикатов или функций. Предикат принимает один или несколько аргументов и возвращает булевское значение, позволяя тем самым управлять выбором элементом из диапазона.
Функция принимает нуль или более аргументов и возвращает значение, которое можно использовать для трансформации или присваивания элементам.

С++ содержит специальные контейнерные адаптеры, предназначенные для особых целей. В

их реализации применяются основные контейнерные классы.
Ниже перечислены стандартные контейнерные адаптеры, определенные в библиотеке.
Стеки – контейнеры, элементы которых обрабатываются по принципу LIFO (последним прибыл, первым обслужен).
Очереди – контейнеры, элементы которых обрабатываются по принципу FIFO (первым прибыл, первым обслужен). Иначе говоря, очередь представляет собой обычный буфер.
Приоритетные очереди - контейнеры, элементам которых назначаются приоритеты. Приоритет определяется на основании критерия сортировки, переданного программистом (по умолчанию используется оператор <). В сущности, приоритетная очередь представляет собой буфер, следующий элемент которого всегда обладает максимальным приоритетом в очереди. Если максимальный приоритет назначен сразу нескольким элементам, порядок следования элементов не определен.

специализиро-ванных итераторов, называемых итераторными адаптерами. Итераторные адаптеры являются не обычными

вспомогательными классами; они наделяют саму концепцию итераторов рядом новых возможностей.
Выделяют три разновидности итераторных адаптеров:
итераторы вставки;
back_inserter (контейнер) – элементы присоединяются с конца в прежнем порядке с использованием функции push_back()
front_inserter (контейнер) – элементы вставляются в начало в обратном порядке с использованием функции push_front()
inserter (контейнер, позиция) – элементы вставляются в заданной позиции в прежнем порядке с использованием функции insert()
потоковые итераторы;
istream_iterator и оstream_iterator
обратные итераторы.
Эти итераторы работают в противоположном направлении: вызов оператора
++ на внутреннем уровне преобразуется в вызов оператора --, и наоборот.
Все контейнеры поддерживают создание обратных итераторов функциями
rbegin() и rend().

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

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

функциональностью.

Главное – это освобождение программиста от проблем захвата и

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

Использование контейнеров STL сразу открывает широкие возможности по использованию готовых алгоритмов и функций STL.

Популярность контейнеров STL легко объяснима — просто они превосходят своих конкурентов, будь то контейнеры из других библиотек или самостоятельные реализации.

называемых контейнерами со смежной памятью) элементы хранятся в одном или

нескольких динамически выделяемых блоках памяти, по несколько элементов в каждом блоке. При вставке нового или удалении существующего элемента другие элементы того же блока сдвигаются вверх или вниз, освобождая место для нового элемента или заполняя место, ранее занимаемое удаленным элементом. Подобные перемещения влияют как на скорость работы, так и на безопасность. К числу стандартных блоковых контейнеров относятся vector, string и deque. Нестандартный контейнер rope также является блоковым.
В узловых контейнерах каждый динамически выделенный фрагмент содержит ровно один элемент. Операции удаления и вставки выполняются только с указателями на узлы, не затрагивая содержимого самих узлов, и потому обходятся без перемещений данных в памяти. К этой категории относятся контейнеры связанных списков (такие как list и slist), а также все стандартные ассоциативные контейнеры, обычно реализуемые в форме сбалансированных деревьев. Реализация нестандартных хэшированных контейнеров тоже построена на узловом принципе.

Type, class Allocator = allocator > class vector
Здесь Type –

тип хранящихся в контейнере данных, Allocator – распределитель памяти, по умолчанию – стандартного типа allocator.

Конструкторы:
vector(); – конструктор, создающий пустой вектор

vector(size_type n); – конструктор, создающий вектор из n элементов

vector(size_type n, const T& t); – конструктор, создающий вектор из n элементов, содержащих значение t

vector(const vector&); – конструктор копирования

template vector (InIterBegin, InIterEnd);
– конструктор, создающий вектор по диапазону

vector vi;
vector ::iterator It;

int buf=0; // Добавление элементов
while(cout <<"Input: ", cin >> buf, buf!=0) vi.push_back(buf);
cout << "Vector size: "< cout << "Vector value:";
for (int i=0; i < static_cast(vi.size()); cout < cout << endl;
It = vi.begin();
while ( It != vi.end( ))
cout << *It++ << " ";
cout << endl;
vi.erase(vi.begin(), vi.end());
cout << "Vector size: "<}

std ;
typedef vector INTVECTOR;
int main()
{ INTVECTOR V;
cout

<< "Initial:\n0) size is: " << V.size() << endl;
cout << "0) maximum size is: " << V.max_size() << endl;
cout << "0) capacity is: " << V.capacity() << endl;
V.push_back(54); cout << endl;
cout << "After adding:\n1) size is: " << V.size() << endl;
cout << "1) capacity is: " << V.capacity() << endl;
V.reserve(10); cout << endl;
cout << "After reserved:\n2) size is: " << V.size() << endl;
cout << "2) capacity is: " << V.capacity() << endl;
V.resize(20); cout << endl;
cout << "After resized:\n3) size is: " << V.size() << endl;
cout << "3) capacity is: " << V.capacity() << endl;
}

< class Type, class Allocator = allocator > class deque

Здесь Type – тип хранящихся в контейнере данных, Allocator – распределитель памяти, по умолчанию – стандартного типа allocator.

Конструкторы:
deque(); – конструктор, создающий пустую очередь

deque(size_type n); – конструктор, создающий очередь из n элементов

deque(size_type n, const T& t); – конструктор, создающий очередь из n элементов, содержащих значение t

deque(const deque&); – конструктор копирования

template deque(InIterBegin, InIterEnd);
– конструктор, создающий очередь по диапазону

и у вектора:
allocator_type, const_iterator, const_pointer, const_reference, const_reverse_iterator,

difference_type, iterator, pointer, reference, reverse_iterator, size_type, value_type

Члены-функции класса deque те же, что и для вектора, за исключением:

элементов с обоих концов очереди, то выгодно использовать в качестве

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

Элементы двусторонней очереди размещаются в блоках фиксированного размера и хранится массив указателей на эти блоки. Черным цветом обозначены существующие элементы очереди, белым – захваченная память.
Поскольку все блоки имеют одинаковый размер, то мы можем обеспечить вычисление позиции требуемого блока без перебора элементов. Фактически, для деки мы можем использовать выражение D[i] как для массива или вектора, равно как выражение *(D.begin()+i)

deque vi;
deque ::iterator It;

int buf=0; // Добавление элементов
while(cout <<"Input: ", cin >> buf, buf!=0) vi.push_back(buf);
cout << "Deque size: "< cout << "Deque value:";
for (int i=0; i < static_cast(vi.size()); cout < cout << endl;
It = vi.begin();
while ( It != vi.end( ))
cout << *It++ << " ";
cout << endl;
vi.erase(vi.begin(), vi.end());
cout << "Deque size: "<}

class Type, class Allocator = allocator > class list
Здесь Type

– тип хранящихся в контейнере данных, Allocator – распределитель памяти, по умолчанию – стандартного типа allocator.

Конструкторы:
list(); – конструктор, создающий пустую очередь

list(size_type n); – конструктор, создающий очередь из n элементов

list(size_type n, const T& t); – конструктор, создающий очередь из n элементов, содержащих значение t

list(const list&); – конструктор копирования

template list(InIterBegin, InIterEnd);
– конструктор, создающий очередь по диапазону

что и у вектора:
allocator_type, const_iterator, const_pointer, const_reference,

const_reverse_iterator, difference_type, iterator, pointer, reference, reverse_iterator, size_type, value_type

Члены-функции класса list по сравнению с вектором:

list vi;
list ::iterator It;

int buf=0; // Добавление элементов
while(cout <<"Input: ", cin >> buf, buf!=0) vi.push_back(buf);
cout << "List size: "< cout << "List value:";
It = vi.begin();
while ( It != vi.end( ))
cout << *It++ << " ";
cout << endl;
vi.erase(vi.begin(), vi.end());
cout << "List size: "<}

не работает со списками. Вместо него включена функция-член класса sort.
Функция

unique удаляет повторяющиеся последовательные элементы.

#include
using namespace std;
#include
void out(char *s, const list &L)
{ cout << s;
copy(L.begin(), L.end(), ostream_iterator (cout, " ")); cout << endl;
}

void main()
{ list L(5,123);
L.push_back(100); L.push_back(123); L.push_back(123); out ("Initial:\n",L);
L.unique(); out ("After unique:\n",L);
L.sort(); out ("After sort:\n",L);
}

элементов из одного списка в другой не перераспределяя память.
void splice(iterator

position, list& x);
Если i является допустимым итератором для списка L, то следующая операция вставляет содержимое списка M перед i в L, оставляя M пустым:
L.splice(i,M);
Внимание! L и M должны обязательно быть разными!
void splice(iterator position,list& x, iterator j);
Если i является допустимым итератором для списка L, а j – для M, то следующая операция удаляет элемент, на который ссылается j, и вставляет его перед i. Возможно, что L и M – это один и тот же список.
L.splice(i,M,j);
void splice(iterator position, list& x, iterator f, iterator l);
Если i является допустимым итератором для списка L, а [j1,j2] – допустимым диапазоном для M, то следующая операция удаляет элементы этого диапазона и вставляет их перед i. L и M могут быть одним и тем же списком.
L.splice(i,M,j1,j2);

void main()
{ list L;
list ::iterator i,j1,j2,j;
for (int

k=1; k<=8; k++) {
L.push_back(k);
j = L.end();
if(k==2) j1 = --j; else
if (k==5) j2 = --j; else
if (k==7) i = --j;
}
L.splice(i,L,j1,j2);
copy(L.begin(), L.end(),
ostream_iterator(cout," "));
cout << endl;
char s; cin >>s;
}

Результат сцепки:
1 5 6 2 3 4 7 8

Важно!
Можно использовать ––j, но нельзя : j2 = j – 1
(для итератора такой операции нет!)

с заданным значением лучше всего использовать функцию-член класса remove.
#include
using

namespace std;
#include
void out(char *s, const list &L)
{ cout << s;
copy(L.begin(), L.end(), ostream_iterator (cout, " ")); cout << endl;
}

void main()
{ list L;
L.push_back(1); L.push_back(4); L.push_back(1);
L.push_back(3); L.push_back(1); L.push_back(2);
out ("Initial:\n",L);
L.remove(1);
out ("After remove:\n",L);
}

функция-член класса merge.
#include
using namespace std;
#include
void out(char *s, const

list &L)
{ cout << s;
copy(L.begin(), L.end(), ostream_iterator (cout, " ")); cout << endl;
}

void main()
{ list L1, L2;
L1.push_back(1); L1.push_back(4); L1.push_back(6);
L2.push_back(3); L2.push_back(5); L2.push_back(8);
out ("Initial 1:\n",L1); out ("Initial 2:\n",L2);
L1.merge(L2);
out ("After merge:\n",L1);
}

Все списки должны быть упорядочены в соответствии с некоторым отношением

связан со следующим и не связан с предыдущим.
Этот контейнер

реализован не во всех библиотеках STL, в частности, в Microsoft – версии, представленной в Studio, его нет.
Главное отличие этого списка от контейнера list состоит в том, что итераторы list являются двунаправленными (bidirectional) , а итераторы slist – однонаправленными итераторами (forward).
С точки зрения эффективности следует заметить, что функции вставки (insert), сцепки (splice) и удаления (erase) выполняются значительно медленнее, поскольку основаны на дополнительном переборе от начала списка перед выполнением собственно операции вставки и удаления.
Для ликвидации этого «перекоса» в интерфейс добавлены функции-члены insert_after, splice_after и erase_after , которыми и рекомендуется пользоваться всякий раз вместо общих функций insert, splice и erase.
Следует отметить, что в ряде случаев slist превосходит list и по затратам памяти, и по скорости работы.

L.push_front(0);
L.push_front(1);
L.insert_after(L.begin(), 2);

copy(L.begin(), L.end(), // The output is 1 2 0
ostream_iterator (cout, " "));
cout << endl;
slist::iterator back = L.previous(L.end());
back = L.insert_after(back, 3);
back = L.insert_after(back, 4);
back = L.insert_after(back, 5);
copy (L.begin(), L.end(), // The output is 1 2 0 3 4 5
ostream_iterator (cout, " "));
cout << endl;
}