StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>You won't be able to have both fast insertions at the two sides AND fast searches with the same container, at least if you restrict the possibilities to the STL. More exotic non-standard containers may help.</p> <p>But the approach I generally choose in these cases is to use two containers. For storing the elements, the obvious option is std::deque. For searches, make a <code>std::map<K,V></code> in which V is an iterator for the deque. Since insert/delete in deques does not invalidate iterators that are not involved, it should be OK IF you always remember to synchronize the map and the deque (i.e. when you do an insert or delete on the deque, do that also on the map). Another simpler/safer option, instead of using iterators - if after a search in the map you just need the element found (you don't need to visit nearby elements, etc.) - is to have in both the deque and the map smart pointers to the actual objects (more specifically, shared_ptr). Again, you have to be careful to keep both in sync; although it won't be as catastrophic if they loose sync, probably the consistency of your program will be compromised, of course.</p> <pre><code>struct MyItem { std::string name; int something; int another; MyItem(const std::string &name_, int something_, int another_) :name(name_), something(something_), another(another_) {} }; class MyContainer { public: typedef std::shared_ptr<MyItem> MyItemPtr; void push_front(MyItemPtr item) { deque.push_front(item); assert(map.find(item->name) == map.end()); map[item->name] = item; } void push_back(MyItemPtr item) { deque.push_back(item); assert(map.find(item->name) == map.end()); map[item->name] = item; } MyItemPtr pop_front() { item = deque.front(); deque.pop_front(); map.erase(item->name); return item; } MyItemPtr pop_back() { item = deque.back(); deque.pop_back(); map.erase(item->name); return item; } MyItemPtr find(const std::string &name) { std::map<std::string, MyItemPtr>::iterator iter = map.find(name); if (iter == map.end()) return MyItemPtr(); else return iter->second; } private: std::deque<MyItemPtr> deque; std::map<std::string, MyItemPtr> map; }; </code></pre> <p>To use it:</p> <pre><code>MyContainer container; MyContainer::MyItemPtr a(new MyItem("blah", 1, 2)); container.push_back(a); MyContainer::MyItemPtr b(new MyItem("foo", 5, 6)); container.push_front(b); MyContainer::MyItemPtr f = container.find("blah"); if (f) cout << f->name << ", " << f->something << ", " << f->another; </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