Если диапазон из N элементов уже отсортирован, то конструирование std::set, std::multiset, std::map или std::multimap из этого диапазона имеет временную сложность O(N); конструирование из неотсортированного диапазона имеет временную сложность O(N*log(N)).

Подробное описание Ссылка на заголовок

Далее мы будем обсуждать std::set; однако те же рассуждения применимы к std::map, std::multiset и std::multimap.

При использовании терминов вроде “отсортирован” или “максимум”, подразумевается, что сравнение выполняется с помощью компаратора контейнера.

Посмотрим на cppreference описание конструктора std::set, который принимает два итератора:

template<class InputIt>
set(InputIt first, InputIt last, const Compare& comp = Compare(), const Allocator& alloc = Allocator());

Сложность: N*log(N), где N — это std::distance(first, last) в общем случае; линейная по N, если [first, last) уже отсортирован согласно value_comp().

Обычная вставка в std::set имеет сложность O(log(N)). Каким образом реализации на практике получают линейный случай?

std::set обычно реализован как красно-чёрное дерево (RB-tree), у которого вставка имеет сложность O(log(N)) (в общем случае). Эта сложность складывается из двух частей, каждая из которых в худшем случае занимает O(log(N)):

  • поиск места, куда нужно вставить элемент;
  • восстановление свойств красно-чёрного дерева (tree fixup) после вставки.

Можно ли избавиться от логарифмического поиска позиции вставки? Да. RB-дерево — это дерево поиска: если мы вставляем новый максимум, то (в состоянии до fixup) он должен стать правым ребёнком текущего максимального элемента. Поэтому можно запомнить адрес вставленной вершины и использовать его, чтобы пропустить полный поиск по дереву позиции вставки для следующего элемента. Обобщая: мы можем полностью избежать O(log(N)) поиска позиции вставки, если умеем подставлять правильную позицию вставки.

Такие “подсказки” позиции вставки называются hint-ами. Hint — это итератор на позицию, перед которой будет вставлен новый элемент (как можно ближе). Например, hint std::set::end() можно использовать, чтобы вставить новый максимум в множество, а std::set::begin() — новый минимум. Hint-ы можно передавать в std::set::insert и std::set::emplace_hint.

Hint — это всего лишь предложение: реализация обычно проверяет, можно ли вставить ключ в предложенную позицию (или рядом с ней). Если нет — происходит откат к обычной вставке за O(log(N)). Если вставка действительно произошла непосредственно перед hint, Стандарт обещает для этих функций амортизированную сложность O(1).

Раньше libstdc++ пыталась “поискать место вставки вокруг” hint-а, даже если он неправильный, но сейчас, если hint некорректен, он просто игнорируется.

Как проверяется hint? В реализациях на основе деревьев обычно проверяют, “помещается” ли новый ключ между hint-ом и его соседом в in-order обходе (как правило, prev(hint) / hint или hint / next(hint)). Если помещается — позиция вставки уже известна, и полный поиск по дереву не нужен; иначе реализация откатывается к обычному O(log(N)) поиску. Такие проверки требуют константное число сравнений (вызовов компаратора), однако переход итератора к предшественнику/последователю (--it / ++it) ради поиска in-order соседа может иметь худшую сложность O(log(N)) в RB-дереве (in-order сосед может находиться “далеко” от hint-а в структуре дерева). Вообще говоря, гарантировать O(1) амортизированно для всех hint-ов и всех паттернов использования нетривиально, и теоретически возможны ситуации, когда даже при корректном hint-е вставка будет иметь O(log(N)) в конкретной реализации. Например, в реализациях вроде GCC libstdc++ и Clang libc++ вставка N элементов с корректным hint-ом, равным текущему корню дерева, приведёт к O(N*log(N)), потому что каждая проверка hint-а будет занимать O(log(N)). Похоже, что стандартная амортизированная гарантия O(1) в основном рассчитана на типичные сценарии использования, не направленные на умышленное осуществления худшего случая.

Реализации могут отдельно оптимизировать такие популярные hint-ы, как std::set::begin() и std::set::end(). В GCC libstdc++ кешируются указатели и на минимальную, и на максимальную вершины, поэтому проверка hint-а std::set::end() дёшево стоит. В libc++ кешируется минимум, но не максимум, поэтому для поиска максимума (и, соответственно, для проверки std::set::end() hint-а) нужен спуск от корня за O(log(N)).

Теоретически можно сделать реализацию, в которой проверка корректности hint-а гарантированно O(1): если вершины дерева дополнительно образуют двусвязный список в in-order порядке. Но это потребует дополнительной памяти (по два указателя на вершину) и дополнительной поддержки этой структуры, поэтому в реальности оно того не стоит.

Остаётся ещё ребалансировка дерева (fixup). Для последовательности вставок в пустое красно-чёрное дерево суммарная стоимость ребалансировок — O(N), то есть O(1) амортизированно на одну вставку. Доказательство этого можно найти, например, здесь (теорема 9.2).

С учётом этого можно представить следующий алгоритм конструирования из диапазона. Вставляем элементы по одному, одновременно поддерживая текущий максимум в контейнере. Если вставляемое значение больше текущего максимума, то позиция вставки уже известна: правый потомок максимальной вершины, а затем tree fixup. Иначе выполняется обычная вставка. Для отсортированного диапазона позиция вставки каждого следующего элемента известна заранее. Это даёт общую сложность O(N) на построение. Для неотсортированного диапазона производительность деградирует до O(N*log(N)). Ровно так делает Clang libc++. GCC libstdc++ делает немного иначе: она постоянно использует std::set::end() в качестве hint-а. Это нормально для их реализации, потому что у них всегда поддерживается указатель на максимальную вершину, и проверка std::set::end() hint-а получается быстрой.

Диапазонная перегрузка std::set::insert не даёт гарантии линейной сложности для отсортированных диапазонов.

Пример Ссылка на заголовок

Алгоритмические сложности, написанные в комментариях, — это сложности, гарантированные Стандартом:

#include <iterator>
#include <ranges>
#include <set>

int main() {
  const auto v = std::views::iota(0, 10000);  // 0 ... 9999

  // O(N)
  std::set<int> s1{std::cbegin(v), std::cend(v)};

  // O(N*log(N))
  std::set<int> s2;
  for (int x : v) {
    s2.insert(x);
  }

  // O(N)
  std::set<int> s3;
  for (int x : v) {
    s3.insert(std::cend(s3), x);
  }
}

Бенчмаркинг Ссылка на заголовок

Код Ссылка на заголовок

Онлайн-результаты бенчмарка и код — здесь.

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <numeric>
#include <random>
#include <set>
#include <vector>

constexpr int N = 1 << 12;

std::vector<int> make_sorted(std::size_t n) {
  std::vector<int> v(n);
  std::iota(v.begin(), v.end(), 0);
  return v;
}

// Генерирует один и тот же неотсортированный вектор для разных реализаций STL,
// чтобы сравнение было честным.
std::vector<int> make_unsorted(std::size_t n) {
  std::vector<int> v(n);
  std::mt19937_64 mt{};
  for (int& x : v) {
    x = static_cast<int>(mt());
  }
  return v;
}

static void constructor_sorted(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_sorted(n);
  for (auto _ : state) {
    std::set<int> s(v.cbegin(), v.cend());
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(constructor_sorted)->Arg(N);

static void insert_sorted_begin_hint(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  std::vector<int> v = make_sorted(n);
  std::reverse(std::begin(v), std::end(v));
  for (auto _ : state) {
    std::set<int> s;
    for (int x : v) {
      s.insert(s.begin(), x);
    }
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(insert_sorted_begin_hint)->Arg(N);

static void insert_sorted_end_hint(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_sorted(n);
  for (auto _ : state) {
    std::set<int> s;
    for (int x : v) {
      s.insert(s.end(), x);
    }
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(insert_sorted_end_hint)->Arg(N);

static void insert_sorted_range(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_sorted(n);
  for (auto _ : state) {
    std::set<int> s;
    s.insert(std::cbegin(v), std::cend(v));
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(insert_sorted_range)->Arg(N);

static void insert_sorted_no_hint(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_sorted(n);
  for (auto _ : state) {
    std::set<int> s;
    for (int x : v) {
      s.insert(x);
    }
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(insert_sorted_no_hint)->Arg(N);

static void constructor_unsorted(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_unsorted(n);
  for (auto _ : state) {
    std::set<int> s(v.begin(), v.end());
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(constructor_unsorted)->Arg(N);

static void insert_unsorted_begin_hint(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_unsorted(n);
  for (auto _ : state) {
    std::set<int> s;
    for (int x : v) {
      s.insert(s.begin(), x);
    }
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(insert_unsorted_begin_hint)->Arg(N);

static void insert_unsorted_end_hint(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_unsorted(n);
  for (auto _ : state) {
    std::set<int> s;
    for (int x : v) {
      s.insert(s.end(), x);
    }
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(insert_unsorted_end_hint)->Arg(N);

static void insert_unsorted_range(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_unsorted(n);
  for (auto _ : state) {
    std::set<int> s;
    s.insert(std::cbegin(v), std::cend(v));
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(insert_unsorted_range)->Arg(N);

static void insert_unsorted_no_hint(benchmark::State& state) {
  const std::size_t n = static_cast<std::size_t>(state.range(0));
  const std::vector<int> v = make_unsorted(n);
  for (auto _ : state) {
    std::set<int> s;
    for (int x : v) {
      s.insert(x);
    }
    benchmark::DoNotOptimize(s.size());
  }
}
BENCHMARK(insert_unsorted_no_hint)->Arg(N);

Графики ниже — для Clang 17:

std::set, 4096 элементов, libc++
std::set, 4096 элементов, libstdc++
std::set, 65536 элементов, libc++
std::set, 65536 элементов, libstdc++

Мои локальные замеры с:

  • Clang 18.1.3 с флагами -O3 -std=c++23 -DNDEBUG
  • libc++ 18.1.3
  • libstdc++ 13.3.0 показывают те же паттерны. Эти паттерны не меняются, если взять другое число вставляемых элементов и/или использовать PMR set с monotonic buffer, тем самым исключив возможные эффекты выделения памяти. GCC с libstdc++ даёт в целом те же числа, что и Clang с libstdc++.

Анализ Ссылка на заголовок

Результаты бенчмаркинга довольно интересные. Для GCC libstdc++ range-конструктор и последовательные вставки с hint-ами std::set::begin()/std::set::end() дают похожие результаты и на отсортированном входе, и на неотсортированном.

Для Clang libc++ на неотсортированном входе последовательная вставка с hint-ом std::set::begin() по времени почти не отличается от range-конструктора. На отсортированном входе range-конструктор работает примерно так же, как и последовательная вставка с hint-ом std::set::end(). Однако последовательная вставка с hint-ом std::set::begin() быстрее обоих! Похоже, что для libc++ самый быстрый способ построить std::set из отсортированного диапазона — это не range-конструктор, а последовательные вставки с hint-ом std::set::begin().

И в libc++, и в libstdc++ контейнеры std::set, std::multiset, std::map, std::multimap используют одну и ту же базовую реализацию дерева, поэтому и их производительность должна быть схожей. Я сделал несколько прогонов для остальных трёх контейнеров, и в каждом случае в libc++ самым быстрым вариантом тоже оказалась последовательная вставка с hint-ом begin().

Я пока не знаю, почему range-конструктор в libc++ работает медленнее, чем вставки с hint-ом std::set::begin(). Причина, по которой вставки с корректным hint-ом std::set::begin() быстрее, чем вставки с корректным hint-ом std::set::end(), в libc++ (как уже упоминалось выше) в том, что libc++ кеширует только минимальную вершину, и ей приходится спускаться по дереву от корня, чтобы найти максимум. В противоположность этому, GCC libstdc++ кеширует указатели и на минимум, и на максимум, поэтому разница между вставками через begin/end hint там не такая заметная.

Если это наблюдение для libc++ устойчиво и на других паттернах данных, то первый, приходящий на ум, способ ускорить реализацию libc++ — итерироваться по диапазону в обратном порядке (когда нам передаются двунаправленные итераторы) и вставлять каждое значение с hint-ом std::set::begin(), а не с используемым сейчас подходом с std::set::end(). Разумеется, для уверенных выводов нужны более тщательные тесты на разных видах входных данных и на разных платформах. Если это известная особенность или уже существующий баг, пожалуйста, дайте знать.