Д. Стефенс - C++. Сборник рецептов

Или можно представить все в виде диаграммы Венна. Она представлена на рис. 7.1.

Рис. 7.1. Категории итераторов

Большая часть стандартных контейнеров поддерживает как минимум двунаправленный iterator, некоторые ( vectorи deque) предоставляют iteratorпроизвольного доступа. Категория итератора, поддерживаемая контейнером, определяется стандартом.

В большинстве случае вы будете использовать iteratorдля простейших задач: поиск элемента и его удаление или что-либо подобное. Для этой цели требуется только однонаправленный iterator, который доступен для всех контейнеров. Но когда потребуется написать нетривиальный алгоритм или использовать алгоритм из стандартной библиотеки, часто потребуется нечто большее, чем простой однонаправленный iterator. Но как определить, что вам требуется? Здесь на сцену выходят категории итераторов.

Различные категории итераторов позволяют стандартным (и нестандартным) алгоритмам указать диапазон требуемой функциональности. Обычно стандартные алгоритмы работают с диапазонами, указываемыми с помощью итераторов, а не с целыми контейнерами. Объявление стандартного алгоритма говорит, какую категорию iteratorон ожидает». Например, std::sortтребует итераторов произвольного доступа, так как ему требуется за постоянное время ссылаться на несмежные элементы. Таким образом, объявление sortвыглядит вот так.

template

void sort(RandomAccessIterator first, RandomAccessIterator last);

По имени типа итератора можно определить, что он ожидает итератор произвольного доступа. Если попробовать откомпилировать sortдля категории итератора, отличной от произвольного доступа, то она завершится ошибкой, так как младшие категории iteratorне реализуют операций, аналогичных арифметике с указателями.

Категория итератора, предоставляемая определенным контейнером и требуемая определенным стандартным алгоритмом, — это то, что определяет, какой алгоритм с каким контейнером может работать. Многие из стандартных алгоритмов описаны далее в этой главе. Таблица 7.1 показывает сокращения, используемые в остальной части главы для указания типов итераторов, принимаемых алгоритмами в качестве аргументов.

Этот рецепт описывал итераторы, как они используются для контейнеров. Но шаблон итераторов используется не только для контейнеров, и, таким образом, имеются другие типы итераторов. Имеются потоковые итераторы, итераторы буферов потоков и итераторы хранения в необработанном виде, но они здесь не описываются.

Глава 6.

Требуется удалить объекты из контейнера.

Для удаления одного или диапазона элементов используйте метод контейнера erase или один из стандартных алгоритмов. Пример 7.2 показывает пару различных способов удаления элементов из последовательностей.

Пример 7.2. Удаление элементов из контейнера

#include

#include

#include

#include

#include

#include "utils.h" // Для printContainer(): см. 7.10

using namespace std;

int main() {

list lstStr;

lstStr.push_back("On");

lstStr.push_back("a");

lstStr.push_back("cloudy");

lstStr.push_back("cloudy");

lstStr.push_back("day");

list::iterator p;

// Найти то что требуется, с помощью find

p = find(lstStr.begin(), lstStr.end(), "day");

p = lstStr.erase(p); // Теперь p указывает на последний элемент

// Или для удаления всех вхождений чего-либо используйте remove

lstStr.erase(remove(lstStr.begin(), lstStr.end(), "cloudy"),

listStr.end());

printContainer(lstStr); // См. 7.10

}

Для удаления одного или нескольких элементов из контейнера используйте метод erase. Все контейнеры содержат два перегруженных erase: один принимает единственный аргумент iterator, который указывает на элемент, который требуется удалить, а другой принимает два аргумента, которые представляют диапазон удаляемых элементов. Чтобы удалить один элемент, получите iterator, указывающий на этот элемент, и передайте этот iteratorв erase, как в примере 7.2.

p = find(lstStr.begin(), lstStr.end(), "day");

p = lstStr.erase(p);

В результате объект, на который указывает p, будет удален, для чего будет вызван его деструктор, а после этого оставшиеся элементы будут реорганизованы. Реорганизация зависит от типа контейнера, и, следовательно, сложность этой операции от контейнера к контейнеру будет различаться. Сигнатура и поведение при использовании последовательного контейнера и ассоциативного контейнера также будут различаться.