Which datastructure to use for finding an element

Question

I have several items saved in a list. I would like to add items that have already been processed to a datastructure (this makes sense in my case even though you might wonder why). When processing the next item from the list I first want to make sure if it has been processed before so lets say something like this:

if(element_is_in_datastructure(current_element)) {
   do this
}
else
{
   do that
   add_element_to_datastructure(current_element)
}

My question is, what is the ideal datastructure where checking if the element is in it won't take too long. At the moment I don't have too many elements (max 30) which will be added to the datastructure, but this number might increase and I don't want to lose performance.

You probably want to use `std::set` or `std::map`. – Piotr Siupa May 28 '18 at 07:31 — Piotr Siupa, May 28 '18 at 07:31

Hello Everyone · Accepted Answer · 2018-05-28T07:37:29.603

1

You can use a map e.g std::unordered_map to store your elements as keys. Then just check their presence e.g

if(!yourMap.count(element))
{
   // your element is not in the structure
}

This finding takes logarithmic time in the map's size to finish.

edited May 28 '18 at 07:37

answered May 28 '18 at 07:32

Hello Everyone

329
4
11

1

It is not constant time. It is logarithmic. – Piotr Siupa May 28 '18 at 07:34
Thanks, I edit it ^^ – Hello Everyone May 28 '18 at 07:36
If all you need is a set of elements, then perhaps `std::set` is a better option, much like the map it's stored in a tree, but only stores the 1 element and not a pair, which you don't need. – Qubit May 28 '18 at 07:44
1

May be fix it again? Logarithmic for map, constant for unordered_map and unordered_set? – Vlad Feinstein Jun 04 '18 at 20:53
It is constant for best-case and linear for worst-case scenarios, so logarithmic time seems conclusive for it. =]] – Hello Everyone Jun 05 '18 at 07:54

Which datastructure to use for finding an element

1 Answers1