114 стандартных алгоритмов C++. Введение

Добро пожаловать в новую серию статей о стандартных алгоритмах C++. Стандартные алгоритмы предлагают безопасные и оптимизированные строительные блоки, которые могут заменить удивительное количество пользовательского кода.

Сегодня мы рассмотрим основы алгоритмов, объясним концепцию итераторов, немного поговорим об истории и о том, что, скорее всего, появится в C++23, и, наконец, рассмотрим алгоритмы for_each и swap.

Стандартные алгоритмы

Вы можете критиковать стандартную библиотеку C++ за отсутствие функциональности. Однако, когда дело доходит до обработки данных и чисел, стандартная библиотека C++ предоставляет универсальный набор алгоритмов. Поэтому, если вы разработчик C++, вы обязаны знать, какие средства доступны в ней.

Итераторы: уровень взаимодействия

В основе, которая находится между структурами данных C++ и алгоритмами, лежат итераторы. Итераторы абстрагируются от деталей обхода конкретной структуры данных, фиксируя поведенческие ограничения, которые налагает структура данных.

Например, массив (например, std::vector) допускает произвольный доступ, что означает, что мы можем переходить от одного элемента к другому за постоянное время. С другой стороны, связанный список (например, std::list) позволяет нам переходить за постоянное время только к следующему и предыдущему элементам, а перемещение на расстояние n требует n операций (линейная сложность).

C++ распознает следующие категории итераторов:

• итератор ввода (input iterator): движение вперед, чтение, один проход;
• однонаправленный итератор (forward iterator): движение вперед, чтение;
• двунаправленный итератор (bidirectional iterator): однонаправленный итератор + движение назад;
• итератор произвольного доступа (random access iterator): двунаправленный итератор + движение вперед и назад на любое целое число, вычисление расстояния между двумя итераторами;
• непрерывный итератор (contiguous iterator): произвольный доступ + хранение элементов непрерывно;
• итератор вывода (output iterator): движение вперед, запись, один проход.

{
  std::vector<int> vec{1,2,3,4,5,6};
  auto it = vec.begin();
  it += 5; // *it == 6
}
{
    std::list<int> lst{1,2,3,4,5,6};
    auto it = lst.begin();
    // it += 5; не компилируется
    std::advance(it, 5); // линейное движение вперед, *it == 6
}

Эта категоризация позволяет алгоритмам указывать требуемый тип итератора либо явно (с использованием концептов C++20), либо неявно, используя операции, поддерживаемые определенным типом итераторов.

Например, для std::sort требуются итераторы произвольного доступа, поскольку необходимо эффективно вычислять расстояние между двумя итераторами. Поэтому следующий код не будет компилироваться (поскольку std::list предоставляет двунаправленные итераторы):

std::list<int> data = { 9, 1, 8, 2, 7, 3};
std::sort(data.begin(), data.end()); // не скомпилируется

Диапазоны (ranges)

В то время как C++20 формализовал понятие диапазона, это понятие присутствовало в C++ с самого начала. Ожидается, что каждый контейнер будет предоставлять доступ к двум итераторам, begin и end. Семантика здесь [begin,end), то есть begin – это итератор для первого элемента, end – это итератор, следующий за последним элементом.

std::vector<int> v{1,2,3,4,5,6};
for (auto it = v.begin(); it != v.end(); it++) {
    std::cout << *it << "\n";
}

Диапазоны (ranges) можно классифицировать с помощью тех же категорий итераторов. В данной серии статей мы будем использовать номенклатуру диапазонов вместо итераторов (например, диапазон ввода, однонаправленный диапазон, двунаправленный диапазон и т. д.).

Немного истории

Из предыдущих разделов вы могли уже предположить, что C++20 представляет собой важную веху в истории алгоритмов. И это происходит с введением диапазонов и ленивых представлений. Кроме того, несколько других стандартов C++ внесли существенные изменения, затронувшие стандартные алгоритмы.

• С++11 представил лямбда-выражения;
• C++17 представил параллельные алгоритмы;
• C++20 представил диапазоны и ленивые представления;
• ожидается, что C++23 представит поддержку реализованных пользователем представлений и, возможно, графовых алгоритмов.

for_each, for_each_n

Хватит теории. Давайте поговорим о конкретных алгоритмах, и начнем мы с самого простого, for_each и for_each_n.

Поскольку в C++11 появился цикл на основе диапазона, for_each стал менее актуальным алгоритмом. Тем не менее, еще есть пара ситуаций, когда for_each предлагает множество возможностей.

Параллельная версия, вероятно, самый простой параллельный функционал в C++. Если всё, что вам нужно, это выполнить дорогостоящую операцию для каждого элемента изолированно, параллельный for_each – идеальное решение:

std::vector<int> data = get_data();
std::for_each(std::execution::par_unseq, 
    data.begin(), data.end(),
    [](int e) { /* какие-то дорогостоящие вычисления */ });

Обратите внимание, что если операции не полностью изолированы, внутри лямбды вам потребуется дополнительная синхронизация.

Версия для диапазона может предложить более краткий код, если всё, что вам нужно, это спроецировать элемент, а затем отправить результат в другую функцию. Здесь у нас показан одинаковый код, выраженный двумя способами: с помощью for_each и с помощью цикла на основе диапазона:

struct Elem {
    double value() { return 10.2; }
};

void some_function(double);

int main() {
    std::vector<Elem> data(10, Elem{});
    
    std::ranges::for_each(data, some_function, &Elem::value);

    for(auto& e: data) {
        some_function(e.value());
    }
}

В версии с ranges (строка 10) первый параметр – это диапазон, второй параметр – это функция, которую мы хотим вызвать для каждого элемента, а третий – проекция. В этом случае мы используем указатель на член. Если вы хотите углубиться в детали, у меня есть отдельная статья о диапазонах в C++20.

В то время как for_each работает со всем диапазоном, т.е. с интервалом [begin, end), for_each_n работает с диапазоном [first, first+n). Важно отметить, что поскольку этот алгоритм даже не имеет доступа к конечному итератору исходного диапазона, он не выполняет проверки выхода за границы, и вызывающий несет ответственность за обеспечение того, чтобы диапазон [first,first+n) являлся допустимым.

Для демонстрации давайте посмотрим на фрагмент кода, который оценивает квалификационный раунд в турнире. Мы хотим пригласить на основной турнир лучших игроков, а затем опубликовать окончательный счет онлайн, разбитый по 100 записей:

struct Player {
    std::string display_name;
    std::string contact_email;
    uint32_t score;
};

std::vector<Player> get_ranking();
void send_invitation_to_main_tournament(const Player& player);
void store_final_score(uint32_t page, const std::string& name, uint32_t score);

inline constexpr const ssize_t MAIN_TOURNAMENT_SEATS = 10;
inline constexpr const ssize_t PAGE_SCORE_SIZE = 100;

int main() {
    std::vector<Player> final_ranking = get_ranking();
    std::ranges::sort(final_ranking, std::greater<>(), &Player::score);

    std::for_each_n(std::execution::par_unseq, 
        final_ranking.begin(), std::min(MAIN_TOURNAMENT_SEATS, final_ranking.size()), 
        send_invitation_to_main_tournament);
    
    auto it = final_ranking.begin();
    uint32_t page = 0;
    while (it != final_ranking.end()) {
        ssize_t cnt = std::min(PAGE_SCORE_SIZE, final_ranking.end()-it);
        std::for_each_n(it, cnt, [page](const Player& p) {
            store_final_score(page, p.display_name, p.score);
        });
        page++;
        it += cnt;
    }
}

Отправку приглашений можно выполнять параллельно (строка 18), но мы должны избегать выхода за границы (std::min в строке 19). Для разбиения на страницы мы переходим блоками размером PAGE_SCORE_SIZE и для каждого блока вызываем for_each_n (строка 26).

swap, swap_ranges, iter_swap

Вторая группа алгоритмов, которую мы сегодня обсудим, – это группа операций обмена.

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

Мы можем специализировать std::swap внутри пространства имен std, но это будет означать, что эта специализация не будет сопоставляться с использованием поиска, зависящего от аргумента (он будет жить в пространстве имен, отличном от его параметров). Это означает, что неквалифицированный вызов swap не найдет правильной реализации.

Правильный способ специализации swap – предоставить (дружественную) функцию в том же пространстве имен, что и структура данных:

namespace SomeLib {

struct SomeStruct {
    std::vector<int> data;

    friend void swap(SomeStruct& left, SomeStruct& right) {
        left.data.swap(right.data);
    }
};

}

И правильный способ вызвать swap – это подтянуть std::swap перед неквалифицированным вызовом:

void some_algorithm(auto& a, auto& b) {
    using std::swap;
    swap(a, b);
}

К счастью, версия swap для диапазонов в C++20 устраняет эту сложность. Она служит окончательным решением, и она:

• вызовет пользовательскую или стандартную версию swap, соответствующую типам;
• если такой версии не существует и параметры являются диапазонами, будет выполнена swap_range;
• если параметры не являются диапазонами, по умолчанию используется версия swap с перемещением
  V v(std::move(t)); t = std::move(u); u = std::move(v);

namespace Library {
struct Storage {
    int value;
};

void swap(Storage& left, Storage& right) {
    std::ranges::swap(left.value, right.value);
}
}

int main() {
    int a = 1, b = 2;
    std::ranges::swap(a, b);

    Library::Storage j{2}, k{3};
    std::ranges::swap(j, k); // вызов пользовательской Library::swap()
}

Наконец, давайте поговорим о двух других вариантах, iter_swap и swap_ranges.

iter_swap также можно назвать косвенным обменом, когда базовые значения заменяются итераторами или другими косвенными типами. Это в основном полезно для реализации пользовательских алгоритмов, поскольку они работают с итераторами.

Вот пример реализации алгоритма разбиения с использованием iter_swap (строка 12):

template <typename It, typename Cond>
    requires std::forward_iterator<It> 
        && std::indirectly_swappable<It,It> 
        && std::predicate<Cond>
auto partition(It first, It last, Cond cond) {
    while (first != last && cond(first)) ++first;
    if (first == last) return last;

    for (auto it = std::next(first); it != last; it++) {
        if (!cond(it)) continue;

        std::iter_swap(it, first);
        ++first;
    }
    return first;
}

Операция обмена значений диапазонов – это перестановка частями двух непересекающихся диапазонов (возможно, из одного контейнера). Итератор начала задает второй диапазон, и вызывающий несет ответственность за обеспечение достаточной емкости целевого диапазона.

std::vector<int> data{ 1, 2, 3, 4, 5, 6, 7, 8, 9};
std::swap_ranges(data.begin(), data.begin()+3, data.rbegin());
// 9, 8, 7, 4, 5, 6, 3, 2, 1

Здесь мы меняем местами первые три элемента массива с последними тремя элементами массива. Порядок элементов обратный, потому что мы используем rbegin (начальный итератор для обратной итерации).

Спасибо за чтение

Следующая статья будет об алгоритмах сортировки и разбиения.

Теги