class="code">// возвращает итератор на максимальный элемент в диапазоне [first:last]
{
Iterator high = first;
for (Iterator p = first; p!=last; ++p)
if (*high<*p) high = p;
return high;
}
Обратите внимание на то, что мы исключили локальную переменную h, которую до сих пор использовали для хранения максимального элемента. Если вам неизвестен реальный тип элементов последовательности, то инициализация –1 выглядит совершенно произвольной и странной. Она действительно является произвольной и странной! Кроме того, такая инициализация представляет собой ошибку: в нашем примере число 1 оправдывает себя только потому, что отрицательных скоростей не бывает. Мы знаем, что “магические константы”, такие как –1, препятствуют сопровождению кода (см. разделы 4.3.1, 7.6.1, 10.11.1 и др.). Здесь мы видим, что такие константы могут снизить полезность функции и свидетельствовать о неполноте решения; иначе говоря, “магические константы” могут быть — и часто бывают — свидетельством небрежности.
Обобщенную функцию high() можно использовать для любых типов элементов, которые можно сравнивать с помощью операции <. Например, мы могли бы использовать функцию high() для поиска лексикографически последней строки в контейнере vector<string> (см. упр. 7).
Шаблонную функцию high() можно применять к любой последовательности, определенной парой итераторов. Например, мы можем точно воспроизвести нашу программу.
double* get_from_jack(int* count); // Джек вводит числа типа double
// в массив и возвращает количество
// элементов в переменной *count
vector<double>* get_from_jill(); // Джилл заполняет вектор
void fct()
{
int jack_count = 0;
double* jack_data = get_from_jack(&jack_count);
vector<double>* jill_data = get_from_jill();
double* jack_high = high(jack_data,jack_data+jack_count);
vector<double>& v = *jill_data;
double* jill_high = high(&v[0],&v[0]+v.size());
cout << "Максимум Джилл " << *jill_high
<< "; Максимум Джека" << *jack_high;
// ...
delete[] jack_data;
delete jill_data;
}
Здесь в двух вызовах функции high() шаблонным типом аргумента является тип double*. Это ничем не отличается от нашего предыдущего решения. Точнее, выполняемые коды этих программ ничем не отличаются друг от друга, хотя степень общности этих кодов разнится существенно. Шаблонная версия функции high() может применяться к любому виду последовательности, определенной парой итераторов. Прежде чем углубляться в принципы библиотеки STL и полезные стандартные алгоритмы, реализующие эти принципы, и для того чтобы избежать создания сложных кодов, рассмотрим несколько способов хранения коллекций данных.
ПОПРОБУЙТЕ
В этой программе снова сделана серьезная ошибка. Найдите ее, исправьте и предложите универсальный способ устранения таких проблем.
20.4. Связанные списки
Еще раз рассмотрим графическое представление последовательности.
Сравним его с визуализацией вектора, хранящегося в памяти.
По существу, индекс 0 означает тот же элемент, что и итератор v.begin(), а функция v.size() идентифицирует элемент, следующий за последним, который можно также указать с помощью итератора v.end().
Элементы в векторе располагаются в памяти последовательно. Понятие последовательности в библиотеки STL этого не требует. Это позволяет многим алгоритмам вставлять элементы между существующими элементами без их перемещения. Графическое представление абстрактного понятия последовательности предполагает возможность вставки (и удаления) элементов без перемещения остальных элементов. Понятие итераторов в библиотеки STL поддерживает эту концепцию.
Структуру данных, которая точнее всех соответствует диаграмме последовательности в библиотеке STL, называют связанным списком (linked list). Стрелки в абстрактной модели обычно реализуются как указатели. Элемент связанного списка — это часть узла, состоящего из элемента и одного или нескольких указателей. Связанный список, в котором узел содержит только один указатель (на следующий узел), называют односвязным списком (singly-linked list), а список, в которой узел ссылается как на предыдущий, так и на следующий узлы, — двусвязным списком (doubly-linked list). Мы схематично рассмотрим реализацию двухсвязных списков, которые в стандартной библиотеке языка С++ имеют имя list. Графически список можно изобразить следующим образом.
В виде кода он представляется так:
template<class Elem> struct Link {
Link* prev; // предыдущий узел
Link* succ; // следующий узел
Elem val; // значение
};
template<class Elem> struct list {
Link<Elem>* first;
Link<Elem>* last; // узел, находящийся за последним узлом
};
Схема класса Link приведена ниже.
Существует много способов реализации и представления связанных списков. Описание списка, реализованного в стандартной библиотеке, приведено в приложении Б. Здесь мы лишь кратко перечислим основные свойства списка — возможность вставлять и удалять элементы, не трогая существующие элементы, а также покажем, как перемещаться по списку с помощью итератора, и приведем пример его использования.
Мы настоятельно рекомендуем вам, размышляя о списках, рисовать диаграммы, иллюстрирующие операции, которые вы рассматриваете. Манипуляции связанным списком — это тема, в которой один рисунок может заменить тысячу слов.
20.4.1. Операции над списками
Какие операции необходимы для списка?
• Операции, эквивалентные операциям над векторами (создание, определение размера и т.д.), за исключением индексирования.
• Вставка (добавление элемента) и стирание (удаление элемента).
• Нечто, что можно использовать для ссылки на элементы и перемещения по списку: итератор.
В библиотеке STL тип итератора является членом своего класса, поэтому и мы поступим так же.
template<class Elem> class list {
// детали представления и реализации
public:
class iterator; // тип — член класса :iterator
iterator begin(); // итератор, ссылающийся на первый элемент
iterator end( ); // итератор, ссылающийся на последний элемент
iterator insert(iterator p, const Elem& v); // вставка v
// в список после элемента,
// на который установлен итератор p
iterator erase(iterator p); // удаление из списка элемента,
// на который установлен итератор p
void push_back(const Elem& v); // вставка v в конец списка
void push_front(const Elem& v); // вставка v в начало списка
void pop_front(); // удаление первого элемента
void pop_back(); // удаление последнего элемента
Elem& front(); // первый элемент
Elem& back(); // последний элемент
// ...
}
Так же как наш класс
