Set with custom compare

Question

In my project I use std::set with custom Compare function for maintaining an event queue. It fulfills following criteria:

• event duplication is not allowed
• should maintain the insertion order

(tried std::vector first, but that performed poorly because of complicated duplicate removal)

The important code is:

template <typename T>
class EventQueue {
public:
 EventQueue() : set_(std::set<DataWrap>()) {}
 void Insert(T elem) {
 set_.insert(DataWrap(elem, set_.size()));
 }
 // ....
private:
 struct DataWrap {
 T data;
 unsigned int order;
 DataWrap(T d, unsigned int o) : data(d), order(o) {}
 bool operator<(const DataWrap& other) const {
 if (data == other.data)
 return false;
 else
 return order < other.order;
 }
 };
 std::set<DataWrap> set_;
};

Naturally I want to avoid undefined behaviour. As far as I can see my Compare fulfills the requirements of strick weak ordering (irreflexive, transitive, asymetric)

Can you confirm that this code is well-defined, or am I missing something? Thanks for your time!

• ratchet freak: If the size of the vector isn't too large then dupe removal can be a loop over the data and then not inserting the duplicate if you find one. That'll be fast enough. Though you'll want something more akin to a circular buffer for fast pop_front behavior.
• Maikel: This doesn't check for unique elements of T at all! The std::vector variant would be linear but at least correct. If you don't have LessThanComparable<T> available, then you have to try hashing to get better than linear asymptotics.
• pergy: @ratchetfreak usually i have 50-100 event in the set and 10-20 duplicate from it. I will investigate further vector based solution!
• Maikel: @Incomputable @pergy std::set will check only log(n) elements selected by the bisection defined on its comparison operator. This doesn't guarantee uniqueness of elements of T, only uniqueness to insertion ids.
• vnp: It is not transitive. Consider a(x, 0), b(y, 1), c(x, 3). Here a < b, b < c, but !(a < c).

Answer 1

As a side note, you pass the element by copy not by const reference. This might also have some real preformance effects. SO rather do

 void Insert(const T&) 

Also you could use emplace_back to enable inplace construction of the elements in the vector. On the other hand std::find only takes const T& so I would guess, that move semantics do not really buy you anything here.

• pergy: Thanks for suggestion! I changed it to accept const&

Answer 2

As it can be concluded from precious comments my design has major flaws:

First, it fails to avoid having duplicates. As @Maikel pointed out

std::set will check only log(n) elements selected by the bisection defined on its comparison operator. This doesn't guarantee uniqueness of elements of T, only uniqueness to insertion ids

As an example:

Let the Event Type T be int. So this wrapper is something like

{42,1}, {24,2}, {3,3}, {12, 4} ...

If we add another 42 into the queue we might do a bisection: Go to the middle, let's check the upper part of set. It will be something like

{42,1}, {24, 2}, {3,3}, {12,4}, {42,5}

because {42,1} will never get compared with {42,5}

It also fails to fulfill strict weak ordering requirements. As @vnp pointed out

It is not transitive. Consider a(x, 0), b(y, 1), c(x, 3).

Here a < b, b < c, but !(a < c)

Many thanks! (if you guys formulate an answer I accept it gladly)

---

As a result I refactored the queue to use std::vector as underlying data struct and check for duplicates at insertion time. Optimized for consecutive duplicates as it's more likely in my case.

template <typename T>
class EventQueue {
public:
 EventQueue() : v_(std::vector<T>()) {}
 void Insert(const T& elem) {
 if (std::find(v_.rbegin(), v_.rend(), elem) == v_.rend()) {
 v_.push_back(elem);
 } // else drop
 }
 // ....
private:
 std::vector<T> v_;
};

• miscco: Hi, for the next question, you should not edit your code after a recommendation. Better create a new answer with the new code. If somebody write an elaborate answer, it will not make any sense anymore once you have changed your code