cout << is_sorted(begin(v), end(v)) << '\n';
print(v);
9. Еще одна интересная функция —
std::partition
. Возможно, мы не хотим полностью сортировать список, поскольку достаточно поместить в начало те элементы, чье значение не превышает некий предел. Секционируем вектор, чтобы переместить все элементы, значение которых меньше 5
, в начало, и выведем результат на экран:
shuffle(begin(v), end(v), g);
partition(begin(v), end(v), [] (int i) { return i < 5; });
print(v);
10. Следующая функция, связанная с сортировкой, —
std::partial_sort
. Ее можно использовать для сортировки содержимого контейнера, но не в полной мере. Эта функция поместит N
самых маленьких элементов в начало контейнера в отсортированном виде. Остальная часть элементов останется во второй половине, они не будут отсортированы.
shuffle(begin(v), end(v), g);
auto middle (next(begin(v), int(v.size()) / 2));
partial_sort(begin(v), middle, end(v));
print(v);
11. Что, если мы хотим отсортировать структуру данных, не поддерживающую оператора сравнения? Определим такую структуру и создадим следующий вектор элементов:
struct mystruct {
int a;
int b;
};
vector mv {{5, 100}, {1, 50}, {-123, 1000},
{3, 70}, {-10, 20}};
12. Функция
std::sort
опционально принимает в качестве третьего аргумента функцию сравнения. Воспользуемся данным обстоятельством и передадим ей такую функцию. Для демонстрации того, что это возможно, мы будем сравнивать элементы на основе второго поля, b
. Таким образом, элементы отсортируются на основе поля mystruct::b
, а не поля mystruct::a
:
sort(begin(mv), end(mv),
[] (const mystruct &lhs, const mystruct &rhs) {
return lhs.b < rhs.b;
});
13. Последним шагом будет вывод на экран упорядоченного вектора, содержащего элементы типа
mystruct
.
for (const auto &[a, b] : mv) {
cout << "{" << a << ", " << b << "} ";
}
cout << '\n';
}
14. Скомпилируем и запустим программу.
Первое значение
1
получено от вызова функции std::is_sorted call
после инициализации упорядоченного вектора. Далее мы перемешали значения вектора и получили значение 0
после второго вызова функции is_sorted
. В третьей строке показаны все элементы вектора после перемешивания. Следующее значение 1
— это результат вызова функции is_sorted
после повторной сортировки с помощью алгоритма std::sort
.Далее мы снова перемешали вектор и секционировали его, задействовав алгоритм
std::partition
. Можно увидеть, что все элементы, чье значение не превышает 5
, находятся слева от значения 5
в векторе. Остальные элементы, чье значение превышает 5
, стоят справа. За исключением этого они выглядят упорядоченными.В предпоследней строке показан результат вызова алгоритма
std::partial_sort
. Все элементы в первой половине вектора выглядят отсортированными, а остальные — нет.В последней строке мы видим наш вектор, содержащий экземпляры типа
mystruct
. Они строго отсортированы по значению второго члена.
$ ./sorting_containers
1
0
7, 1, 4, 6, 8, 9, 5, 2, 3, 10,
1
1, 2, 3, 4, 5, 6, 7, 8, 9, 10,
1, 2, 4, 3, 5, 7, 8, 10, 9, 6,
1, 2, 3, 4, 5, 9, 8, 10, 7, 6,
{-10, 20} {1, 50} {3, 70} {5, 100} {-123, 1000}
Как это работает
Мы использовали разные алгоритмы, связанные с сортировкой (табл. 5.1).
Для объектов, не имеющих реализации оператора сравнения
<
, можно предоставить собственные функции сравнения. Этим функциям всегда следует иметь сигнатуру 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