Class vector {
...
};
Первый параметр T определяет тип элементов вектора, а второй параметр Allocator инкапсулирует модель памяти программы (использование этого параметра позволяет исключить необходимость изменения реализации вектора при переходе к новой модели памяти).
Чтобы создать вектор в программе, достаточно записать, например:
vector<float> v; // “пустой” вектор
vector<float> w(10); // вектор из 10 нулевых элементов
vector<float> x(5, 3.25); // вектор вида (3.25,3.25,3.25,3.25,3.25)
В результате компилятор инстанцирует класс vector<float>, а при выполнении программы происходит вызов конструктора, который формирует объекты v, w, x класса vector<float>. В дальнейшем в вектор v (или w, или x) можно будет добавить элементы типа float, удалить их, вывести содержимое вектора в поток, определить его длину и т.д. Все эти действия инкапсулированы в классе vector<float>. Например, для определения текущей длины вектора можно использовать компонентную функцию size, вставка элемента в конец вектора выполняется функцией push_back, обращение к заданному элементу осуществляется через операцию operator[], первый и последний элементы возвращаются функциями front и back соответственно, «пустота» вектора проверяется функцией empty.
Названные выше и некоторые другие функции сосредоточены внутри шаблона vector (список его функций можно получить из файла vector.h, где определен этот шаблон); кроме них, вектор могут обрабатывать и глобальные функции, реализующие алгоритмы STL. Однако, для доступа к вектору они должны взаимодействовать с итераторами. Итераторы по сути обобщают понятие указателя и ассоциируются с каждым контейнером, включая и вектор.
В шаблоне vector (и других шаблонах контейнеров) имеются две специальные функции, играющие особую роль для алгоритмов STL. Это функции begin и end. Обе они возвращают итераторы, при этом итератор, возвращаемый функцией begin, указывает на первый элемент вектора, а итератор, возвращаемый функцией end, ссылается за последний элемент вектора (его называют past-the-end-итератором). Вместе указанные итераторы образуют открытый справа диапазон, в котором могут работать алгоритмы. Графически это можно представить так, как показано на рисунке 9.
Рис. 9
Пример
vector<int> v(3);
v[0] = 5;
v[1] = 2;
v[2] = 7;
// Определение итераторов
vector<int>::iterator first = v.begin();
vector<int>::iterator last = v.end();
Sort(first,last); // сортировка вектора в диапазоне итераторов
while (first != last) // перебор диапазона итератора
cout << *first++ << " "; // вывод элементов вектора
Работа со списками и двухсторонними очередями организуется аналогично работе с векторами. Контейнеры этих видов также содержат функции begin и end, отображающие диапазон итераторов, есть функции для вставки элементов, удаления и т.д. Основные отличия рассматриваемых контейнеров друг от друга заключаются в наборах допустимых операций, временной сложности выполнения операций, а также корректности итераторов после реализации тех или иных действий. Например, к списку, в отличие от вектора, нельзя обратиться прямо через операцию [] (возможен только последовательный доступ), а в очередь deque элементы можно добавлять как в конец, так и в начало (появляется функция push_front). Вставка элемента в список не нарушает корректность итераторов на другие элементы списка, а в векторе все итераторы после точки вставки становятся некорректными. Для работы со списком следует включить файл list.h, а для deque – файл deque.h.
Ниже приведена функция, выполняющая поэлементное сравнение списков класса list<int>.
bool CompareLists(const list<int> & List1, const list<int> & List2)
{
if(List1.size() != List2.size())
return false; // списки различны по длине – сравнение не нужно
list<int>::const_iterator43 i1 = List1.begin();
list<int>::const_iterator i2 = List2.begin();
// цикл поэлементного сравнения
while(i1 != List1.end()) {
if(*i1 != *i2)
return false; // списки отличаются
++i1; // передвинуть итераторы
++i2;
}
return true; // списки совпали
}
9.3. Итераторы
Итератор, как мы уже отмечали выше, представляет собой обобщение указателя. Его основная задача – обеспечить унифицированный перебор элементов в любом контейнере, построенном в соответствии с принципами STL. Итератор задается в виде соответствующего шаблонного класса, который обязательно инкапсулирует операции разыменования, инкремента, декремента и присваивания. В STL выделяются пять категорий итераторов, отличающиеся набором дополнительных операций. Эти категории следующие: итераторы произвольного доступа, двунаправленные итераторы, однонаправленные итераторы, входные итераторы, выходные итераторы44. С точки зрения возможностей итераторы произвольного доступа наиболее богаты; входные и выходные итераторы обеспечивают минимум возможностей. В соответствии с этим для итераторов вводится следующее правило применения: итератор с большими возможностями можно использовать везде, где требуется итератор с меньшими возможностями (например, двунаправленный итератор может использоваться в роли выходного итератора, но не наоборот).
Входные и выходные итераторы характеризуются минимальным набором допустимых операций (функций). Для выходных итераторов это конструктор, операция присваивания, операция разыменования, а также пре- и постинкремент. Для входных итераторов дополнительно включаются операции сравнения на равенство и неравенство. Входные и выходные итераторы могут последовательно перебирать элементы контейнера от его первого элемента до последнего.
Примером входного итератора является стандартный итератор входных потоков, который инкапсулирован в шаблоне istream_iterator. Пример выходного итератора – стандартный итератор выходных потоков ostream_iterator. Используя указанные итераторы легко, например, организовать копирование содержимого одного файла в другой: