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

vector vec;

Здесь важно запомнить, что vectorхранит значения , не обращая внимания на то, что они означают. Следовательно, он не знает, что для указателей перед их удалением следует использовать delete. Если выделить память, затем поместить указатели в память vector, то по окончании работы следует самостоятельно удалить память. Не дайте ввести себя в заблуждение термину «контейнер», думая, что если в vectorсохранить указатель, то это подразумевает владение им.

После удаления указателей следует явно очистить vector— по той же причине, по которой следует присваивать переменным-указателям по окончании работы с ними значение NULL. Это предотвратит ошибочное повторное удаление.

Требуется хранить элементы в виде последовательности, но vector не соответствует всем требованиям. В частности, требуется иметь возможность эффективно добавлять и удалять элементы в середине последовательности, а не только в ее конце.

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

Пример 6.5. Использование list

#include

#include

#include

#include

using namespace std;

// Простая функция для печати

template

struct printer {

void operator()(const T& s) {

cout << s << '\n';

}

};

bool inline even(int n) {

return(n % 2 == 0);

}

printer strPrinter;

printer intPrinter;

int main() {

list lstOne;

list lstTwo;

lstOne.push_back("Red");

lstOne.push_back("Green");

lstOne.push_back("Blue");

lstTwo.push_front("Orange");

lstTwo.push_front("Yellow");

lstTwo.push_front("Fuschia");

for_each(lstOne.begin(), // Напечатать каждый элемент списка,

lstOne.end(), // используя пользовательскую функцию печати

strPrinter);

lstOne.sort(); // list содержит методы для сортировки

lstTwo.sort();

lstOne.merge(lstTwo); // Объединить два списка и напечатать

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

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

strPrinter);

list 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(), 2));

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

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

intLst.remove_if(even);

}

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

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

list

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

// памяти

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

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

list 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 strlst;

list::iterator p;

// ...

string s = "Scion";

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

"Toyota");

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

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

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

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

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