Поддерживать порядок вставки для одинаковых элементов в std :: multiset

Question

Поддерживать порядок вставки для одинаковых элементов в std :: multiset

У меня есть std :: multiset отсортированных пользовательских объектов. Два равных объекта (на основе < оператор) в мультимножестве может содержать несколько полей, которые не равны. В таком случае мне нужно поддерживать порядок вставки объектов в мультимножество<>.

Я знаю, что это не проблема, если я использую C ++ 11, но мы не на этом этапе.

Другое решение, которое я видел, использует поле метки времени в классе, используя <ctime> но это дает разрешение в 1 секунду. Если у меня есть 2 вставки в одну секунду, то я не могу использовать метку времени в операции сравнения. Мы не / не можем использовать boost :: chrono в этом проекте.

Есть ли другой способ, которым я могу использовать, чтобы обеспечить сохранение порядка вставки?

1

c++multiset stl strict-weak-ordering

Решение

Другие решения

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

1

Источник

Accepted Answer

Вот дикая идея: как предлагает @Jerry, ведите счетчик. Поскольку пара объекта и счетчика уникальна, теперь мы можем использовать набор (упорядоченный лексикографически). Тогда мы используем lower_bound найти точку вставки и вычислить следующее значение счетчика:

unsigned int const uimax = std::numeric_limits<unsigned int>::max();

typedef std::set<std::pair<T, unsigned int>> pair_set;

void counted_insert(pair_set & s, T const & t)
{
pair_set::iterator it = s.lower_bound(std::make_pair(t, uimax));

if (it == s.begin() || !(*--it == t))
{
s.insert(it, std::make_pair(t, 0));
}
else
{
s.insert(it, std::make_pair(t, it->first + 1));
}
}

1