Проблема с С++ 0x: вставка константного времени в std:: set

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

iterator std::set::insert ( iterator position, const value_type& x );

а итератор position, который я предоставляю, непосредственно "предшествует" правильной (в порядке) точке вставки.

Теперь, если я знаю, что значение, которое я вставляю, заканчивается (поскольку оно является самым большим), например:

set<int> foo = {1, 2, 3};
foo.insert(4); // this is an inefficient insert

В соответствии с вышеприведенным критерием я должен передать последний элемент foo.end()-1 в insert не foo.end(). Правильно ли я понимаю? Что произойдет, если я пройду foo.end()? Будет ли это вставка O(log n) или O(1). Итак, варианты:

// Option A
foo.insert(foo.end()-1, 4);

// Option B
foo.insert(foo.end(), 4);

// Safer version of Option A
if(foo.empty())
    foo.insert(4);
else
    foo.insert(foo.end()-1, 4);

Я спрашиваю, потому что я пишу функцию, которая была построена на контейнере. Я хочу вставить элемент (который, как я знаю, самый большой), в конец любого контейнера, который передается. Использование "Option A" выше имеет другое поведение для контейнера, такого как vector:

foo.insert(foo.end()-1, 4);
// result is {1, 2, 3, 4} if foo is an std::set
// result is {1, 2, 4, 3} if foo is an std::vector

Как указывает @Bo_Persson, проблема здесь в том, что С++ 03 говорит "логарифмический вообще, но амортизируется постоянным, если t вставлен сразу после p". в то время как С++ 0x говорит "логарифмический вообще, но амортизируется постоянным, если t вставлен прямо перед p."

PS: Я использую GCC 4.5 на Ubuntu 11.04 с поддержкой С++ 0x.

Изменить: я запускал эмпирические тесты с поддержкой и отключением поддержки С++ 0x, а опубликовал результаты в ответе. В основном, вывод состоит в том, что он так же хорош (и, очевидно, безопаснее), чтобы обеспечить end() в качестве подсказки вставки. Однако это, очевидно, просто эмпирическое наблюдение. Стандарт, как указано, по-прежнему запутан в этом аспекте.

Ответы

Ответ 1

Это мошенничество для запуска теста вместо чтения через спецификации библиотеки?

Для g++-4.4 -O2 для целых чисел 0 <= i < 5000000 мое время работы для стандартная вставка

real    0m14.952s
user    0m14.665s
sys 0m0.268s

и мои текущие времена для вставки с использованием end() в качестве подсказки

real    0m4.373s
user    0m4.148s
sys 0m0.224s

Вставка в end() - 1 так же быстро, насколько я могу судить, но это более громоздко использовать, потому что end() - 1 является незаконной операцией (вы должны использовать operator--()), и она сработает, если это произойдет быть пустым.

#include <set>

typedef std::set<int> Set;

void insert_standard(Set& xs, int x)
{
    xs.insert(x);
}

void insert_hint_end(Set& xs, int x)
{
    xs.insert(xs.end(), x);
}

int main()
{
    const int cnt = 5000000;
    Set xs;
    for (int i = 0; i < cnt; i++) {
        // insert_hint_end(xs, i);
        insert_standard(xs, i);
    }
}

Ответ 2

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

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

Ответ 3

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

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

Ответ 4

Следуя по стопам @antonakos, я расширяюсь на "обманом" решении и выполняю эмпирический тест. Я использую GCC 4.5 с оптимизацией (-02) и рассматриваю как тот случай, когда поддержка С++ 0x не включена, а когда она находится с -std=c++0x. Результаты в 40 000 000 вставок следующие (отображение системного времени, так как другие значения в этом случае не являются особыми):

  • Без поддержки С++ 0x
    • Нет подсказки: 26,6 секунд
    • Подсказка end(): 5.71 секунд
    • Подсказка --end(): 5.84 секунд
  • С поддержкой поддержки С++ 0x
    • Нет подсказки: 29,2 секунды
    • Подсказка end(): 5,34 секунды
    • Подсказка: --end(): 5.54 секунды

Заключение: GCC (с включенным или включенным С++ 0x) эффективно вставляет, когда end() предоставляется в качестве подсказки вставки.

Используемый мной код основан на @antonakos's:

#include <set>
typedef std::set<int> Set;

void insert_standard(Set & xs, int x) {
    xs.insert(x);
}

void insert_hint_end(Set & xs, int x) {
    xs.insert(xs.end(), x);
}

void insert_hint_one_before_end(Set & xs, int x) {
    xs.insert(--xs.end(), x);
}

int main() {
    const int cnt = 40000000;
    Set xs;
    xs.insert(0);
    for (int i = 1; i < cnt; i++) {
        //insert_standard(xs, i);
        //insert_hint_one_before_end(xs, i);
        insert_hint_end(xs, i);
    }

    return 0;
}