C++. Сборник рецептов

Когсуэлл Джефф

После удаления указателей следует явно очистить

vector

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

6.5. Хранение объектов в списке

Проблема

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

Решение

Для

хранения данных используйте

list

, объявленный в

<list>

.

list

предлагает более высокую производительность и большую гибкость при изменении последовательности в произвольных местах. Пример 6.5 показывает, как использовать

list

, а также демонстрирует некоторые из его уникальных операций.

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

#include <iostream>

#include <list>

#include <string>

#include <algorithm>

using namespace std;

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

template<typename T>

struct printer {

 void operator(const T& s) {

cout << s << '\n';

 }

};

bool inline even(int n) {

 return(n % 2 == 0);

}

printer<string> strPrinter;

printer<int> intPrinter;

int main {

 list<string> lstOne;

 list<string> 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<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

просто должен обновить набор указателей, и больше ничего.