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

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

Для 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);
    }
}

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

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

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

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

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

• Without C++0x support
  • No hint: 26.6 seconds
  • Подсказка на end(): 5,71 секунды
  • Подсказка на --end(): 5,84 секунды
• With C++0x support enabled
  • No hint: 29.2 seconds
  • Подсказка на end(): 5,34 секунды
  • Подсказка на --end(): 5,54 секунды

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

Код, который я использовал, основан на коде @antonakos:

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