Контейнерные типы данных (vector, list, map, set).

Контейнеры служат для хранения данных. Последовательный контейнер содержит упорядоченный набор элементов одного типа. Можно выделить два основных типа контейнеров – вектор (vector) и список (list). Третий последовательный контейнер – двусторонняя очередь (deque) – обеспечивает ту же функциональность, что и vector, но особенно эффективно реализует операции вставки и удаления первого элемента. deque следует применять, например, при реализации очереди, из которой извлекается только первый элемент. Все сказанное ниже относительно вектора применимо также и к deque. Трудоемкость O n.

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

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

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

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

int main() {

vector< string > svec;

svec.reserve(32); // задает емкость равной 32

//...

}

 

Ассоциативный контейнер эффективно реализует операции проверки существования и извлечения элемента. Два основных ассоциативных контейнера – это отображение (map) и множество (set). map состоит из пар ключ/значение, причем ключ используется для поиска элемента, а значение содержит хранимую информацию. Телефонный справочник хорошо иллюстрирует понятие отображения: ключом является фамилия и имя абонента, а значением – его телефонный номер. Элемент контейнера set содержит только ключ, поэтому set эффективно реализует операцию проверки его существования. В контейнерах map и set не может быть дубликатов – повторяющихся ключей. Для поддержки дубликатов существуют контейнеры multimap и multiset. Трудоемкость O log n.

В map хранятся пары ключ/значение.

map<string,int> word_count;

 

Итераторы.

Итератор предоставляет обобщенный способ перебора элементов любого контейнера – как последовательного, так и ассоциативного.

Все контейнеры имеют функции-члены begin() и end() - begin() возвращает итератор, указывающий на первый элемент контейнера. - end() возвращает итератор, указывающий на элемент, следующий за последним в контейнере.

// vector<string> vec;vector<string>::iterator iter = vec.begin();vector<string>::iterator iter_end = vec.end();

 

Итераторы поддерживают адресную арифметику. Арифметические действия с итераторами возможны только для контейнеров vector и deque. list не поддерживает адресную арифметику, поскольку его элементы не располагаются в непрерывной области памяти.

Для того чтобы напечатать все элементы вектора, нужно написать:

vector<string> name;vector<string>::iterator itt;for(itt=name.begin(); itt!= name.end(); itt++) cout << *itt << '\n';