Скотт Мейерс - Эффективное использование STL

Второй принципиальный аргумент заключается в том, что практически все алгоритмы STL (кроме самых элементарных) основаны на теоретических разработках, более сложных — а иногда гораздо более сложных, — нежели те, которые может предложить средний программист C++. Превзойти sortи его сородичей (см. совет 31) по эффективности практически невозможно; столь же эффективны алгоритмы поиска в сортированных интервалах (см. советы 34 и 45). Даже повседневные задачи вроде удаления объектов из блоковых контейнеров более эффективно решаются при помощи идиомы erase-remove, чем при помощи самостоятельно запрограммированных циклов (см. совет 9).

Если соображений эффективности недостаточно, существует и другой принципиальный фактор — правильность работы программы. В частности, при самостоятельном программировании циклов приходится следить за тем, чтобы итераторы (1) были действительными и (2) указывали на те элементы, на которые они должны указывать. Предположим, у нас имеется массив (возможно, из-за использования унаследованного интерфейса с языком C — см. совет 16), и вы хотите взять каждый элемент массива, прибавить к нему 41 и вставить в начало контейнера deque. При самостоятельном программировании цикла примерная реализация выглядит приблизительно так (следующий фрагмент представляет собой видоизмененный пример из совета 16):

// Функция получает указатель на массив.

// содержащий не более arraySize чисел типа double,

// и записывает в него данные.

// Возвращается количество записанных чисел.

size_t fillArray(double *pArray, size_t arraySize);

double data[maxNumDoubles]; // Определение локального массива

deque d; // Создать контейнер deque

… // и заполнить его данными

size_t numDoubles = fillArray(data.maxNumDoubles); // Получение данных от функции

for (size_t i=0; i < numDoubles; ++i) { // Для каждого индекса i в data

d.insert(d.begin(), data[i]+41); // вставить в начало d значение

} // data[i]+41.

//Программа содержит ошибку!

Вообще говоря, этот пример работает — если вас устраивает, что вновь вставленные элементы следуют в порядке, обратном порядку соответствующих элементов data. Вставка производится в позиции d.begin(), поэтому последний вставленный элемент попадает в начало контейнера!

Если изменение порядка не было предусмотрено (признайтесь, ведь не было!), проблему можно решить следующим образом:

deque::iterator insertLocaton = d.begin();// Сохранить итератор

// для начальной

// позиции d

for (size_t = 0; i < numDoubles; ++i) { // Вставить значение data[i]+41

d.insert( insertLocation++, data[i]+41); // в позиции insertLocation

} // и увеличить insertLocation.

// Программа также содержит ошибку!

На первый взгляд кажется, что этот фрагмент решает сразу две проблемы — программа не только наращивает итератор, задающий позицию вставки, но и избавляется от необходимости заново вычислять beginпри каждой итерации; тем самым решается второстепенная проблема повторяющихся вычислений, о которой говорилось выше. К сожалению, вместо этих двух проблем возникает третья — программа вообще перестает работать. При каждом вызове deque::insertвсе итераторы deque, включая insertLocation, становятся недействительными, поэтому второй и все последующие вызовы insertприводят к непредсказуемым последствиям.

После обнаружения этой проблемы (возможно, при помощи отладочного режима STL — см. совет 50) приходит в голову следующее решение:

deque::iterator insertLocation =

d.begin(); // См. ранее

for (size_t i = 0; i < numDoubles; ++i) { // Программа обновляет

insertLocation = // итератор insertLocation

d.insert( insertLocaton, data[i]+41); // при каждом вызове insert

++insertLocation; // и увеличивает его.

}

Программа делает именно то, что требовалось, но подумайте, как много времени понадобилось, чтобы прийти к верному решению! А теперь сравните со следующим вызовом transform:

transform(data, data+numDoubles, // Копирование всех элементов

inserter(d, d.begin()), // из data в начало d

bind2nd(plus(), 41)); // с прибавлением 41

Возможно, вам потребуется пара минут на анализ конструкции bnd2nd(plus(), 41), но после этого все хлопоты с итераторами сводятся к простому заданию начала и конца исходного интервала и вызову inserterпри определении начала приемного интервала (см. совет 30). На практике итераторы исходного и приемного интервала обычно вычисляются относительно просто — во всяком случае, это значительно проще, чем диагностика случайного появления недействительных итераторов в теле цикла.