Inserting into a map or set has the same type of performance, because they keep their elements sorted, so I will treat them identically; inserting requires finding the insert position (
logn - logarithmic), and inserting.
Reference
Similarly, a find operation is
logn for both.
A task: add a list of elements, probably with many duplicates, to a set or a map. So the first question one might ask, as I did, without proper knowledge: is it faster to insert each, or to check if they exist before inserting?
12 | for each element in list:
insert into set;
|
or
123 | for each element in list:
if not exists in set:
insert into set;
|
Inserting into a map is faster using value_type than std::pair.
Here are four common ways to insert into a map:
std::map m;
- m[0] = 100;
- m.insert(std::pair<int, int>(0, 100));
- m.insert(std::make_pair(0, 100));
- m.insert(std::map<int, int>::value_type(0, 100));