Is it possible to have an associative ordered container, which can order by a member of the object, rather than the object itself?

Question

For example:

If I wanted to create a message manager which among other functions would maintain a time-ordered list of messages, structured something like this.

class Message
{
    MessageHeader header;
    MessageData data;
};

where the header structure would, among other elements, contain a creation time-stamp.

struct MessageHeader
{
    uint64_t timeStamp;
    userId_t sender;
    userId_t receiver;
    /* ... */
};

Is it possible using an existing container in the STL library to order the messages by the time stamp? I would be using nanosecond time stamps, so the likelihood of not unique values would be low.

463035818_is_not_an_ai · Answer 1 · 2020-10-16T17:58:50.997

3

Yes.

Ordered containers typically use operator< by default and let you specify a custom comparator. For example for a std::map<Message> all you need to add is:

struct Message
{
    MessageHeader header;
    MessageData data;
    bool operator<(const Message& other) const { 
        return header.timeStamp < other.header.timeStamp;
    }
};

to have the map sorted according to the timestamps.

However, note that this comparison is used to establish a notion of equivalence according to:

!comp(a,b) && !comp(b,a) => a is equivalent to b

Which means: If two different messages have the same timestamp then neither of them compares smaller than the other hence they are considered as equivalent by the map. You should make sure that this cannot happen, by making sure that different messages are guaranteed to have different timestamps.

edited Oct 16 '20 at 17:58

answered Oct 16 '20 at 17:35

463035818_is_not_an_ai

109,796
11
89
185

Make sure you're confident that timestamps are actually unique. If the ordering implied by your specified `operator<` isn't actually a strict weak ordering, you can run into trouble. – Nathan Pierson Oct 16 '20 at 17:37
Also I would suggest making `operator<` itself a `const` member method. – Nathan Pierson Oct 16 '20 at 17:38
@NathanPierson thanks will add a note, and `const` is fixed – 463035818_is_not_an_ai Oct 16 '20 at 17:38

score 2 · Answer 2 · answered Oct 16 '20 at 17:46

2

If objects of your type have a natural ordering, then implement that in operator< for the type. If you just want to define a type that is a container with objects sorted in some specific fashion, then you can pass a predicate directly to STL containers such as std::set and std::map.

From c++20, you can create such a type quite conveniently:

using UniqueTimedMessages 
 = std::set<Message, 
            decltype([](auto const& a, auto const &b){
              return a.header.timeStamp < b.header.timeStamp;
            })>;

answered Oct 16 '20 at 17:46

cigien

57,834
11
73
112

as OP is asking for having the container order specifically not according to the types natural order but according to one of its members, this answer is much better than mine. One of the cases where I wouldn't know how to fix my answer other than stealing from here, so I just leave it as is – 463035818_is_not_an_ai Oct 16 '20 at 18:04
1

@idclev463035818 Thanks :) In fact, OP is asking about [this](https://stackoverflow.com/questions/2620862/using-custom-stdset-comparator) and I was about to hammer it, but saw that the solution there didn't make it as convenient as it could be, so figured I'd add something :) – cigien Oct 16 '20 at 18:07
@idclev463035818 Oh, and feel free to "steal" from my answers :) You can always say where you got it from. – cigien Oct 16 '20 at 18:09

Is it possible to have an associative ordered container, which can order by a member of the object, rather than the object itself?

2 Answers2