CODEWITHSUNDEEP
c++stlcontainers
Sampath
Sampath

Reputation: 1202

Ordered inserts to stl::map faster?

As the stl::map is an ordered map, will it be quicker to insert a sorted data-set? Specially if we consider a large data-set?

Upvotes: 1

Views: 102

Answers (2)

Jason L.
Jason L.

Reputation: 741

Yes, that's true. From the perspective of big O, inserting N elements one by one is O(N*logN), in comparison, building a map(usually some kind of balanced binary tree) only requires O(N).

You can also take GCC's libstdc++ implementation as a reference.
gcc/libstdc++-v3/include/bits/stl_map.h

Upvotes: 1

user2249683
user2249683

Reputation:

Sure, having sorted data.

#include <map>
#include <vector>

int main() {
    std::vector<int> data { 0, 1, 2, 3, 4, 5 };
    std::map<int, int> result;
    // From: http://en.cppreference.com/w/cpp/container/map/insert
    // Amortized constant if the insertion happens in the position just before
    // the hint, logarithmic in the size of the container otherwise.
    for(auto i : data)
        result.insert(result.end(), { i, i} );
}

Upvotes: 3

Related Questions