CODEWITHSUNDEEP
c++performanceinsertunordered-map
Chris
Chris

Reputation: 3688

How to (efficiently) insert into a map with a map as value?

I am writing a C++ program, to read from a big file line by line, and insert each line-info (after some processing) to an unordered_map.

This is the declaration of the unordered_map: 

unordered_map<int, unordered_map<int, int> > entries;

What I did to insert was (this is in the loop code-block in which I process each line of the text file):

unordered_map<int, int> tmp;
tmp[y] = z;
entries[x] = tmp;

But this proved to behave badly in performance terms.

I've tried creating a pair<int, pair<int, int>> and inserting it using entries.insert(the_pair) but I cannot get this to compile (getting: no matching member function for call to 'insert').

Edit:
The program looks like this: 

ifstream ifile(path-to-file);
string line;
unordered_map<int, unordered_map<int, int> > entries;
while (getline(ifile, line)) {
    // some processing with line to find (int) x and (int) y 
    if (entries.find(x) == entries.end()) {
        auto iter_and_success = entries.emplace(x, unordered_map<int, int>{});
        auto &tmp_m = iter_and_success.first->second;
        tmp_m[y] = 1;
    }
    else {
        unordered_map<int, int> r = entries[x];
        if (r.count(y) == 0)
            entries[x][y] = (int) r.size() + 1;
    }
}

Upvotes: 1

Views: 87

Answers (1)

Rostislav
Rostislav

Reputation: 3977

I think your best bet is simply move the child unordered_map to the parent one:

entries[x] = std::move(tmp);

This way you will avoid an extra copy of tmp.

Another way is to fill up the child map after inserting it.

 auto iter_and_success = entries.emplace(x, unordered_map<int, int>{});
 auto& tmp = iter_and_success.first->second;
 tmp[y] = z;

This way actually, you will append the data to the child map if x happens to occur multiple times (if this is unwanted behavior - just check the bool flag and act accordingly).

ifstream ifile(path-to-file);
string line;
unordered_map<int, unordered_map<int, int> > entries;
while (getline(ifile, line)) {
    // some processing with line to find (int) x and (int) y 

    // This will insert a new map only if x wasn't present
    auto iter_and_success = entries.emplace(x, unordered_map<int, int>{});

    // This will be 1 if a new map was inserted
    auto value_to_insert = static_cast<int>(iter_and_success.first->second.size()) + 1;

    // This will do anything only if y wasn't present in sub-map
    iter_and_success.first->second.emplace(y, value_to_insert);
}

Upvotes: 3

Related Questions