CODEWITHSUNDEEP
c++algorithmdata-structurescollections
SilverWarrior
SilverWarrior

Reputation: 55

Correct data structure for fast insert and fast search?

I have an array and I need to insert items there as fast as possible. Before adding an item I need to see if it exists, so I do a full array scan. I can't use binary search since I can't sort the array after every insert.

Is there a more efficient data structure for this job?

Edit: On that array I store strings. Next to each string I store a 4 byte hash. I first compare the hashes and if they are the same then the string.

Upvotes: 1

Views: 5131

Answers (1)

Alexei Levenkov
Alexei Levenkov

Reputation: 100620

std::unordered_map usually implemented as (hashtable) will give you best insert/search time (O(1)) but does not preserve nor provide any order.

std::map gives you O(log(n)) for search and insert as it requires particular ordering (not the one you got to insert items so) and usually implemented with balanced tree.

Custom balanced search trees are another option if you need sorted order and fast (O(log n)) insert/search.

Sorted std::vector (to support ability to add items) is another option if O(n) is acceptable insert time but you need smallest memory footprint and O(log n) search time. You'd need to insert items in sorted order which is O(n) due to need to copy the rest of the array.

If you need to preserve original order you stuck with O(n) for both insert/search if you are using just an array ('std::vector').

You can use separate std::unordered_map/std::unordered_set in addition to 'std::vector' to add "is already present" check to gain speed at price of essentially 2-3x memory space and need to update 2 structures when adding items. This array+hashtable combination will give you O(n) insert and O(1) search.

Upvotes: 3

Related Questions