Вопрос по stl, stdset, initialization, c++ – Эффективно инициализировать std :: set с помощью последовательности чисел

16

Очевидный (наивный?) Подход будет:

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

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

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

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

Update:

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

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);
}

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

Вы правы. Спасибо за тестирование. mfontanini
@mfontanini Я инициализирую пустой набор так,begin() должен сделать работу. Я посмотрю, смогу ли я составить быстрый тест, но я уверен, что вторая версия будет быстрее. Shawn Chin
возможный дубликатIs the STL map container optimized (balanced tree) while constructed? Fred Foo
Ммм, вы должны сравнить это, если вы действительно хотите найти наиболее эффективный способ сделать это. Поскольку входные данные расположены в порядке возрастания, я чувствую, что вы добавляете элементы в неправильной позиции (наборы сохраняют данные в порядке возрастания, поэтому begin () будет указывать на наименьшее число). Не могли бы вы сравнить это? Я действительно заинтересован: D mfontanini
@mfontanini Быстрый тест на ideone:naive (0,49 с) противwith hint (0,24 с) для1000000 записей. Shawn Chin

Ваш Ответ

4   ответа
14

Самые красивые будут:

#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);
@rubenvb Нет, когда они другого типа, верно?
Вы можете объявить несколько переменных в одном цикле for. Нет необходимости в структурах
Производительностьcounting_iterator version кажется, не далеко отhinted insert version, Как и ожидалось, они оба стучалиnaive version. Shawn Chin
@pmr Я так думаю. Эта структура выглядит ужасно, черт возьми, без обид.
Спасибо! Я надеялся на что-то подобное, когда я отправил Q. Shawn Chin
4
#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++; });,
}

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

Версия C ++ 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));
}
Благодарю. Конечно, он выглядит более объемным, но с точки зрения C ++ n00b ему гораздо сложнее следовать. Тем не менее, +1 за то, что научил меня чему-то новому. Shawn Chin
Я бы предпочел версию сstatic Int член.
Хм ... не могу заставить его работатьon ideone, Что я упустил? Shawn Chin
Вам нужно выбрать C ++ 0x.
Я попробовал это, и это на самом деле медленнее, чем подсказка, но немного быстрее, чем наивный (по крайней мере, на ideone).
3

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

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

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

Спасибо, прав. Я действительно сталкивался с этими моментами после того, как отправил вопрос, и обновил сообщение, чтобы отразить это. Тем не менее +1. Shawn Chin
19

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

В C ++ 11 вы хотите немедленно использовать итератор для элементаafter тот, который вы собираетесь вставить. Когда вы вставляете по порядку, это немного упрощает: вы всегда используете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() как подсказка, а не итератор, возвращенный предыдущей вставкой.

Я только что проверил код pmr ниже, с подсказкой в .cbegin, .cend и your s.insert (s.end (), i); и твой код самый быстрый. Родной - 83, .cend - 74,5, .cbegin - 66,5, а ваш - 42 плоских. Благодарю. Отлично сработано! Размер набора был 51,200.
Согласноdefect reportуказав его как «после» изначально был несчастным случаем, и большинство реализаций не работали таким образом, даже когда это было указано.
Это может быть что-нибудь близкое и все же помогающее, но описание изменилось с: «Итератор p - это подсказка, указывающая, где вставка должна начать поиск». to: & quot; t вставляется как можно ближе к положению непосредственно перед p. & quot; Сложность следует за этим. В C ++ 03: «амортизированная константа, если t вставляется сразу после p.», Но в C ++ 11: «амортизированная константа, если t вставляется прямо перед p.»
Интересно. Я думал, что итератор для подсказки может быть одним в непосредственной близости.
Странное решение. Есть ли у вас какие-либо советы, где я могу найти обоснование для этого изменения? У меня есть много API, которые следуютinserted right after Схема для подсказок, где ускорение имеет важное значение. Я также представляю, что это гораздо более неудобно в использовании, чем код в моем примере.

Похожие вопросы