dalerank 9 фев в 23:54

Game++. Juggling STL algorithms

Простой

29 мин

2.1K

C++*Программирование*Разработка игр*Игры и игровые консолиУправление разработкой*

Мы все пишем циклы, в каждом софте, в каждой игре они будут. Вы не можете обойтись без них. Скажете, что делает этот код?

Конечно, это просто: код суммирует элементы массива. Похожую задачу про суммирование или другую операцию над массивом мой лид даёт на собесах :) Люди смотрят с удивлением, а потом большинство пишут, вот то, что было выше. И тут три вещи - человек либо поленился прочитать про STL алгоритмы, либо не доверяет нам и знает про них, но думает что не поймем мы, либо знает, но не понимает зачем показываеть эти знания, почему? вопрос оставим открытым. Этот пример с циклом - простейший алгоритм.

Алгоритмы STL — это настоящий швейцарский нож для разработчика. Они не просто помогают писать код, а делают его чище, понятнее и надежнее. В проектах с большими кодовыми базами, где легаси код не всегда стабилен и удобен для поддержки, это особенно важно. Каждый, кто писал циклы вручную, сталкивался с ошибками: вылезли за границы массива, забыли обработать пустой контейнер, сделали лишнее копирование. STL-алгоритмы избавляют от многих проблем, позволяя выразить мысли кратко и четко. Вместо простыней кода с индексами — несколько строк с понятным смыслом. Так что, если вы еще не знакомы со стандартными алгоритмами, самое время это исправить. Это один из тех инструментов, которые однажды освоив, уже невозможно забыть, это как езда на велосипеде, хорошем промышленном велике, за авторством Кнута или Саттера - надежном и с серийным номером.

Похоже, что набирается статей на миницикл. У меня есть план куда двигаться дальше, но если есть идеи, о чем бы вы хотели прочитать - оставляйте в коментах.

Game++. String interning

Game++. Cooking vectors

Game++. Dancing with allocators

Game++. Juggling STL algoritms <=== Вы тут

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

Далее будет использоваться аббревиатура gtl как и std, stl, eastl, все они обозначают стандартную библиотеку. GTL - game templates library, набор алгоритмов, которые реализует тот или иной движок, фреймворк. Обычно разработчики предпочитают делать свои реализации алгоритмов, чтобы избежать зависимостей от вендоров и компиляторов, а также для унификации работы алгоритмов на разных платформах, чем, к сожалению std похвастаться не может.

Большинство реализаций более или менее похожи, а многие опираются на EASTL, как одну из первых, которая появилась в открытом доступе. Первые публичные комиты в EASTL (Electronic Arts Standard Template Library) относятя к 2005 году в рамках внутренних инструментов Electronic Arts, но сама история появления по разным источникам стартует в 1995, или даже на год-другой раньше.

Изначально библиотека создавалась как высокопроизводительная альтернатива стандартной STL, оптимизированная для игровых проектов, разрабатываемых EA. Основной целью EASTL было предсказуемое управлению памятью и повторяемость результатов на разных платформах. EASTL полностью совместима со стандартной библиотекой, и предоставляет контейнеры и алгоритмы, аналогичные STL, но с упором на разработку игр и движков. Позже, в 2007 году, компания вывела проект в open-source и с тех пор она активно используется в игровой индустрии. Как обычно у реализации много критиков, но как и в случае языками программирования, язык либо ругают, либо на нем не пишут.

Продолжаем суммировать массив

Возвращаясь к заданному в начале статьи вопросу - меньшая часть, где-то четверть пишут вот так.

gtl::vector numbers = {1, 2, 3, 4, 5};
int sum = gtl::accumulate(numbers.begin(), numbers.end(), 0);

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

А знаете какая может быть ошибка? Очень простой пример, все тоже самое, просто у нас теперь строки. Строка здесь выступает в качестве класса, который аллоцирует данные при создании.

std::vector numbers = {"1", "2", "3", "4", "5"};
string sum = 0;

for (string num : numbers) { 
  sum += num;
}

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

std::vector numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
std::vector odds;

for (int num : numbers) { 
  if (!!(num % 2)) { 
    odds.push_back(num); 
  } 
}

Аналогично for, но более выразительно и с меньшим количеством кода.

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
std::vector<int> odds;

std::copy_if(numbers.begin(), numbers.end(), std::back_inserter(odds), 
             [] (const auto &v) { return !!(v % 2); })

Другой пример

Если вы хоть немного знакомы с программированием, то, просмотрев этот код, вы поймете, что он копирует элементы из массива numbers в другой массив по какому-то условию. В принципе, вам даже не надо смотреть на само условие, потому мы смотрим в данном случае на логику работы.

std::vector numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; 
std::vector odds;

std::copy_if(numbers.begin(), numbers.end(), std::back_inserter(odds),
             [] (auto &v) { return v % 2 != 0; })

Там вобще может быть что-то такое:

 std::copy_if(numbers.begin(), numbers.end(), std::back_inserter(odds),
              func);

Даже если вы не знаете что означает std::back_inserter, вы сразу понимаете - данные из одного массива копируются в другой массив, потому что в коде явно указано: copy. В этом разница между написанием сырой логики, которую нужно прочитать и осмыслить, прежде чем двинуться дальше.

Это всего 10–15 секунд. Но если умножить это на количество строк в вашей кодовой базе и учесть более сложные сценарии, как много времени вы тратите на разбор логики внутри блока, вместо понимания логики работы этого участка кода в целом?

std::copy/copy_if — это алгоритм, доступный во всех имплементациях STL (а их больше десятка), и каждый вендор старается сделать свою. Да, некоторые элементы в этом коде больше похожи на шум, чем на полезную информацию — например, .begin() и .end(), но это было сделано из-за принципа ортогональности данных. В любом случае, такое использование STL закладывает хорошую, и главное, стандартную основу для написания понятного и самодокументируемого кода. Это как разговаривать на одном языке.

Все алгоритмы STL, разработанные за десятилетия развития языка, указывают, что конкретно они делают. Они НЕ выносят наружу как они это делают. Это напрямую связано с принципом разработки «пиши логику, а не код», про которую часто говорит Саттер. Но мне больше нравится «zero copy programming» стиль, который несет в массы Александреску.

Как работают итераторы

Немного углубимся в прошлый пример, если вам знакома эта часть языка, смело проматывайте дальше. Тут нет, чего-то интересного -std::copy_if принимает на вход три итератора:

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

template<typename ...> 
OutputIterator copy_if(InputIterator first, 
                       InputIterator last,
                       OutputIterator out,
                       Func func);

Началом диапазона считается итератор, указывающий на его первый элемент, концом диапазона является итератор, указывающий на элемент, следующий за последним: выходной итератор в std::copy_if — это начало диапазона, в который будут скопированы элементы. std::copy_if проходит по входному диапазону и последовательно копирует все элементы, которые попадают в условие, в выходной диапазон, начинающийся с итератора out.

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

Тут на помощь приходит std::back_inserter. Он создает итератор, который привязан к переданному контейнеру. Когда через этот итератор записывается значение, фактически вызывается метод push_back этого контейнера с передаваемым значением. Теперь при использовании других контейнеров с неизвестным размером, а это будет в 90% случаев, нет необходимости вручную его изменять.

Fluent C++

Знание и применение алгоритимов - это обычный "разговорный" C++. Это уже часть языка, без которой он не воспринимается многими разработчиками как полноценный. И умение читать такой код становится не то, что желаемым навыком, но скорее необходимым, и не надо бояться писать такой код.

Надеюсь, теперь вам понятно одно из главных преимуществ алгоритмов — это их стандартная выразительность, они меняют уровень абстракции логики, убирая необходимость "писать отдельные слова" и позволяют писать сразу предложениями. Алгоритмы показывают Что вы делаете в данном участке кода, а не Как вы это делаете.

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

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(3); // выделяем с размером всего 3.
    
// Попытка скопировать все 5 элементов из source в destination.
// вызывает запись за границы массива.
std::copy(source.begin(), source.end(), destination.begin());
int sum = *std::max_element(destination.begin(), destination.end());

for (int t : destination) {
    printf("%d", t);
}

printf("\n%d", ((int*)destination.data())[4]);
printf("\n%d", sum);

>> 123
>> 5
>> 3

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

std::vector<Hit> hits;

...

    int maxDamage = -1;
    for (size_t i = 0; i < hits.size() - 1; ++i) { // int -> size_t
        int pa = hits[i];
        int pb = hits[i + 1];

        maxDamage = std::max(maxDamage, std::max(pa, pb));
        ...
        
    }
    updateDamage(maxDamage)
...

int поменяли на size_t когда убирали ворнинги clang, и получили краш на пустых коллекциях. Если же опираться только на ту логику, что есть, то это могло быть сделано более выразительно и безопасно, и также бы избавляло от другой частой ошибки - обработки пустых коллекций. Здесь есть один нюанс, я не обрабатываю случай когда в Hits содержится только одни элемент, оригинальная логика в этом случае вернет -1.

auto it = std::max_element(hits.begin(), hits.end());
int maxDamage = it != hits.end() ? *it : -1;
updateDamage(maxDamage)

Еще использование алгоритмов убирает ошибки "размазанного перфа", когда вы пользуетесь индексами для контейнера. В общем случае мы не можем знать как реализован оператор получения элемента по индексу. Опять же тест - синтетика, но и реальных примеров, на которых он основан, в существующем коде пруд пруди. Один из них, который уже не первый раз встречается в коде разных игровых движков, когда любители итерироваться по list, делают "удобную" возможность делать это через индекс. Там нет аллокаций, которые были бы видны в профайлере, просто функция начинает потихоньку "поджирать" время, и иногда оно действительно небольшое, но суммарно набегает достаточно, чтобы отнять у вас фрейм-другой, пока вы обратите внимание на такую аномалию и примете меры. (https://quick-bench.com/q/rg6kugF2MYqDIbHK_HsP4Gki_Dg)

    list::at(int i) {
      // Двигаем итератор i раз
      return *std::next(lst.begin(), i);
    }

    int listSum = 0;
    for (size_t i = 0; i < lst.size(); ++i) {
        listSum += list.at(i);
    }

Размазанный перф

std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> lst = {6, 7, 8, 9, 10};

static void VectorIndexSum(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    int vecSum = 0;
    for (size_t i = 0; i < vec.size(); ++i) {
        vecSum += vec[i]; // Обычный доступ по индексу
    }
    // Make sure the variable is not optimized away by compiler
    benchmark::DoNotOptimize(vecSum);
  }
}
// Register the function as a benchmark
BENCHMARK(VectorIndexSum);

static void ListIndexSum(benchmark::State& state) {
  // Code before the loop is not measured
  for (auto _ : state) {
    int listSum = 0;
    for (size_t i = 0; i < lst.size(); ++i) {
        listSum += *std::next(lst.begin(), i); // Двигаем итератор i раз
    }
    benchmark::DoNotOptimize(listSum);
  }
}
BENCHMARK(ListIndexSum);

static void ListIterSum(benchmark::State& state) {
  // Code before the loop is not measured
  for (auto _ : state) {
    int listSum = 0;
    for (auto it = lst.begin(); it != lst.end(); ++it) {
        listSum += *it; // Двигаем итератор i раз
    }
    benchmark::DoNotOptimize(listSum);
  }
}
BENCHMARK(ListIterSum);

static void NoopIndexSum(benchmark::State& state) {
  // Code inside this loop is measured repeatedly
  for (auto _ : state) {
    int vecSum = 0;
    // Make sure the variable is not optimized away by compiler
    benchmark::DoNotOptimize(vecSum);
  }
}
// Register the function as a benchmark
BENCHMARK(NoopIndexSum);

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

Как обычно есть масса способов выстрелить себе в ногу при сколь угодно грамотном и безопасном фреймворке, но тут хотя бы есть глушитель, дополнительно обмотанный тряпками. Будет не так больно и свалится на тестах или внутрениих ассертах, в случае чего ногу можно будет перевязать тряпкой от глушителя и допрыгать до закрытия сессии.

Data + Algorithms

Еще одно хорошее свойство алгоритмов - разделение алгоритмов и данных, на которых они работают. Nicolai M. Josuttis в своей книге The C++ Standard Library: A Tutorial and Reference достаточно много времени уделяет тому, что основная идея STL — разделение алгоритмов и контейнеров посредством итераторов, что позволяет развивать структуры данных и операции над ними независимо друг от друга. До определенной степени конечно.

Возможно, термин "итераторное разделение" (iterator separation) будет правильным, но на русском это звучит как "разделение через итераторы", оно редко встречается в ру-литературе, наши переводчики больше используют другой термин - "обобщенное программирование" или более умное "ортогональность данных". В STL хватает простых и очевидных алгоритмов, но также, там омень много широкоприменимых решений, которые в наивном варианте работают за O(n²), но в STL оптимизированы до O(n).

Эти решения покрывают 80% каждодневной работы. Поначалу разнообразие алгоритмов STL может казаться давящим, и разработчики, даже с опытом, бывает ограничиваются знакомыми, вроде std::copy, std::count или std::find, поскольку их назначение очевидно, и редко заглядывают дальше std::is_heap_until.

Это нормальная и естественная реакция — игнорировать «странные» алгоритмы, которые кажутся слишком сложными или редкими, но будь они действительно редкими их бы не поместили в стандартную библиотеку. Я периодически мониторю пропозалы новых стандартов в отношении алгоритмов, и каждый год их расшаривается больше десятка для обсуждения, но действительно новые принимаются редко. Возможно это правильно - почти все алгоритмы STL, которые сейчас есть в библиотеке полезны в повседневном примении, надо просто знать их и видеть, где они подходят.

Кеширование шейдеров

Возьмём, например, std::set_difference. Этот алгоритм выполняет разность множеств для любых отсортированных контейнеров. Имея отсортированные контейнеры A и B, можно получить элементы, которые есть в A, но отсутствуют в B.

Применение очень широкое, приведу пример из текущего движка, где этот алгоритм ипользуется при кэшировании шейдеров. Каждый раз при старте игры, она обновляет текущий набор шейдеров. Кеш шейдеров представлен в виде ассоциативного контейнера, содержащего ключи и значения, при этом допускается наличие нескольких одинаковых ключей, потому что шейдер может существовать в разных вариациях для разных типов юнитов. Игра также поддерживает моды, поэтому также требуется хранить разные версии шейдера для обеспечения соместимости мода и актуальной версии движка. Для таких случаев идеально подходит std::multimap.

stl::multimap<Key, Shader> shaderCache();

Добавление новых данных в кэш происходит через некоторую функцию addNewShaders , где нужно следить за тем, чтобы не добавлять в кэш уже существующие результаты, иначе мы рискуем накопить дубликаты. Это приводит не только к овериспользованию памяти, но и к логическим проблемам и даже глитчам(визуальным артефактам) в самой игре. Я рекомендую попытаться понять этот код строка за строкой, просто чтобы было с чем сравнивать ниже. Думаю у того программиста, который это писал, просто не было особого выбора - решение было написано для железа 2009 года. Вот как это было реализовано без использования алгоритмов:

void addNewShaders(stl::multimap const& results) {
  ...
  for (stl::multimap<Key, Shader>::const_iterator it = newShaders.begin(); it != newShaders.end(); ++it)
  {
      using iterator = stl::pair<std::multimap<Key, Shader>::const_iterator, stl::multimap<Key, Shader>::const_iterator>::type;
      iterator range = cachedShaders.equal_range(it->first);
      if (range.first == range.second)
      {
          stl::multimap<Key, Shader>::const_iterator it2 = it;
          while (!(it2->first < it->first) && !(it->first < it2->first))
          {
              ++it2;
          }
          cachedShaders.insert(it, it2);
      }
  }
  ...
}

Код бы написан давно, и человек уже в студии не работает, спросить не у кого. Фактически тот программист написал свою реализацию set_difference и скрестил её со вставкой, возможная причина будет указана ниже. Как это работает:

Цикл for проходит по всем элементам контейнера newShaders. Переменная it – это константный итератор. C помощью
iterator range = cachedShaders.equal_range(it->first);производится поиск диапазона элементов в контейнере cachedShaders, у которых ключ равен it->first (ключу текущего элемента из newShaders).

Функция equal_range возвращает пару итераторов (range.first и range.second), где:
- range.first – начало диапазона элементов с данным ключом;
- range.second – итератор, указывающий на первый элемент с другим ключом (конец диапазона).

Условие if (range.first == range.second) проверяет, что в cachedShaders нет ни одного элемента с ключом it->first. Если диапазон пустой, значит, элементов с таким ключом там нет.

Если в cachedShaders отсутствует элемент с данным ключом, то необходимо добавить из newShaders все элементы, у которых ключ равен it->first. Для этого создаётся дополнительный итератор it2, инициализированный значением it:
stl::multimap::const_iterator it2 = it;

Затем выполняется цикл:

while (!(it2->first < it->first) && !(it->first < it2->first))
{
    ++it2;
}

Здесь используется идиома сравнения с помощью оператора < для строгого порядка. Если ни it2->first не меньше it->first, ни it->first не меньше it2->first, то считается, что ключи эквивалентны. Таким образом, после выхода из цикла it2 указывает на первый элемент в newShaders, у которого ключ отличается от it->first.

После завершения внутреннего цикла, диапазон элементов от it до it2 (то есть все элементы с ключом it->first) вставляется в cachedShaders:
cachedShaders.insert(it, it2); если в cachedShaders ещё нет элементов с данным ключом, то вставляется весь блок элементов из newShaders, имеющих этот ключ.

Ну как? Все понятно?

А как сделать через алгоритмы?

А теперь давайте вместо вот той относительно сложной логики, попробуем понять что надо было сделать. А надо добавить в кэш элементы, которые есть в newShaders, но которых нет в кэше (cachedShaders). И тут на помощь приходит stl::set_difference:

stl::multimap<Key, Shader> shadersToAdd;

stl::set_difference(newShaders.begin(),
                    newShaders.end(),
                    cachedShaders.begin(),
                    cachedShaders.end(),
                    stl::inserter(shadersToAdd, shadersToAdd.end()),
                    compareShaderHash);

stl::copy(shadersToAdd.begin(), shadersToAdd.end(), 
          stl::inserter(cachedShaders, cachedShaders.end()));

stl::inserter похож на stl::back_inserter, за исключением того, что он вызывает метод insert контейнера, с которым связан, вместо push_back, а compareShaderHash— это функция, которую мы определяем, чтобы указать stl::set_difference как сравнивать элементы в контейнерах.

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

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

Вместо тысячи слов

Я хочу подвести вас к тому, что понимание алгоритмов STL также важно, как и знание основ языка, шаблонов, хороших практик проектирования и программирования. Это такие же ключевые слова, как if, else, for, auto , только на уровне логики.

Статья получилась больше обзорная, да и примеров маловато. Чтобы было понятно насколько актуальны алгоритмы в текущем игрострое, оставлю тут те, которые рекомендованы к пониманию в нашей студии и паттерны их проявления в коде. Примеры я скопировал с нашей корпвики, надеюсь они не слишком NDA :) Но если найдете ошибку, тоже пишите в коментах.

std::accumulate

std::vector<int> numbers = {1, 2, 3, 4, 5};
int sum = std::accumulate(numbers.begin(), 
                          numbers.end(), 0.f)

std::vector<int> numbers = {1, 2, 3, 4, 5};
int sum = initial_value;
for (int number : numbers) {
    sum += number;
}

std::all_of

int ar[6] = {1, 2, 3, 4, 5, -6};
// Checking if all elements are positive
bool allPositive = all_of(ar, ar+6, [](int x) { return x>0; })

bool allPositive = true;
// Manual check if all numbers are positive
for (int num : numbers) {
    if (num <= 0) {
        allPositive = false;
        break;
    }
}

std::any_of

std::vector<int> numbers = {1, 3, 5, 8, 11};
// Check if any number in the vector is even
bool hasEven = std::any_of(
    numbers.begin(),
    numbers.end(),
    [](int num) { return num % 2 == 0; }
);

std::vector<int> numbers = {1, 3, 5, 8, 11};
bool hasEven = false;
// Manual check if any number is even
for (int num : numbers) {
    if (num % 2 == 0) { 
        hasEven = true;
        break; 
    }
}

std::none_of

std::vector<int> numbers = {1, 3, 5, 7, 9};
// Check if no number in the vector is even
bool noEven = std::none_of(
                numbers.begin(), numbers.end(),
                [](int num){ return !(num%2);})

std::vector<int> numbers = {1, 3, 5, 7, 9};
bool noEven = true;
for (int num : numbers) {
    if (num % 2 == 0) {
        noEven = false;
        break;
    }
}

std::find

std::vector<int> numbers = {10, 20, 30, 40, 50};
int target = 30;     // Value to find
auto it = std::find(numbers.begin(), 
                    numbers.end(), target);
bool found = it != numbers.end();

std::vector<int> numbers = {10, 20, 30, 40, 50};
bool found = false;
for (int num : numbers) {
    if (num == 30) {
        std::cout << "Found " << num << "\n";
        found = true;
        break;
    }
}

std::find_if

std::vector<int> numbers = {10, 20, 30, 40, 50};
auto it = std::find_if(numbers.begin(), numbers.end(), 
               [](int num) { return num > 25; });

std::vector<int> numbers = {10, 20, 30, 40, 50};
bool found = false;
for (int num : numbers) {
    if (num > 25) {
        found = true;
        break;
    }
}

std::find_if_not

std::vector<int> numbers = {10, 20, 30, 40, 50};
auto it = std::find_if_not(
    numbers.begin(), numbers.end(), 
    [](int num) { return num > 25; });

std::vector<int> numbers = {10, 20, 30, 40, 50};
bool found = false;
for (int num : numbers) {
    if (num <= 25) {
        found = true;
        break;
    }
}

std::find_end

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8};
std::vector<int> subsequence = {4, 5};
auto it = std::find_end(
            numbers.begin(), numbers.end(), 
            subsequence.begin(), subsequence.end());

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8};
std::vector<int> subsequence = {4, 5};
bool found = false;
for (size_t i = numbers.size() - subsequence.size(); i != (size_t)-1; --i) {
    bool match = true;
    for (size_t j = 0; j < subsequence.size(); ++j) {
        if (numbers[i + j] != subsequence[j]) {
            match = false;
            break;
        }
    }
    if (match) {
        found = true;
        break;
    }
}

std::find_first_of

std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
std::vector<int> set = {3, 7, 8};
auto it = std::find_first_of(
            numbers.begin(), numbers.end(), 
            set.begin(), set.end());

std::vector<int> numbers = {1, 2, 3, 4, 5, 6};
std::vector<int> set = {3, 7, 8};
bool found = false;
for (int num : numbers) {
    for (int s : set) {
        if (num == s) {
            found = true;
            break;
        }
    }
    if (found) break;
}

std::adjacent_find

std::vector<int> numbers = {1, 2, 3, 4, 4, 6, 7};
auto it = std::adjacent_find(
            numbers.begin(), numbers.end());

std::vector<int> numbers = {1, 2, 3, 4, 4, 6, 7};
bool found = false;
for (size_t i = 0; i < numbers.size() - 1; ++i) {
    if (numbers[i] == numbers[i + 1]) {
        found = true;
        break;
    }
}

std::count

std::vector<int> numbers = {1, 2, 3, 4, 5, 5, 6, 7, 5};
int count = std::count(
              numbers.begin(), numbers.end(), 5);

std::vector<int> numbers = {1, 2, 3, 4, 5, 5, 6, 7, 5};
int count = 0;
for (int num : numbers) {
    if (num == 5) {
        ++count;
    }
}

std :: count_if

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int count = std::count_if(numbers.begin(), numbers.end(), [](int num) {
    return num % 2 == 0; // Count even numbers
});

std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int count = 0;
for (int num : numbers) {
    if (num % 2 == 0) { // Count even numbers
        ++count;
    }
}

std::mismatch

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {1, 2, 0, 4, 5};
auto result = std::mismatch(
                  range1.begin(), range1.end(), 
                  range2.begin());

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {1, 2, 0, 4, 5};
bool foundDifference = false;
for (size_t i = 0; i < range1.size() && i < range2.size(); ++i) {
    if (range1[i] != range2[i]) {
        foundDifference = true;
        break;
    }
}

std::equal

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {1, 2, 3, 4, 5};
std::equal(range1.begin(), range1.end(), 
            range2.begin())

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {1, 2, 3, 4, 5};
bool areEqual = true;
for (size_t i = 0; i < range1.size(); ++i) {
    if (range1[i] != range2[i]) {
        areEqual = false;
        break;
    }
}

std::is_permutation

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {5, 4, 3, 2, 1};
std::is_permutation(range1.begin(), range1.end(),
                    range2.begin())

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {5, 4, 3, 2, 1};
std::vector<int> temp = range2;
std::sort(range1.begin(), range1.end());
std::sort(temp.begin(), temp.end());
bool isPermutation = (range1 == temp);

std::search

std::vector<int> range = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> subsequence = {3, 4, 5};
auto it = std::search(range.begin(), range.end(), 
                      subsequence.begin(), 
                      subsequence.end());
const bool found = (it != range.end());

std::vector<int> range = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> subsequence = {3, 4, 5};
bool found = false;
for (size_t i = 0; i <= range.size() - subsequence.size(); ++i) {
    bool match = true;
    for (size_t j = 0; j < subsequence.size(); ++j) {
        if (range[i + j] != subsequence[j]) {
            match = false;
            break;
        }
    }
    if (match) {
        found = true;
        break;
    }
}

std::search_n

 std::vector<int> range = {1, 2, 3, 3, 3, 4, 5};
 int value = 3;
 size_t count = 3;
 auto it = std::search_n(range.begin(), range.end(), 
                        count, value);
 bool found = (it != range.end());

std::vector<int> range = {1, 2, 3, 3, 3, 4, 5};
int value = 3;
size_t count = 3;
bool found = false;
for (size_t i = 0; i <= range.size() - count; ++i) {
    bool match = true;
    for (size_t j = 0; j < count; ++j) {
        if (range[i + j] != value) {
            match = false;
            break;
        }
    }
    if (match) {
        found = true;
        break;
    }
}

std::copy

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());
std::copy(source.begin(), source.end(),
          destination.begin());

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(source.size());
for (size_t i = 0; i < source.size(); ++i) {
    destination[i] = source[i];
}

std::copy_n

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(3); 
std::copy_n(source.begin(), 3, destination.begin());

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(3);
for (size_t i = 0; i < 3; ++i) {
    destination[i] = source[i];
}

std::copy_if

std::vector<int> source = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> destination;
std::copy_if(source.begin(), source.end(),
             std::back_inserter(destination), 
             [](int num) { return num % 2 == 0; });

std::vector<int> source = {1, 2, 3, 4, 5, 6, 7};
std::vector<int> destination;
for (int num : source) {
    if (num % 2 == 0) {
        destination.push_back(num);
    }
}

std::copy_backward

std::vector<int> source = {1, 2, 3, 4, 5};
// Size of destination should be at least the same as source
std::vector<int> destination(5); 
std::copy_backward(source.begin(), source.end(), destination.end());

std::vector<int> source = {1, 2, 3, 4, 5};
// Size of destination should be at least the same as source
std::vector<int> destination(5); 
for (size_t i = 0; i < source.size(); ++i) {
    destination[destination.size() - 1 - i] = source[i]; // Copy backward
}

std::move

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);
std::move(source.begin(), source.end(),
          destination.begin());
// source vector will be empty after this algo

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);
for (size_t i = 0; i < source.size(); ++i) {
    // Move elements manually
    destination[i] = std::move(source[i]);  
}
source.clear();

std::move_backward

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);
std::move_backward(source.begin(), source.end(), 
                  destination.end())
// source vector will be empty after this algo

std::vector<int> source = {1, 2, 3, 4, 5};
std::vector<int> destination(5);
for (size_t i = 0; i < source.size(); ++i) {
    // Move elements manually backward
    destination[destination.size() - 1 - i] = std::move(source[i]);  
}
// Clear the source after moving elements to simulate 'move'
source.clear();

std::swap

int a = 10, b = 20;
std::swap(a, b);

int a = 10, b = 20;
// Manual swap using a temporary variable
int temp = a;
a = b;
b = temp;

std::swap_ranges

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {6, 7, 8, 9, 10};
std::swap_ranges(range1.begin(), range1.end(), 
                 range2.begin());

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {6, 7, 8, 9, 10};
// Manual swap of elements
for (size_t i = 0; i < range1.size(); ++i) {
    int temp = range1[i];
    range1[i] = range2[i];
    range2[i] = temp;
}

std::iter_swap

std::vector<int> vec = {1, 2, 3, 4, 5};
// Swap the elements pointed to by two iterators
std::iter_swap(vec.begin(), vec.begin() + 4);

std::vector<int> vec = {1, 2, 3, 4, 5};
// Manual swap of elements using iterators
auto it1 = vec.begin();
// Point to the last element
auto it2 = vec.begin() + 4;  
int temp = *it1;
*it1 = *it2;
*it2 = temp;

std::transform

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result(vec.size());
// Transform the elements by multiplying each by 2
std::transform(vec.begin(), vec.end(),
               result.begin(), 
               [](int x) { return x * 2; });

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result(vec.size());
// Manual transformation by multiplying each element
for (size_t i = 0; i < vec.size(); ++i) {
    result[i] = vec[i] * 2;
}

std::replace

std::vector<int> vec = {1, 2, 3, 4, 5, 3};
// Replace all occurrences of 3 with 10
std::replace(vec.begin(), vec.end(), 3, 10);

std::vector<int> vec = {1, 2, 3, 4, 5, 3};
// Manual replace of all occurrences of 3 with 10
for (int& num : vec) {
    if (num == 3) {
        num = 10;
    }
}

std::replace_if

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
// Replace all even numbers with 10
std::replace_if(vec.begin(), vec.end(), [](int x) {
    return x % 2 == 0;
}, 10);

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
// Manual replace of even numbers with 10
for (int& num : vec) {
    if (num % 2 == 0) {
        num = 10;
    }
}

std::replace_copy

std::vector<int> vec = {1, 2, 3, 4, 5, 3};
std::vector<int> result;
// Replace all occurrences of 3 with 10 while copying to the new vector
std::replace_copy(vec.begin(), vec.end(), 
                  std::back_inserter(result), 3, 10);

std::vector<int> vec = {1, 2, 3, 4, 5, 3};
std::vector<int> result;
// Manually copy elements and replace 3 with 10
for (int num : vec) {
    if (num == 3) {
        result.push_back(10);
    } else {
        result.push_back(num);
    }
}

std::replace_copy_if

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
std::vector<int> result;
// Replace all even numbers with 10 while copying to the new vector
std::replace_copy_if(vec.begin(), vec.end(), 
                     std::back_inserter(result), 
                     [](int x) { return x % 2 == 0;},
                     10);

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
std::vector<int> result;
// Manually copy elements and replace even numbers
for (int num : vec) {
    if (num % 2 == 0) {
        result.push_back(10);
    } else {
        result.push_back(num);
    }
}

std::fill

std::vector<int> vec = {1, 2, 3, 4, 5};
// Fill the entire range with the value 10
std::fill(vec.begin(), vec.end(), 10);

std::vector<int> vec = {1, 2, 3, 4, 5};
// Manually fill the entire range with the value 10
for (int& num : vec) {
    num = 10;
}

std::fill_n

std::vector<int> vec(10);  // Vector of size 5
// Fill the first 5 elements with the value 10
std::fill_n(vec.begin(), 5, 10);

std::vector<int> vec = {1, 2, 3, 4, 5};
// Manually fill the entire range with the value 10
for (int i = 0; i < 5; ++i) {
    vec[i] = 10;
}

std::generate

int generate_value() {
  static int i = 1;
  return i++;  
}
std::vector<int> vec(5);
// Generate values for the range using 
// the generate_value function
std::generate(vec.begin(), vec.end(), generate_value);

int generate_value() {
  static int i = 1;
  return i++;  
}
std::vector<int> vec(5);
// Manually generate values for the range
for (int& num : vec) {
    num = generate_value();  
}

std::generate_n

int generate_value() {
  static int i = 1;
  return i++;  
}
std::vector<int> vec(5);
// Generate values for the sequence using 
// the generate_value function
std::generate_n(vec.begin(), 5, generate_value);

int generate_value() {
  static int i = 1;
  return i++;  
}
std::vector<int> vec = {1, 2, 3, 4, 5};
// Manually fill the entire range with the value 10
for (int i = 0; i < 5; ++i) {
    vec[i] = generate_value();
}

std::remove

std::vector<int> vec = {1, 2, 3, 4, 5, 3};
// Remove all occurrences of 3
vec.erase(std::remove(vec.begin(), vec.end(), 3),
          vec.end());

std::vector<int> vec = {1, 2, 3, 4, 5, 3};
// Manually remove all occurrences of 3
for (int i = 0; i < vec.size(); ++i) {
    if (vec[i] != 3) {
        vec.erase(i);
        --i;
    }
}

std::remove_if

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
// Remove all even numbers
vec.erase(std::remove_if(vec.begin(), vec.end(), 
          [](int x) { return x % 2 == 0;}),
          vec.end());

bool wantRemove(int n) { return n % 2 == 0; }
std::vector<int> vec = {1, 2, 3, 4, 5, 3};
// Manually remove all occurrences of 3
for (int i = 0; i < vec.size(); ++i) {
    if (wantRemove(vec[i])) {
        result.erase(i);
        --i;
    }
}

std::remove_copy

std::vector<int> vec = {1, 2, 3, 4, 5, 3};
std::vector<int> result;
// Copy the range while removing all occurrences 
std::remove_copy(vec.begin(), vec.end(), 
                 std::back_inserter(result), 3);

std::vector<int> vec = {1, 2, 3, 4, 5, 3};
std::vector<int> result;
// Manually copy the range while removing all occurrences of 3
for (int num : vec) {
    if (num != 3) {
        result.push_back(num);
    }
}

std::remove_copy_if

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
std::vector<int> result;
// Copy the range while removing all even numbers
std::remove_copy_if(vec.begin(), vec.end(), 
                    std::back_inserter(result), 
                    [](int x) { return x % 2 == 0; });

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
std::vector<int> result;
// Manually copy the range while removing all 
// even numbers
for (int num : vec) {
    if (num % 2 != 0) {
        result.push_back(num);
    }
}

std::unique

std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 4, 5};
auto last = std::unique(vec.begin(), vec.end());
vec.erase(last, vec.end());

std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 4, 5};
std::vector<int> result;
for (size_t i = 0; i < vec.size(); ++i) {
    if (i == 0 || vec[i] != vec[i - 1]) {
        result.push_back(vec[i]);
    }
}
std::swap(vec, result);

std::unique_copy

std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 4, 5};
std::vector<int> result;
std::unique_copy(vec.begin(), vec.end(),
                 std::back_inserter(result));

std::vector<int> vec = {1, 1, 2, 2, 3, 3, 3, 4, 4, 5};
std::vector<int> result;
for (size_t i = 0; i < vec.size(); ++i) {
    if (i == 0 || vec[i] != vec[i - 1]) {
        result.push_back(vec[i]);
    }
}

std::reverse

std::vector<int> vec = {1, 2, 3, 4, 5};
std::reverse(vec.begin(), vec.end());

std::vector<int> vec = {1, 2, 3, 4, 5};
size_t left = 0;
size_t right = vec.size() - 1;
while (left < right) {
    std::swap(vec[left], vec[right]);
    ++left;
    --right;
}

std::reverse_copy

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result;
std::reverse_copy(vec.begin(), vec.end(),
                  std::back_inserter(result));

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result(vec.size());
size_t j = 0;
for (int i = vec.size() - 1; i >= 0; --i) {
    result[j++] = vec[i];
}

std::rotate

std::vector<int> vec = {1, 2, 3, 4, 5};
std::rotate(vec.begin(), vec.begin() + 2, vec.end());

std::vector<int> vec = {1, 2, 3, 4, 5};
size_t n = 2;  // Number of positions to rotate
std::vector<int> result(vec.size());
for (size_t i = 0; i < vec.size(); ++i) {
    result[i] = vec[(i + n) % vec.size()];
}
std::swap(vec, result);

std::rotate_copy

std::vector<int> vec = {1, 2, 3, 4, 5};
std::vector<int> result;
std::rotate_copy(vec.begin(), vec.begin() + 2,
                 vec.end(), 
                 std::back_inserter(result));

std::vector<int> vec = {1, 2, 3, 4, 5};
size_t n = 2;
std::vector<int> result(vec.size());
for (size_t i = 0; i < vec.size(); ++i) {
    result[i] = vec[(i + n) % vec.size()];
}

std::random_shuffle

std::vector<int> vec = {1, 2, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(vec.begin(), vec.end(), g);

std::vector<int> vec = {1, 2, 3, 4, 5};
std::srand(std::time(0)); 
for (size_t i = 0; i < vec.size(); ++i) {
    size_t j = std::rand() % vec.size();  
    std::swap(vec[i], vec[j]); 
}

std::shuffle

std::vector<int> vec = {1, 2, 2, 3, 3, 4, 5};
std::random_device rd;
std::mt19937 g(rd());
std::shuffle(vec.begin(), vec.end(), g);

std::vector<int> vec = {1, 2, 2, 3, 3, 4, 5};
std::srand(std::time(0));
for (size_t i = 0; i < vec.size(); ++i) {
    size_t j = std::rand() % vec.size();
    std::swap(vec[i], vec[j]);
}

std::is_partitioned

std::vector<int> vec = {1, 2, 3, 4, 5};
bool result = std::is_partitioned(
                vec.begin(), vec.end(), 
                [](int x) { return x % 2 == 0; });

std::vector<int> vec = {1, 2, 3, 4, 5};
bool partitioned = true;
for (int num : vec) {
    if (num % 2 == 0) {
        if (found_odd) {
            partitioned = false;
            break;
        }
    }
}

std::partition

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
auto partition_point = std::partition(
          vec.begin(), vec.end(), 
          [](int x) { return x % 2 == 0; });

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
std::vector<int> part1, part2;
for (int num : vec) {
    if (num % 2 == 0) {
        part1.push_back(num);
    } else {
        part2.push_back(num);
    }
}
auto tail = std::copy(part1.begin(), part1.end(),
                      vec.begin());
std::copy(part2.begin(), part2.end(), tail);

std::partition_copy

int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int true_arr[5] = {0};
int false_arr[5] = {0};
std::partition_copy(std::begin(arr), std::end(arr),
                    std::begin(true_arr), std::begin(false_arr),
                    [](int i) { return 4 < i; });

std::vector<int> vec = {1, 2, 3, 4, 5, 6};
std::vector<int> part1, part2;
for (int num : vec) {
    if (4 < num) {
        part1.push_back(num);
    } else {
        part2.push_back(num);
    }
}

std::sort

std::vector<int> vec = {5, 3, 1, 4, 2};
std::sort(vec.begin(), vec.end());

std :: partial_sort

std::vector<int> vec = {7, 3, 9, 1, 4, 8};
std::partial_sort(vec.begin(), vec.begin() + 3, 
                  vec.end());

std::vector<int> vec = {7, 3, 9, 1, 4, 8};
for (size_t i = 0; i < 3; ++i) {
    for (size_t j = i + 1; j < vec.size(); ++j) {
        if (vec[j] < vec[i]) {
            std::swap(vec[i], vec[j]);
        }
    }
}

std::partial_sort_copy

std::vector<int> vec = {7, 3, 9, 1, 4, 8};
std::vector<int> result(3);
std::partial_sort_copy(vec.begin(), vec.end(), 
                      result.begin(), result.end());

std::vector<int> vec = {7, 3, 9, 1, 4, 8};
std::vector<int> result(3);
// Copy all elements to result, up to the size of result
for (size_t i = 0; i < result.size(); ++i) {
    result[i] = vec[i];
}
// Sort the copied portion
for (size_t i = 0; i < result.size(); ++i) {
    for (size_t j = i + 1; j < result.size(); ++j) {
        if (result[j] < result[i]) {
            std::swap(result[i], result[j]);
        }
    }
}

std::is_sorted_until

std::vector<int> vec = {1, 2, 5, 4, 6, 7};
auto it = std::is_sorted_until(vec.begin(), vec.end());
const bool sorted = it != vec.end();

std::vector<int> vec = {1, 2, 5, 4, 6, 7};
auto it = vec.begin();
for (; it != vec.end() - 1; ++it) {
    if (*(it + 1) < *it) {
        break;
    }
}
const bool sorted = (it != vec.end() - 1);

std::nth_element

std::vector<int> vec = {7, 2, 9, 4, 6, 3, 8};
std::nth_element(vec.begin(), vec.begin() + 3, vec.end());
std::cout << "The 4th smallest element is: " << vec[3] << "\n";
std::cout << "Partially sorted range: ";
for (int num : vec) {
    std::cout << num << " ";
}
The 4th smallest element is: 6
Partially sorted range: 4 2 3 6 9 8 7

int partition(std::vector<int>& vec, int low, int high) {
  int pivot = vec[high];
  int i = low - 1;
  for (int j = low; j < high; ++j) {
      if (vec[j] < pivot) {
          ++i;
          std::swap(vec[i], vec[j]);
      }
  }
  std::swap(vec[i + 1], vec[high]);
  return i + 1;
}
void nth_element_manual(std::vector<int>& vec, int n, int low, int high) {
  if (low < high) {
      int pivot_index = partition(vec, low, high);
      if (pivot_index == n) {
          return;
      } else if (pivot_index > n) {
          nth_element_manual(vec, n, low, pivot_index - 1);
      } else {
          nth_element_manual(vec, n, pivot_index + 1, high);
      }
  }
}
std::vector<int> vec = {7, 2, 9, 4, 6, 3, 8};
nth_element_manual(vec, 3, 0, vec.size() - 1);
std::cout << "The 4th smallest element is: " << vec[3] << "\n";
std::cout << "Partially sorted range: ";
for (int num : vec) {
    std::cout << num << " ";
}
The 4th smallest element is: 6
Partially sorted range: 4 2 3 6 9 8 7

std::merge

std::vector<int> vec1 = {1, 3, 5, 7};
std::vector<int> vec2 = {2, 4, 6, 8};
std::vector<int> result(vec1.size() + vec2.size());
std::merge(vec1.begin(), vec1.end(), 
           vec2.begin(), vec2.end(), 
           result.begin());
result: 1 2 3 4 5 6 7 8

std::vector<int> vec1 = {1, 3, 5, 7};
std::vector<int> vec2 = {2, 4, 6, 8};
std::vector<int> result(vec1.size() + vec2.size());
auto it1 = vec1.begin();
auto it2 = vec2.begin();
auto it_result = result.begin();
while (it1 != vec1.end() && it2 != vec2.end()) {
    if (*it1 < *it2) {
        *it_result = *it1;
        ++it1;
    } else {
        *it_result = *it2;
        ++it2;
    }
    ++it_result;
}
while (it1 != vec1.end()) {
    *it_result = *it1;
    ++it1;
    ++it_result;
}
while (it2 != vec2.end()) {
    *it_result = *it2;
    ++it2;
    ++it_result;
}

std::includes

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {2, 4};
bool includes = std::includes(range1.begin(), range1.end(), 
                              range2.begin(), range2.end()))

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {2, 4};
auto it1 = range1.begin();
auto it2 = range2.begin();
while (it1 != range1.end() && it2 != range2.end()) {
    if (*it1 < *it2) {
        ++it1;
    } else if (*it1 == *it2) {
        ++it1;
        ++it2;
    } else {
        break;
    }
}
bool includes = (it2 == range2.end())

std::set_union

std::vector<int> range1 = {1, 3, 5, 7};
std::vector<int> range2 = {2, 3, 6, 8};
std::vector<int> result;
result.resize(range1.size() + range2.size());
auto it = std::set_union(range1.begin(), range1.end(), 
                         range2.begin(), range2.end(),
                        result.begin());
result.resize(it - result.begin());
for (int num : result) {
    std::cout << num << " ";
}
1 2 3 5 6 7 8

std::vector<int> range1 = {1, 3, 5, 7};
std::vector<int> range2 = {2, 3, 6, 8};
std::vector<int> result;
auto it1 = range1.begin();
auto it2 = range2.begin();
while (it1 != range1.end() && it2 != range2.end()) {
    if (*it1 < *it2) {
        result.push_back(*it1);
        ++it1;
    } else if (*it2 < *it1) {
        result.push_back(*it2);
        ++it2;
    } else {
        result.push_back(*it1);
        ++it1;
        ++it2;
    }
}
while (it1 != range1.end()) {
    result.push_back(*it1);
    ++it1;
}
while (it2 != range2.end()) {
    result.push_back(*it2);
    ++it2;
}
for (int num : result) {
    std::cout << num << " ";
}
1 2 3 5 6 7 8

std::set_intersection

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {3, 4, 5, 6, 7};
std::vector<int> result;
result.resize(std::min(range1.size(), range2.size()));
auto it = std::set_intersection(range1.begin(), range1.end(), range2.begin(), range2.end(), result.begin());
result.resize(it - result.begin());
for (int num : result) {
    std::cout << num << " ";
}
3 4 5

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {3, 4, 5, 6, 7};
std::vector<int> result;
auto it1 = range1.begin();
auto it2 = range2.begin();
while (it1 != range1.end() && it2 != range2.end()) {
    if (*it1 < *it2) {
        ++it1;
    } else if (*it2 < *it1) {
        ++it2;
    } else {
        result.push_back(*it1);
        ++it1;
        ++it2;
    }
}
for (int num : result) {
    std::cout << num << " ";
}
3 4 5

std::set_difference

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {3, 4, 5, 6, 7};
std::vector<int> result;
result.resize(range1.size());  
auto it = std::set_difference(
                range1.begin(), range1.end(), 
                range2.begin(), range2.end(),
                result.begin());
result.resize(it - result.begin());
for (int num : result) {
    std::cout << num << " ";
}
1 2

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {3, 4, 5, 6, 7};
std::vector<int> result;
auto it1 = range1.begin();
auto it2 = range2.begin();
while (it1 != range1.end()) {
    if (it2 != range2.end() && *it1 < *it2) {
        result.push_back(*it1);
        ++it1;
    } else if (it2 != range2.end() && *it2 < *it1) {
        ++it2;
    } else {
        ++it1;
        ++it2;
    }
}
for (int num : result) {
    std::cout << num << " ";
}
1 2

std::set_symmetric_difference

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {3, 4, 5, 6, 7};
std::vector<int> result;
result.resize(range1.size() + range2.size()); 
auto it = std::set_symmetric_difference(
                range1.begin(), range1.end(), 
                range2.begin(), range2.end(), 
                result.begin());
result.resize(it - result.begin());  
for (int num : result) {
    std::cout << num << " ";
}
1 2 6 7

std::vector<int> range1 = {1, 2, 3, 4, 5};
std::vector<int> range2 = {3, 4, 5, 6, 7};
std::vector<int> result;
auto it1 = range1.begin();
auto it2 = range2.begin();
while (it1 != range1.end() && it2 != range2.end()) {
    if (*it1 < *it2) {
        result.push_back(*it1);
        ++it1;
    } else if (*it2 < *it1) {
        result.push_back(*it2);
        ++it2;
    } else {
        ++it1;
        ++it2;
    }
}
while (it1 != range1.end()) {
    result.push_back(*it1);
    ++it1;
}
while (it2 != range2.end()) {
    result.push_back(*it2);
    ++it2;
}
for (int num : result) {
    std::cout << num << " ";
}
1 2 6 7

std :: minmax

int a = 5, b = 8;
auto result = std::minmax(a, b);

std::pair<int, int> minmax_manual(int a, int b) {
    if (a < b) {
        return {a, b};
    } else {
        return {b, a};
    }
}
int a = 5, b = 8;
auto result = minmax_manual(a, b);

std::min_element

std::vector<int> nums = {10, 20, 5, 30, 15};
auto minElemIt = std::min_element(nums.begin(), nums.end());

int min_element_manual(const std::vector<int>& nums) {
    int minElem = nums[0];
    for (const auto& num : nums) {
        if (num < minElem) {
            minElem = num;
        }
    }
    return minElem;
}
std::vector<int> nums = {10, 20, 5, 30, 15};
int minElem = min_element_manual(nums);

std::max_element

std::vector<int> nums = {10, 20, 5, 30, 15};
auto maxElemIt = std::max_element(nums.begin(), nums.end());

int max_element_manual(const std::vector<int>& nums) {
    int maxElem = nums[0];
    for (const auto& num : nums) {
        if (num > maxElem) {
            maxElem = num;
        }
    }
    return maxElem;
}
std::vector<int> nums = {10, 20, 5, 30, 15};
int maxElem = max_element_manual(nums);

std::minmax_element

std::vector<int> nums = {10, 20, 5, 30, 15};
auto result = std::minmax_element(nums.begin(), nums.end());

std::pair<int, int> minmax_element_manual(const std::vector<int>& nums) {
    int minElem = nums[0];
    int maxElem = nums[0];
    for (const auto& num : nums) {
        if (num < minElem) {
            minElem = num;
        }
        if (num > maxElem) {
            maxElem = num;
        }
    }
    return {minElem, maxElem};
}
std::vector<int> nums = {10, 20, 5, 30, 15};
auto result = minmax_element_manual(nums);

Теги:

Хабы:

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку