Контейнеры библиотеки STL. Последовательности типа vector.
Теперь, когда вы вспомнили, что такое шаблоны функций и шаблоны классов, мы можем исследовать возможности стандартной библиотеки шаблонов STL. В июле 1994 года специальный комитет Международной организации по принятию стандартов (ANSI/ISO C++) проголосовал за то, чтобы принять STL в качестве части стандарта языка C++. Предложение было основано на исследовании обобщенного (generic) программирования и концепции библиотеки (generic software library), которое проводили Alex Stepanov, Meng Lee и David Musser. Главной целью при разработке библиотеки было достижение общности (generality) подхода к различным структурам данных и алгоритмам их обработки без ущерба эффективности кода.
В STL определены два типа контейнеров – последовательности (sequence containers) и ассоциативные контейнеры. Все контейнеры предназначены для хранения данных любого типа. Последовательности предполагают последовательный доступ к своим элементам, а ассоциативные контейнеры работают по принципу ассоциации ключа (key) с его значением (value). Можно считать, что ассоциативные контейнеры хранят пары произвольных элементов и производят поиск по ключу, используя технику hash-таблиц. В STL существует три типа последовательных контейнеров: vector, deque и list.
Последовательности типа vector
Для их использования необходимо подключить файл заголовков <vector> и сделать доступным (видимым) стандартное (std) пространство имен:
#include <vector> using namespace std;
Обратите внимание на отсутствие расширения.h в директиве подключения файла заголовков. Дело в том, что STL используется на множестве различных платформ с применением разных компиляторов. Файлы заголовков в разных условиях имеют разные расширения. Они могут иметь расширение Н, НРР или НХХ. Для того чтобы одинаково запутать всех разработчиков, было решено вовсе не использовать расширение для файлов заголовков библиотеки STL. Пространство имен std позволяет избежать конфликта имен. Если вы назовете какой-то свой класс тем же именем, что и класс из STL (например, string), то обращение вида std::string однозначно определит принадлежность класса стандартной библиотеке. Директива using позволяет не указывать (многократно) операцию разрешения области видимости std::, поэтому можно расслабиться и не писать std::string, a писать просто – string.
Вектор является шаблоном класса, который настраивается с помощью двух параметров:
vector<class T, allocator<class T> >
Объект, который управляет динамическим выделением и освобождением памяти типа т, называется allocator. Для большинства типов контейнеров он обычно объявляется по умолчанию в конструкторе. Для "хитрых" данных, например требующих памяти в глобальном heap, видимо, можно изобрести индивидуальный распределитель памяти. Но в большинстве случаев работает вариант по умолчанию. Кроме того, с типом vector обычно связаны 4 типа сущностей:
- Pointer – ведет себя как указатель на тип т;
- const pointer – не позволяет изменить данные типа т, на которые он указывает;
- reference – ссылки на данные типа т;
- const reference – не позволяет изменить данные типа т, на которые она ссылается.
Обычно эти сущности являются тем, чем и должны являться, но это не гарантируется. Они могут быть более сложными объектами.
Итак, vector является аналогом обычного массива в языке С, за исключением того, что он может автоматически изменять память по мере надобности. Доступ к данным обеспечивается с помощью операции выбора [ ]. Вставка новых элементов эффективна только в конец контейнера (push_back). Удаление – тоже. Данные операции в начале или середине влекут сдвиги всего массива данных, что резко снижает эффективность работы контейнера. Такие операции называются линейными, имея в виду тот факт, что время их выполнения линейно зависит от количества элементов в контейнере. Вставка или удаление в конце называются константными операциями, так как время их выполнения является константой для данной реализации и не зависит от количества элементов.
Вот простая программа, иллюстрирующая использование вектора. Так как в приложениях консольного типа обычно возникают проблемы с русификацией, то для вывода текста мы используем английский язык.