Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the most efficient std container for non-duplicated items?

What is the most efficient way of adding non-repeated elements into STL container and what kind of container is the fastest? I have a large amount of data and I'm afraid each time I try to check if it is a new element or not, it takes a lot of time. I hope map be very fast.

// 1- Map
map<int, int> Map;
...
if(Map.find(Element)!=Map.end()) Map[Element]=ID;

// 2-Vector
vector<int> Vec;
...
if(find(Vec.begin(), Vec.end(), Element)!=Vec.end()) Vec.push_back(Element);

// 3-Set
// Edit: I made a mistake: set::find is O(LogN) not O(N)
like image 857
Roy Avatar asked Jan 22 '13 23:01

Roy


People also ask

Which containers do not allow duplicates?

A Set is a Collection that cannot contain duplicate elements.

What are the three categories of containers?

The three types of containers found in the STL are sequential, associative and unordered.

Which of these containers are used for finding unique values efficiently?

Container library as flat_set .

Which STL collection guarantees the uniqueness of the stored content?

set::begin() and set::end() in C++ STL. Sets are a type of associative container in which each element has to be unique because the value of the element identifies it.


1 Answers

Both set and map has O(log(N)) performance for looking up keys. vector has O(N).

The difference between set and map, as far as you should be concerned, is whether you need to associate a key with a value, or just store a value directly. If you need the former, use a map, if you need the latter, use a set.

In both cases, you should just use insert() instead of doing a find().

The reason is insert() will insert the value into the container if and only if the container does not already contain that value (in the case of map, if the container does not contain that key). This might look like

Map.insert(std::make_pair(Element, ID));

for a map or

Set.insert(Element);

for a set.

You can consult the return value to determine whether or not an insertion was actually performed.


If you're using C++11, you have two more choices, which are std::unordered_map and std::unordered_set. These both have amortized O(1) performance for insertions and lookups. However, they also require that the key (or value, in the case of set) be hashable, which means you'll need to specialize std::hash<> for your key. Conversely, std::map and std::set require that your key (or value, in the case of set) respond to operator<().

like image 165
Lily Ballard Avatar answered Jan 01 '23 11:01

Lily Ballard