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!

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.

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