Как понять с какой стороны от `it` `std::multiset::insert(it,value)` будет вставлен элемент?

Question

Допустим, есть итератор it в контейнере std::multiset. Добавляется новое значение в контейнер - value, которое равно значению под итератором *it. Логично использовать std::multiset::insert(it, value) для ускорения вставки, но мне нужно знать встал новый элемент до it или после

std::multiset<T> a;

if (*it == value){
    auto pos = a.insert(it, value);
    //if (it > pos) - то что хотелось бы
    //else
}

Вот, как можно реализовать искомый код? Сейчас приходится использовать вариант

   if(std::distance(a.begin(), it) > std::distance(a.begin(), pos))
   else

Найдётся ли вариант пошустрей?

Итак, мне нужно знать: позиция нового элемента будет до it или после?

Answer 1

В стандарте сказано что в вашем случае элемент будет вставлен прямо перед it:

inserts value in the position as close as possible, just prior(since C++11), to hint

Код можно поменять вот так:

std::multiset<T> a;

if (*it == value){
    auto pos = a.insert(it, value);
    assert(pos + 1 == it);
    // ...
}

Answer 2

В целом, Stanislav Volodarskiy указал правильное направление, оно работает только с C++11.

Что даёт простая вставка значения std::multiset::insert(value)? Стандарт утверждает, вставка value будет в конец последовательности из одинаковых значений, но только начиная с C++11. Для более ранних версий поведение не регламентировано - может встать где угодно в череде одинаковых значений. Сложность O(log N)

Вставка std::multiset::insert(hint, value) позволяет добавить value как можно ближе к hint. Если, при проверке слева от hint, получается вставить value, то вставка происходит за O(1), иначе за O(log N) ищется ближайшее место. Это справедливо для С++11. Для версий до С++11 утверждается, что за O(1) вставка справа от hint, однако, в справке по С++ так же сказано, что hint - всего лишь стартовая позиция поиска (до С++11).

Эксперименты с разными компиляторами и разными стандартами показали, что:

вставка происходит слева от hint за O(1) когда это возможно: *hint >= value && *prev(hint) <= value,
некоторые компиляторы способны сделать вставку за O(1) справа когда *hint < value && *next(hint) <= value,
новый элемент вставал максимально близко к hint,
ни один из задействованных в эксперименте компиляторов не захотел сделать вставку справа от hint при -std=c++98. Тем не менее это не означает, что таких компиляторов нет.

Вывод. Гарантировать, что вставка будет слева от hint можно только для С++11. Гарантировать, что вставка будет справа для ранних стандартов - нельзя. "Любимое" место проверки на доступность вставки - слева от hint.

Чтобы гарантировать, что новый элемент добавиться строго, скажем, справа от it за O(1) достаточно в качестве hint использовать элемент следующий за it:

std::multiset<T> a;

if (*it == value) {
    auto pos = a.insert(std::next(it), value);
    //теперь std::distance(a.begin(), it) всегда меньше std::distance(a.begin(), pos)
}

БЛОГ НА HUSL

Как понять с какой стороны от `it` `std::multiset::insert(it,value)` будет вставлен элемент?

Ответы (2 шт):