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!
T
at all! Thestd::vector
variant would be linear but at least correct. If you don't haveLessThanComparable<T>
available, then you have to try hashing to get better than linear asymptotics. \$\endgroup\$ – Maikel Mar 31 '17 at 10:17std::set
will check onlylog(n)
elements selected by the bisection defined on its comparison operator. This doesn't guarantee uniqueness of elements ofT
, only uniqueness to insertion ids. \$\endgroup\$ – Maikel Mar 31 '17 at 10:48a(x, 0), b(y, 1), c(x, 3)
. Herea < b
,b < c
, but!(a < c)
. \$\endgroup\$ – vnp Mar 31 '17 at 16:53