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

 for_each(lstOne.begin(), // результаты (перед объединением списки должны

  lstOne.end(),           // быть отсортированы)

  strPrinter);

 list<int> intLst;

 intLst.push_back(0);

 intLst.push_back(1);

 intLst.push_back(2);

 intLst.push_back(3);

 intLst.push_back(4);

 // Удалить все значения больше 2

 intLst.remove_if(bind2nd(greater<int>(), 2));

 for_each(intLst.begin(), intLst.end(), intPrinter);

 // Или удалить все четные значения

 intLst.remove_if(even);

}

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

Объявление list не вызывает сложностей — просто укажите тип элементов, которые в нем будут храниться, и, опционально, класс распределителя памяти.

list<typename Value, // Тип элементов, хранящихся в списке

 typename Allocator = allocator<Value> > // Используемый распределитель

                                         // памяти

Параметр шаблона Value — это тип элементов, которые будут храниться в list. Это должен быть тип, который поддерживает конструктор копирования и присвоение. Allocator — это используемый класс распределителя памяти. По умолчанию используется стандартный распределитель (и в большинстве случаев его вполне достаточно).

Далее приведено типичное объявление list (см. пример 6.5).

list<string> lstOne;

После объявления списка поместите в него что-нибудь с помощью push_front или push_back, как здесь.

lstOne.push_back("Red"); // Добавление элементов в конец списка

lstOne.push_back("Green");

lstOne.push_back("Blue");

lstTwo.push_front("Orange"); // Добавление элементов в начало

lstTwo.push_front("Yellow");

lstTwo.push_front("Fuschia");

Помещение элементов в list занимает постоянное время, а не амортизированное постоянное время, как в случае с vector. Реализации list не требуется периодически изменять размер буфера, так что в них не будет возникать периодических падений производительности, как при использовании vector. list просто должен обновить набор указателей, и больше ничего.

Для удаления элементов из начала или конца list используйте pop_front или pop_back (без аргументов). Несмотря на их имя, методы «pop» не возвращают извлекаемый элемент, как это можно ожидать, исходя из обычной семантики стеков.

Обычно list выглядит так, как показано на рис. 6.2. Каждый узел содержит (по меньшей мере) три части: объект, в нем содержащийся, указатель на предыдущий узел и указатель на следующий узел. В оставшейся части рецепта я буду ссылаться на указатели на следующий и предыдущий узлы как next_ и prev_.

Рис. 6.2. Список с двунаправленными связями

Когда вы увидите, как реализован list, станет очевидно, почему некоторые операции имеют сложность, отличную от их сложности для vector. Добавление элемента в любое место list требует только изменения указателей next_ и prev_ предыдущего и следующего элементов. Приятным моментом в list является то, что при вставке и удалении элементов в помощью insert и erase устаревают значения только тех итераторов, которые указывают на затрагиваемый(е) объект(ы). Итераторы для других элементов не теряют актуальности.

Методы вставки и удаления — это insert и erase, insert в качестве первого аргумента принимает итератор, а в качестве второго — либо объект типа T, либо количество и затем объект типа T, либо начальный и конечный итераторы. Первый аргумент-итератор указывает на элемент, непосредственно перед которым должна произойти вставка. Перегрузки insert используются вот так.

list<string> strlst;

list<string>::iterator p;

// ...

string s = "Scion";

p = find(strLst.begin(), strLst.end(), // std::find из <algorithm>

 "Toyota");

strLst.insert(p, s);     // Вставить s сразу перед p

strLst.insert(p, 16, s); // Вставить 16 копий s непосредственно перед p

strLst insert(p, myOtherStrLst.begin(), // Вставить все, что содержится

 myOtherStrLst.end());                  // в myOtherStrLst, перед p

Удаление элементов аналогично.

p = find(strLst.begin(), strLst.end(), // std::find из <algorithm>

 "Toyota");

strLst1.erase(p); // Удаляем этот элемент

strLst2.erase(p, strLst.end()); // Удаляем от p до конца

strLst3.clear(); // Удаляем все элементы

В дополнение к методам стандартных контейнеров list предоставляет несколько своих. Первый — это splice.

splice делает то, что означает его имя: он объединяет два list в один. Вот как можно объединить lstTwo с lstOne из примера 6.5.

list<string>::iterator p = // Находим, куда вставить второй

 std::find(lstOne.begin(), // список

  lstOne.end(), "Green");

lstOne.splice(p, lstTwo); // Вставляем lstTwo непосредственно перед "Green"

p — это итератор, который указывает на элемент в lstOne. lstTwo вставляется в lstTwo непосредственно перед p. Как и в случае со вставкой, все, что здесь требуется сделать, — это изменить указатели next_ и prev_ соответствующих узлов, так что эта операция занимает постоянное время. После объединения lstTwo с lstOne первый очищается, и именно поэтому этот параметр не объявлен как const. Также можно вставить в lstOne один элемент или диапазон элементов из lstTwo. В обоих случаях элементы, объединяемые с другим списком, удаляются из первоначального.

Если списки отсортированы (list содержит свой собственный метод sort, std::sort с list не работает) и требуется объединить их в один, сохранив их порядок, то вместо splice используйте merge. merge объединяет два списка в один, и если два элемента оказываются одинаковыми, то в конечную версию попадает элемент из lstOne. Как и в случае со splice, список, переданный в качестве аргумента, по окончании объединения очищается.

Также list содержит несколько удобных операций для удаления элементов. Представьте, что вам требуется удалить все вхождения какого-либо элемента. Все, что для этого требуется сделать, это вызвать remove, передав такой аргумент, который при сравнении с элементами list будет давать (*p == item) != false, где p — это итератор list. remove вызывается вот так.

strLst.remove("Harry");

В результате из strLst будут удалены все элементы, у которых el == "Harry". Если требуется удалить элементы, которые удовлетворяют какому-либо предикату, такому как больше какого-либо значения, используйте remove_if.

bool inline even(int n) {

 return(n % 2 == 0);

}

list<int> intLst;

// Fill up intLst...

intLst.remove_if(even); // Удаляет все элементы, для которых even(*p)

                        // != false

Если предикаты более сложные, то попробуйте использовать какие-то из функторов из <functional>. Например, если требуется удалить элементы, которые больше определенного значения, используйте в remove_if объединение из greater (из <algorithm>) и bind2nd.

intLst.remove_if(std::bind2nd(std::greater<int>(), 2));

В результате этого из intLst будут удалены все значения, которые больше 2. Эта запись несколько необычна, но ничего сложного в ней нет. bind2nd принимает два аргумента — объект функции (назовем ее f) и значение (v) — и возвращает объект функции, который принимает один аргумент (arg) и вызывает f(arg, v). bind2nd — это простой способ делать подобные вещи без необходимости писать набор небольших функций.

list — это хорошая альтернатива вектору, когда требуется стандартный последовательный контейнер. Другое внутреннее представление list позволяет ему обеспечить другой уровень сложности многих стандартных операций с последовательностями и несколько дополнительных операций.

Рецепт 6.1.

6.6. Отображение строк на другие объекты

Имеются объекты, которые требуется сохранить в памяти, и вы хотите хранить их по ключам типа string. Требуется иметь возможность быстро добавлять, удалять и получать элементы (с, как максимум, логарифмической сложностью).