Maintain insertion order for equal elements in std::multiset

Question

I have a std::multiset of sorted custom objects. Two equal objects (based on the < operator) in the multiset may contain some fields which are not equal. In that case I need to maintain the order of insertion of objects in the multiset<>.

I know this is not an issue if I am using C++11 but we are not at this point.

Another solution I saw uses a timestamp field in the class using <ctime> but that gives a resolution of 1 second. If I have 2 insertions in the same second then I cant use the timestamp in the compare operation. We are not / can not using boost::chrono on this project.

Is there another way I can use to ensure insertion order is maintained?

Answer 1

Here's a wild idea: As @Jerry suggests, maintain a counter. Since the pair of object and counter is unique, we can now use a set (ordered lexicographically). Then we use lower_bound to find the insertion point and compute the next counter value:

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