Эффективно инициализировать std:: set с последовательностью чисел

Очевидным (наивным?) подходом было бы:

std::set<int> s;
for (int i = 0; i < SIZE; ++i) {
    s.insert(i);
}

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

Есть ли более элегантный/эффективный (или де-факто) способ инициализации std::set с последовательностью чисел?

Или, в общем, как эффективно вставить упорядоченный список записей в коллекцию?

Обновление:

Просматривая документы, я только что заметил конструктор, который принимает итератор, чтобы указать позицию для вставки:

iterator insert ( iterator position, const value_type& x );

Это означает, что это будет более эффективно:

std::set<int> s;
std::set<int>::iterator it = s.begin();
for (int i = 0; i < SIZE; ++i) {
    it = s.insert(it, i);
}

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

Ответы

Ответ 1

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

В С++ 11 вы хотите использовать итератор для элемента сразу после того, который вы собираетесь вставить. Когда вы вставляете в порядок, это делает вещи немного проще: вы всегда используете your_container.end():

std::set<int> s;
for (int i = 0; i < SIZE; ++i) 
    s.insert(s.end(), i);

Вы можете, конечно, использовать алгоритм (например, std::iota) или итератор (например, boost::counting_iterator, как уже упоминалось в @pmr), чтобы генерировать ваши значения, но, насколько это касается самой вставки, для текущей реализации вы хотите использовать .end() как подсказку, а не итератор, возвращенный предыдущей вставкой.

Ответ 2

Самый красивый был бы:

#include <set>
#include <boost/iterator/counting_iterator.hpp>

int main()
{
  const int SIZE = 100;
  std::set<int> s(boost::counting_iterator<int>(0), 
                  boost::counting_iterator<int>(SIZE));

  return 0;
}

Если вы нацелены на сырую эффективность, полезно использовать намеченную версию вставки:

const int SIZE = 100;
std::set<int> s;
auto hint = s.begin();
for(int i = 0; i < SIZE; ++i)
  hint = s.insert(hint, i);

Возможность объявить hint вместе с счетчиком будет приятной и дать нам чистую область, но для этого требуется struct хакерство, которое я нахожу немного запутывающим.

std::set<int> s;
for(struct {int i; std::set<int>::iterator hint;} 
      st = {0, s.begin()};
    st.i < SIZE; ++(st.i))
  st.hint = s.insert(st.hint, st.i);

Ответ 3

#include <algorithm>
#include <set>
#include <iterator>

int main()
{
    std::set<int> s;
    int i = 0;
    std::generate_n(std::inserter(s, s.begin()), 10, [&i](){ return i++; });
}

Это (я думаю) эквивалентно вашей второй версии, но IMHO выглядит намного лучше.

Версия С++ 03 будет:

struct inc {
    static int i;
    explicit inc(int i_) { i = i_; }
    int operator()() { return i++; }
};

int inc::i = 0;

int main()
{
    std::set<int> s;
    std::generate_n(std::inserter(s, s.end()), SIZE, inc(0));
}

Ответ 4

Ну, вы можете использовать версию insert() set<>, в которой вы можете указать позицию как подсказку, где элемент может быть вставлен.

iterator insert ( iterator position, const value_type& x );

Сложность: эта версия является логарифмической вообще, но амортизируется константой, если x вставляется сразу после элемента, указанного позицией.

Ответ 5

Это может быть выполнено в одной строке кода. Лямбда-захват может инициализировать переменную i в 0, а изменяемый спецификатор позволяет обновлять i в лямбда-функции:

generate_n( inserter( s, s.begin() ), SIZE, [ i=0 ]() mutable { return i++; });