StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>One possibility is to use <a href="http://www.cplusplus.com/reference/stl/set/" rel="nofollow">std::set</a> or <a href="http://www.cplusplus.com/reference/stl/unordered_set/" rel="nofollow">std::unordered_set</a> which is basically a hash table and maintain the order between the elements yourself. This will give you O(log(n)) or amortized O(1) lookup complexity and constant insertion/deletion at the beginning/end. In Java this is called LinkedHashSet. Unfortunately STL doesn't provide this kind of data structure out of the box, but it should be easy to implement on top of a set/unordered_set or map/unordered_map.</p> <p>Here's a piece of code that illustrates the idea:</p> <pre><code>template <typename T> class linked_set { private: // Comparator of values with dereferencing. struct value_deref_less { bool operator()(const T *lhs, const T *rhs) const { return *lhs < *rhs; } }; typedef std::set<const T*, value_deref_less> Set; Set set_; // Used for quick lookup std::deque<T> store_; // Used for ordered storage. deque is used instead of // vector because the former doesn't invalidate // pointers/iterators when elements are pushed. public: void push_back(const T& value) { store_.push_back(value); set_.insert(&store_.back()); // TODO: handle the case of duplicate elements. } // TODO: better provide your own iterator. typedef typename Set::iterator iterator; iterator find(const T& value) { return set_.find(&value); } // ... }; </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload