C ++ 0x проблема: вставка постоянного времени в std :: set - PullRequest
Новая
       28

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

11 голосов
/ 03 июля 2011

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

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

Я спрашиваю, потому что я пишу функцию, которая основана на контейнере.Я хочу вставить элемент (который, я знаю, самый большой) в конец любого контейнера, в который передан. Использование «Варианта А» выше имеет другое поведение для контейнера, например 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, проблема здесь в том, что C ++ 03 говорит «логарифмическая в общем случае, но амортизированная константа, если t вставляется сразу после p».в то время как C ++ 0x говорит «логарифмическая в общем случае, но амортизированная константа, если t вставляется прямо перед p.»

PS: я использую GCC 4.5 в Ubuntu 11.04 с включенной поддержкой C ++ 0x.

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

Ответы [ 4 ]

4 голосов
/ 04 июля 2011

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

Для 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);
    }
}
3 голосов
/ 03 июля 2011

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

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

2 голосов
/ 04 июля 2011

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

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

1 голос
/ 04 июля 2011

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

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

Заключение : GCC (с включенным или выключенным C ++ 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;
}
...