Searching for suitable data structure in c++

Question

Suggest a suitable data structure (in C++), such that the below mentioned purpose is solved:

insert an element to the end.
read and delete an element from the end.
read and delete an element from beginning.
find out if a particular element exists.

Right now i am using vectors..but finding if a particular element exists has a great time complexity in vectors as my elements are not sorted.

Is there some better data structure than vectors to accomplish this..if yes..then which one and please give an example.

If his problem is that searching a vector is too slow, how will deque help? — cgmb
– cgmb, Commented Jul 3, 2012 at 21:36
@Jannat : If searching is your only problem then say so. As it is, you listed four criteria, one of which is removing an element from the beginning. — ildjarn
– ildjarn, Commented Jul 3, 2012 at 21:38
@ildjarn I have listed all 4 criterion..that means all should be satisfied...not just the first or the last few — Jannat Arora
– Jannat Arora, Commented Jul 3, 2012 at 21:39
@Jannat : And I didn't post an answer, just a comment. Where does your entitlement come from? Look at Boost.MultiIndex. — ildjarn
– ildjarn, Commented Jul 3, 2012 at 21:41

vitaut · Accepted Answer · 2012-08-12 13:59:50Z

One possibility is to use std::set or std::unordered_set 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.

Here's a piece of code that illustrates the idea:

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); } // ... };

Sorry...i did not get the statement..."..it should be easy to implement on top of a set/unordered_set or map/unordered_map. I am a novice at this..so can you please explain by an example. And +1 for the answer..thanks for being helpful
@JannatArora: Sure, I added some code to illustrate the idea. Not the best piece of code ever, but hope it is simple enough. And it uses standard containers (set and deque) so no need to worry about implementing low level details like linked list yourself.

Fabio Ceconello · Accepted Answer · 2012-07-04 01:19:46Z

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.

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 std::map<K,V> 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.

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

To use it:

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;

Thanks a lot for answering..+1 for the answer...can u please give an example to illustrate...actually i am a novice, so it is a bit difficult for me to comprehend.
@FabioCeconello: caveat emptor => insert and delete do invalidate iterators on a deque, unless applied at either end.
Thanks for the heads up, @MatthieuM.; I'm assuming a well-behaved use of deque should only do that, but the use of smart pointers instead of iterators is a cleaner option anyway, IMO.

Ivan Vergiliev · Accepted Answer · 2012-07-03 21:45:52Z

You can keep the vector, but also use a std::set for fast queries.

The set is not enough for deleting an element from the beginning/end, as you don't really know which is the first/last element you've inserted. You could keep references to those elements, but then in order to support deletion, you would need the next ones and so on, which degrades back to using one more container.

jxh · Accepted Answer · 2012-07-03 22:08:57Z

You should start with a std::map to see if logarithmic complexity is suitable.

A B+Tree would be a bit more complex and would require your own implementation or research to find an open source implmentation. But it is a reasonable choice given the requirements and the pain point you cited (searching), if the std::map still proves inadequate.

You would map an element's value to its iterator in a std::list, for example. All operations would be O(lg n) with std::map.

score 0 · Accepted Answer · 2012-07-03 21:42:53Z

Use std::deque. This is a double-ended queue and it is also used as a container for standard interfaces such as std::stack.

It usually uses a quasi-linked list implementation and has amortized O(1) time complexity for insertions and deletions at edges.

Julien Lebot · Accepted Answer · 2012-07-03 22:00:01Z

If there is a lot of insert/delete a linked list would be more appropriate.
Beware that a linked list (single or double) will have quite an overhead (usually the size of a pointer, but implementation vary).

The standard template library offers you std::list.

Collectives™ on Stack Overflow

Searching for suitable data structure in c++

6 Answers 6

2 Comments

3 Comments

Comments

Comments

1 Comment

Comments

Hot Network Questions

Collectives™ on Stack Overflow

6 Answers 6

2 Comments

3 Comments

Comments

Comments

1 Comment

Comments

Related