C++17 STL Стандартная библиотека шаблонов

Для объектов, не имеющих реализации оператора сравнения <, можно предоставить собственные функции сравнения. Этим функциям всегда следует иметь сигнатуру 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

#include

#include

#include

using namespace std;

2. Короткая вспомогательная функция print выведет на экран содержимое вектора:

void print(const vector &v)

{

  copy(begin(v), end(v), ostream_iterator{cout, ", "});

  cout << '\n';

}

3. Начнем с примера вектора, содержащего некие простые целочисленные значения. Мы также выведем его на экран, чтобы увидеть изменения, которые внесет наша функция.

int main()

{

  vector 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 v2; vector v3;