Разумеется, вектор реализован в виде шаблона класса. Так, мы можем написать

Есть два существенных отличия нашей реализации шаблона класса Array от реализации шаблона класса vector. Первое отличие состоит в том, что вектор поддерживает как присваивание значений существующим элементам, так и вставку дополнительных элементов, то есть динамически растет во время выполнения, если программист решил воспользоваться этой его возможностью. Второе отличие более радикально и отражает существенное изменение парадигмы проектирования. Вместо того чтобы поддержать большой набор операций-членов, применимых к вектору, таких, как sort(), min(), max(), find()и так далее, класс vector предоставляет минимальный набор: операции сравнения на равенство и на меньше, size() и empty(). Более общие операции, перечисленные выше, определены как независимые обобщенные алгоритмы.

Для использования класса vector мы должны включить соответствующий заголовочный файл.

Так же, как наш класс Array, класс vector поддерживает операцию доступа по индексу. Вот пример перебора всех элементов вектора:

Для такого перебора можно также использовать итераторную пару. Итератор – это объект класса, поддерживающего абстракцию указательного типа. В шаблоне класса vector определены две функции-члена – begin() и end(), устанавливающие итератор соответственно на первый элемент вектора и на элемент, который следует за последним. Вместе эти две функции задают диапазон элементов вектора. Используя итератор, предыдущий пример можно переписать таким образом:

Определение переменной iter

инициализирует ее адресом первого элемента вектора vec. iterator определен с помощью typedef в шаблоне класса vector, содержащего элементы типа int. Операция инкремента

перемещает итератор на следующий элемент вектора. Чтобы получить сам элемент, нужно применить операцию разыменования:

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

алгоритмы поиска: find(), find_if(), search(), binary_search(), count(), count_if();

алгоритмы сортировки и упорядочения: sort(), partial_sort(), merge(), partition(), rotate(), reverse(), random_shuffle();

алгоритмы удаления: unique(), remove();

численные алгоритмы: accumulate(), partial_sum(), inner_product(), adjacent_difference();

алгоритмы генерации и изменения последовательности: generate(), fill(), transform(), copy(), for_each();

алгоритмы сравнения: equal(), min(), max().

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

Чтобы применить алгоритм sort() только к первой половине вектора, мы напишем:

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

Упорядочить весь массив можно вызовом алгоритма sort():

Так можно упорядочить первые четыре элемента:

Для использования алгоритмов в программу необходимо включить заголовочный файл

Ниже приведен пример программы, использующей разнообразные алгоритмы в применении к объекту типа vector:

Стандартная библиотека С++ поддерживает и ассоциативные массивы. Ассоциативный массив – это массив, элементы которого можно индексировать не только целыми числами, но и значениями любого типа. В терминологии стандартной библиотеки ассоциативный массив называется отображением (map). Например, телефонный справочник может быть представлен в виде ассоциативного массива, где индексами служат фамилии абонентов, а значениями элементов – телефонные номера:

(Классы векторов, отображений и других контейнеров в подробностях описываются в главе 6. Мы попробуем реализовать систему текстового поиска, используя эти классы. В главе 12 рассмотрены обобщенные алгоритмы, а в Приложении приводятся примеры их использования.)

В данной главе были очень бегло рассмотрены основные аспекты программирования на С++, основы объектно-ориентированного подхода применительно к данному языку и использование стандартной библиотеки. В последующих главах мы разберем эти вопросы более подробно и систематично.

Упражнение 2.22

Поясните результаты каждого из следующих определений вектора:

Упражнение 2.23

Напишите две реализации функции min(), объявление которой приведено ниже. Функция должна возвращать минимальный элемент массива. Используйте цикл for и перебор элементов с помощью

индекса

итератора

elemType min (const vector<elemType> &vec);