имеющих реализации оператора сравнения <, можно предоставить собственные функции сравнения. Этим функциям всегда следует иметь сигнатуру bool имя_функции(const T &lhs, const T &rhs), и они не должны вызывать побочные эффекты во время выполнения.
Существуют и другие алгоритмы, такие как std::stable_sort, которые сортируют элементы, но сохраняют порядок элементов с одинаковым ключом сортировки, и std::stable_partition.
Алгоритм std::sort имеет разные реализации. В зависимости от природы аргументов итератора его можно реализовать как сортировку методом выбора, вставки или слияния или полностью оптимизировать для небольшого диапазона элементов. С точки зрения пользователя нас это, как правило, не волнует.
Удаляем конкретные элементы из контейнеров
Копирование, преобразование и фильтрация, возможно, наиболее распространенные операции, которые можно выполнить с диапазоном данных. В этом разделе мы сконцентрируемся на фильтрации элементов.
Фильтрация элементов из структур данных (или простое удаление конкретных элементов) работает по-разному для разных структур данных. В связанных списках (например, std::list) элемент может быть удален, если вы заставите его предшественника указывать на элемент, стоящий после удаляемого. После такого удаления узла из цепи ссылок этот узел можно вернуть распределителю ресурсов. В непрерывных структурах данных (std::vector, std::array и в некоторой степени std::deque) элементы можно удалить, только перезаписав их другими элементами. Если позиция элемента помечается как удаляемая, то все элементы, стоящие после него, должны сдвинуться вперед, чтобы заполнить пропуск. Кажется, возни для простой операции слишком много, но, например, просто удалить пробельные символы из строки можно с помощью относительно небольшого количества строк кода.
Нужно удалить элемент, не оглядываясь на тип нашей структуры данных. Здесь помогут алгоритмы std::remove и std::remove_if.
Как это делается
В этом примере мы преобразуем содержимое вектора, удалив из него элементы разными способами.
1. Импортируем все необходимые заголовочные файлы и объявим об использовании пространства имен std:
#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
2. Короткая вспомогательная функция print выведет на экран содержимое вектора:
void print(const vector<int> &v)
{
copy(begin(v), end(v), ostream_iterator<int>{cout, ", "});
cout << 'n';
}
3. Начнем с примера вектора, содержащего некие простые целочисленные значения. Мы также выведем его на экран, чтобы увидеть изменения, которые внесет наша функция.
int main()
{
vector<int> v {1, 2, 3, 4, 5, 6};
print(v);
4. Теперь удалим из вектора все элементы со значением 2. Функция std::remove переместит другие элементы так, что единственное значение 2, присутствующее в векторе, испарится. Поскольку длина реального содержимого вектора сократилась после удаления элементов, функция std::remove вернет итератор, указывающий на новую конечную позицию. Элементы, стоящие между новым и старым конечными итераторами, считаются мусором, так что дадим вектору команду удалить их. Окружаем две строки, связанные с удалением этих элементов, новой областью видимости, поскольку итератор new_end в дальнейшем станет некорректным, вследствие чего может мгновенно выйти из области видимости:
{
const auto new_end (remove(begin(v), end(v), 2));
v.erase(new_end, end(v));
}
print(v);
5. Теперь удалим все нечетные числа. Для этого реализуем предикат, который сообщит, является ли число нечетным, и передадим его в функцию std::remove_if, принимающую подобные предикаты:
{
auto odd_number ([](int i) { return i % 2 != 0; });
const auto new_end (
remove_if(begin(v), end(v), odd_number));
v.erase(new_end, end(v));
}
print(v);
6. Далее поработаем с алгоритмом std::replace. Воспользуемся им, чтобы переписать все значения 4 значениями 123. Функция std::replace существует и в форме std::replace_if, которая также принимает функции-предикаты.
replace(begin(v), end(v), 4, 123);
print(v);
7. Заполним вектор совершенно новыми значениями и создадим два новых пустых вектора, чтобы провести еще один эксперимент:
v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> v2; vector<int> v3;
8. Далее снова реализуем предикат для нечетных чисел и еще одну функцию-предикат, которая решает прямо противоположную задачу: сообщает, является ли заданное число четным:
auto odd_number ([](int i) { return i % 2 != 0; });
auto even_number ([](int i) { return i % 2 == 0; });
9. Следующие две строки делают одно и то же: копируют четные значения в векторы v2 и v3. В первой строке это делается с помощью алгоритма std::remove_copy_if, копирующего все из исходного контейнера в другой контейнер, который не соответствует ограничению, налагаемому предикатом. В другой строке используется алгоритм std::copy_if, который копирует все значения, удовлетворяющие ограничению, налагаемому предикатом:
remove_copy_if(begin(v), end(v),
back_inserter(v2), odd_number);
copy_if(begin(v), end(v),
back_inserter(v3), even_number);
10. Вывод на экран двух векторов должен дать одинаковый результат:
print(v2);
print(v3);
}
11. Скомпилируем и запустим программу. В первой строке показан вектор после инициализации. Во второй — вектор, из которого мы удалили все значения 2. В следующей строке представлен результат удаления всех нечетных чисел. Перед четвертой строкой мы заменили все значения 4 на значения 123.
В последних двух строках показываются векторы v2 и v3:
$ ./removing_items_from_containers
1, 2, 3, 4, 5, 6,
1, 3, 4, 5, 6,
4, 6,
123, 6,
2, 4, 6, 8, 10,
2, 4, 6, 8, 10,
Как это работает
Мы использовали различные алгоритмы, связанные с фильтрацией данных (табл. 5.2).
Для каждого из перечисленных алгоритмов существует версия *_if, принимающая вместо значения функцию-предикат, которая затем выводит, какие значения будут удалены или заменены.
Преобразуем содержимое контейнеров
Если std::copy является самым простым алгоритмом STL для работы с диапазонами данных, то std::transform — второй по сложности алгоритм STL. Как и copy, он копирует элементы из одного диапазона данных в другой, но дополнительно принимает функцию преобразования. Она может изменить значение выходного типа до того, как это значение окажется в выходном диапазоне. Более того, данная функция может создать значение совершенно другого типа, что может быть
