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

Question

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

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

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

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

Answer 1

Вот дикая идея: как предлагает @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));
    }
}

Answer 2

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