Когда нельзя использовать обобщенные алгоритмы
Ассоциативные контейнеры (отображения и множества) поддерживают определенный порядок элементов для быстрого поиска и извлечения. Поэтому к ним не разрешается применять обобщенные алгоритмы, меняющие порядок, такие, как sort() и partition(). Если в ассоциативном контейнере требуется переставить элементы, то необходимо сначала скопировать их в последовательный контейнер, например в вектор или список.
Контейнер list (список) реализован в виде двусвязного списка: в каждом элементе, помимо собственно данных, хранятся два члена-указателя– на следующий и на предыдущий элементы. Основное преимущество списка – это эффективная вставка и удаление одного элемента или целого диапазона в произвольное место списка, а недостаток – невозможность произвольного доступа. Например, можно написать:
vector<string>::iterator vec_iter = vec.begin() + 7;
Такая форма вполне допустима и инициализирует vec_iter адресом восьмого элемента вектора, но запись
// ошибка: арифметические операции над итераторами
// не поддерживаются списком
list<string>::iterator list_iter = slist.begin() + 7;
некорректна, так как элементы списка не занимают непрерывную область памяти. Для того чтобы добраться до восьмого элемента, необходимо посетить все промежуточные.
Поскольку список не поддерживает произвольного доступа, то алгоритмы merge(), remove(), reverse(), sort() и unique() лучше к таким контейнерам не применять, хотя ни один из них явно не требует наличия соответствующего итератора. Вместо этого для списка определены специализированные версии названных операций в виде функций-членов, а также операция splice():
