В ассоциативных контейнерах erase возвращает void. При удалении одного элемента сложность имеет вид амортизированной константы, а при удалении диапазона — логарифмической зависимости плюс количество удаляемых элементов. Причина этого заключается в том, что ассоциативные контейнеры часто реализуются как сбалансированные деревья (например, красно-черное дерево).
erase удобен, но не интересен. Если требуется большая гибкость в выражении того, что требуется удалить, следует обратить внимание на стандартные алгоритмы (из <algorithm>). Рассмотрим такую строку из примера 7.2.
lstStr.erase(std::remove(lstStr.begin(), lstStr.end(), "cloudy"),
lstStr.end());
Обратите внимание, что я использую erase, но на этот раз по какой-то причине мне требуется удалить из list<string> все вхождения слова «cloudy», remove возвращает iterator, который передается в erase как начало удаляемого диапазона, a end передается в erase как конечная точка диапазона. В результате удаляются все объекты obj (вызывая их метод delete) из диапазона, для которого obj == "cloudy" равно истине. Но поведение этой строки может оказаться не совсем таким, как ожидается. Здесь мне требуется пояснить некоторую терминологию.
remove на самом деле ничего не удаляет. Он перемещает все, что не равно указанному значению, в начало последовательности и возвращает iterator, который ссылается на первый элемент, следующий за этими перемещенными элементами. Затем вы должны вызвать erase для контейнера, чтобы удалить объекты между [p, end), где p — это iterator, возвращенный remove.
remove также имеет несколько вариантов. Что, если требуется удалить элементы, которые удовлетворяют некоторому предикату, а не просто равны какому-то значению? Используйте remove_if. Например, представьте, что есть класс с именем Conn, который представляет какой-то тип соединений. Если это соединение простаивает больше определенного значения, его требуется удалить. Во-первых, создайте функтор, как здесь.
struct IdleConnFn :
public std::unary_function<const Conn, bool> { // Включите эту строку,
bool operator() (const Conn& c) const { // чтобы он работал с
if (с.getIdleTime() > TIMEOUT) { // другими объектами из
return(true); // <functional>
} else return(false);
}
} idle;
Затем вызовите remove_if с erase и передайте в него новый функтор, как здесь.
vec.erase(std::remove_if(vec.begin(), vec.end(), idle), vec.end());
Есть причина, по которой такие функторы следует наследовать от unary_function, unary_function определяет несколько typedef, используемых другими функторами из <functional>, и если они их не найдут, то другие функторы не скомпилируются. Например, если вы очень злы и хотите удалить все не задействованные в данный момент соединения, то в функторе проверки на простой можно использовать функтор not1.
vec.erase(std::remove_if(vec.begin(), vec.end(); std::not1(idle)),
vec.end());
Наконец, вам может потребоваться сохранить первоначальную последовательность (может, с помощью const) и скопировать результаты, кроме некоторых элементов, в новую последовательность. Это можно сделать с помощью remove_copy и remove_copy_if, которые работают аналогично remove и remove_if, за исключением того, что здесь также требуется передавать iterator вывода, в который будут записываться результирующие данные. Например, чтобы скопировать из одного списка в другой строку, сделайте так.
std::remove_copy(lstStr.begin(), lstStr.end(), lstStr2, "cloudy");
При использовании remove_copy или любого стандартного алгоритма, записывающего в выходной диапазон, следует помнить, что выходной диапазон должен уже быть достаточно большим, чтобы в нем поместились элементы, которые туда будут записываться.
erase и remove (и связанные с ними алгоритмы) предлагают удобный способ удалять определенные элементы последовательностей. Они предоставляют простую альтернативу самостоятельному перебору и поиску нужных элементов с последующим их удалением по одному.
Рецепты 6.2 и 7.1.
7.3. Случайное перемешивание данных
Имеется последовательность данных и требуется перемешать их так, чтобы они были расположены в случайном порядке.
Используйте стандартный алгоритм random_shuffle, определенный в <algorithm>. random_shuffle принимает два итератора произвольного доступа и (необязательно) функтор генератора случайных чисел и реорганизует случайным образом элементы заданного диапазона. Пример 7.3 показывает, как это делается.
Пример 7.3. Случайное перемешивание последовательностей
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
#include "utils.h" // Для printContainer(): см. 7.10
using namespace std;
int main() {
vector<int> v;
back_insert_iterator<std::vector<int> > p = back_inserter(v);
for (int i = 0; i < 10; ++i) *p = i;
printContainer(v, true);
random_shuffle(v.begin(), v.end());
printContainer(v, true);
}
Вывод должен выглядеть примерно так.
-----
0123456789
-----
8192057346
random_shuffle очень прост в использовании. Дайте ему диапазон, и он перемешает этот диапазон случайным образом. Имеется две версии, и их прототипы выглядят так.
void random_shuffle(RndIter first, RndIter last);
void random_shuffle(RndIter first, RndIter last, RandFunc& rand);
В первой версии используется зависящая от реализации функция генерации случайных чисел, которой должно быть достаточно для большинства задач. Если ее недостаточно — например, требуется неоднородное распределение, такое, как гауссово — то можно написать собственную функцию, которую можно передать во вторую версию.
Этот генератор случайных чисел должен быть функтором с единственным аргументом, возвращающим единственное значение, и оба они должны преобразовываться в iterator_traits<RndIter>::difference_type. В большинстве случаев для этого подойдет целое число. Например, вот мой псевдогенератор случайных чисел.
struct RanNumGenFtor {
size_t operator()(size_t n) const {
return(rand() % n);
}
} rnd;
random_shuffle(v.begin(), vend(), rnd);