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

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

"Toyota");

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

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

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

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

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

list::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 intLst;

// Fill up intLst...

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

// != false

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

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

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

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

Рецепт 6.1.

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

Для отображения ключей ( string) на значения (любой тип, который подчиняется семантике значений) используйте стандартный контейнер map, объявленный в . Пример 6.6 показывает, как это делается.

Пример 6.6. Создание отображения строк

#include

#include

#include

using namespace std;

int main() {

map strMap;

strMap["Monday"] = "Montag";

strMap["Tuesday"] = "Dienstag";

strMap["Wednesday"] = "Mittwoch";

strMap["Thursday"] = "Donnerstag";

strMap["Friday"] = "Freitag";

strMap["Saturday"] = "Samstag";

// strMap.insert(make_pair("Sunday", "Sonntag"));

strMap.insert(pair("Sunday", "Sonntag"));

for(map::iterator p = strMap.begin();

p != strMap.end(); ++p) {

cout << "English: " << p->first

<< German: " << p->second << endl;

}

cout << endl;

strMap.erase(strMap.find("Tuesday"));

for (map::iterator p = strMap.begin();

p ! = strMap.end(); ++p) {

cout << "English: " << p->first

<< ", German: " << p->second << endl;

}

}

map— это ассоциативный контейнер, который отображает ключи на значения, предоставляет логарифмическую сложность вставки и поиска и постоянную сложность удаления одного элемента. Обычно разработчики используют отображение для хранения объектов по их ключам типа string. Именно это делает пример 6.6. В этом случае отображаемый тип является строкой, но он может быть почти чем угодно.

Отображение объявляется вот так.

map

typename Value, // Тип значения

typename LessThanFun = std::less, // Функция/функтор,

// используемые для сортировки

typename Alloc = std::allocator > // Распределитель памяти

Keyи Value— это типы ключа и связанного значения, которые хранятся в отображении. LessThanFun— это функция или функтор, который принимает два аргумента и возвращает истину, если первый меньше, чем второй. По умолчанию используется стандартный функтор less. Alloc— это распределитель памяти, и по умолчанию используется стандартный.

Использование mapдовольно просто. Объявите тип ключа и значения вот так.

map strMan;

В результате будет создан map, в котором и ключ, и значение имеют тип string. С помощью operator[]поместите в отображение объекты, что интуитивно и легко читаемо.

strMap["Monday"] = Montag";

strMap["Tuesday"] = "Dienstag";

strMap["Wednesday"] = "Mittwoch"; // ...

В результате в mapбудут вставлены элементы с индексом (например, "Monday") в качестве ключа и правым операндом в качестве значения. Они хранятся в порядке, определяемом параметром шаблона LessThanFun, и если он не указан, то mapиспользует std::less.

Чтобы получить значения из map, используйте operator[]в правой части присвоения, как здесь.