Листинг 19.9. Навигация по списку с ппмощью итератора
1: #include <iostream>
2: #include <list>
3: using namespace std;
4:
5: typedef list<int> IntegerList;
6:
7: int main()
8: {
9: IntegerList intList;
10:
11: for (int i = 1; i <= 10; ++i)
12: intList.push_back(i * 2);
13:
14: for (IntegerList::const_iterator ci = intList.begin();
15: ci!= intList.end(); ++ci)
16: cout << *ci << " ";
17:
18: return 0;
19: }
Результат:
2 4 6 8 10 12 14 16 18 20
Анализ: В строке 9 объект intList определен как список целых чисел. В строках 11 и 12 с помощью функции push_back() в список добавляются первые 10 положительных четных чисел.
В строках 14-16 мы обращаемся к каждому узлу в списке, используя константный итератор. Константность указывает, что мы не собираемся изменять узлы с помощью этого итератора. Если бы мы хотели изменить узел, на который указывает итератор, пришлось бы использовать переменный итератор:
intList::iterator
Функция-член begin() возвращает итератор на первый узел списка. Оператор инкремента (++) можно использовать для перехода к итератору следующего узла. Функция-член end(), что может показаться странным, возвращает итератор на узел, расположенный за последним узлом списка. Часто метод end() используют для определения допустимых границ списка.
Разыменование итератора (для возвращения связанного с ним узла) происходит аналогично разыменованию указателя, как показано в строке 16.
Хотя понятие итератора было введено только при рассмотрении класса list, итераторы можно использовать и с векторными классами. В дополнение к функциям-членам, с которыми вы познакомились в векторном классе, базовый класс списка тоже представляет функции push_front() и pop_front(), которые работают точно так же, как и функции push_back() и pop_back(). Но вместо добавления и удаления элементов в конце списка, они добавляют и удаляют элементы в его начале.
|
|
|
Контейнер двухсторонней очереди
Двухсторонняя очередь подобна двунаправленному вектору — она наследует эффективность класса-контейнера vector по операциям последовательного чтения и записи. Но, кроме того, класс контейнер deque обеспечивает оптимизированное добавление и удаление узлов с обоих концов очереди. Эти операции реализованы аналогично классу-контейнеру list, где процесс выделения памяти запускается только для новых элементов. Эта особенность класса двухсторонней очереди устраняет потребность перераспределения целого контейнера в новую область памяти, как это приходится делать в векторном классе. Поэтому двухсторонние очереди идеально подходят для приложений, в которых вставки и удаления происходят с двух концов массива и для которых имеет важное значение последовательный доступ к элементам. Примером такого приложения может служить имитатор сборки поезда, в котором вагоны могут присоединяться к поезду с обоих концов.
|
|
|
Стеки
Одной из самых распространенных в программировании структур данных является стек. Однако стек не используется как независимый контейнерный класс, скорее, его можно назвать оболочкой контейнера. Шаблонный класс stack определен в файле заголовка <stack> в пространстве имен std.
Стек — это непрерывный выделенный блок памяти, который может расширяться или сжиматься в хвостовой части, т.е. к элементам стека можно обращаться или удалять только с одного конца. Вы уже видели подобные характеристики в последовательных контейнерах, особенно в классах vector и deque. Фактически для реализации стека можно использовать любой последовательный контейнер, который поддерживает функции back(), push_back() и pop_back(). Большинство других методов контейнеров для работы стека не используются, поэтому они и не предоставляются классом stack.
Базовый шаблонный класс stack библиотеки STL шаблона разработан для поддержания объектов любого типа. Единственное ограничение состоит в том, что все элементы должны иметь один и тот же тип.
Данные в стеке организованы по принципу "последним вошел — первым вышел". Ее можно сравнить с переполненным лифтом: первый человек, вошедший в лифт, припирается к стене, а последний втиснувшийся стоит прямо у двери. Когда лифт поднимается на указанный кем-то из пассажиров этаж, тот, кто зашел последним, должен выйти первым, Если кто-нибудь (из стоящих посередине пассажиров) захочет выйти из лифта раньше других, то все, кто находится между ним и дверью, должны выйти из лифта, выпустив его, а затем вернуться обратно.
|
|
|
Открытый конец стека называется вершиной стека, а действия, выполняемые с элементами стека, — операциями помещения (push) и выталкивания (pop) из стека. Для класса stack эти общепринятые термины остаются в силе.
Примечание: Класс stack из библиотеки STL не соответствует стекам памяти, используемым компиляторами и операционными системами, которые могут содержать объекты различных типов, хотя они работают сходным образом.
Очередь
Очередь — это еще одна распространенная в программировании структура данных. В этом случае элементы добавляются к очереди с одного конца, а вынимаются с другого. Приведем классическую аналогию. Вспомним стек. Его можно сравнить со стопкой тарелок на столе. При добавлении в стек тарелка ставится сверху всей стопки (помещение в стек), и взять тарелку из стопки (стека) можно тоже только сверху (выталкивание из стека), т.е. берется тарелка, которая была положена в стопку самой последней.
|
|
|
Очередь же можно сравнить с любой очередью людей, например при входе в театр. Вы занимаете очередь сзади, а покидаете ее спереди. Конечно, каждому из нас приходилось стоять предпоследним в какой-нибудь очереди (например, в магазине), когда вдруг начинает работать еще одна касса, к которой подбегает стоявший за вами, что скорее напоминает стек, чем очередь. Но в компьютерах такого не случается.
Подобно классу stack, класс queue реализован как класс оболочки контейнера. Контейнер должен поддерживать такие функции, как front(), back(), push_back() и pop_front().
Ассоциативные контейнеры
Тогда как последовательные контейнеры предназначены для последовательного и произвольного доступа к элементам с помощью индексов или итераторов, ассоциативные контейнеры разработаны для быстрого произвольного доступа к элементам с помощью ключей. Стандартная библиотека C++ предоставляет четыре ассоциативных контейнера: карту, мульти карту, множество и мультимножество.
Карта
Вектор можно сравнить с расширенной версией массива. Он имеет все характеристики массива и ряд дополнительных возможностей. К сожалению, вектор также страдает от одного из существенных недостатков массивов: он не предоставляет возможности для произвольного доступа к элементам с помощью ключа, а лишь использует для этого индекс или итератор. Ассоциативные контейнеры как раз обеспечивают быстрый произвольный доступ, основанный на ключевых значениях.
В листинге 19.10 для создания списка студентов, который мы рассматривали в листинге 19.8, используется карта.
Дата добавления: 2019-02-12; просмотров: 251; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!