C++ Multimap manipulation

Question

I have created a multimap as I have repeating keys. But I want do an efficient manipulation so that I can generate a new multimap with subsequent higher keys aligned. This is what I mean:

This is what I have:

key        values
11          qwer
11          mfiri
21          iernr
21          ghfnfjf
43          dnvfrf

This is what I want to achive

key        values
11          qwer,iernr
11          mfiri,iernr
21         iernr,dnvfrf
21          ghfnfjf,dnvfrf
43          dnvfrf

I have about 10 million entries so I am looking for something efficient.

In above value "qwer,iernr" is one string.

So the aim is for each entry `map[i]` to be suffixed with one of the values of `map[i+1]`, for all `i`? If that's not it, could you post some (pseudo)code that describes what you want, and then we can talk about making it efficient. — Oliver Charlesworth, Jan 18 '13 at 20:56
I just modified the tables in my original post so that it does not create confusion. So, I want to use the next higher key and not necessarily (i+1) key value if the current key is (i). Thanks! — Zanam, Jan 18 '13 at 21:05
Do you have to do new multimap creation once? Or every once in a while? And do you need to update original map after new one was created? (add/delete/modify values) — Eugene, Jan 18 '13 at 21:08
I can create multiple if I need to. There is no restriction on how many I can create. I have a PC with 6 GB ram. No I don't need to update it or rather I can generate a new multimap which hold the desired arrangement. — Zanam, Jan 18 '13 at 21:12

score 2 · Answer 1 · answered Jan 18 '13 at 21:55

Here's a simple way to do it:

auto cur = map.begin();
auto next = map.upper_bound(cur->first);

for(; next != map.end(); next = map.upper_bound(cur->first))
{
    for(; cur != next; ++cur)
    {
        cur->second += ", ";
        cur->second += next->second;
    }
}

... given a std::multimap<int, std::string> map;

However, any operation transforming 10m+ elements isn't going to be super fast.

score 0 · Accepted Answer · answered Jan 18 '13 at 21:48

Looks like straight-forward way would work fine. Map elements will be laid out in ascending order (assuming compare operator suits you). So just going through the equal ranges and modifying them with value of the element just after the range will do what you want.

Clone map (if you need the original), take first element, get equal_range() for its key, modify values with value of second iterator in the range (unless it is the last one). Get equal_range() for the key of second iterator. Repeat.

score 0 · Answer 3 · edited May 23 '17 at 10:28

0

agree with Eugene ! also see following reference in terms of equal_range() stl::multimap - how do i get groups of data?

edited May 23 '17 at 10:28

Community

1
1

answered Jan 18 '13 at 21:56

user1830108

195
1
15

score 0 · Answer 4 · answered Jan 18 '13 at 22:16

To do this, you need to simply iterate through the map, while building the new map in order.

You can do this in two levels:

for (auto it=map.cbegin(); it != map.cend(); ) 
{ 
    // The inner loop is over all entries having the same key
    auto next_key_it=find_next_key_after(it);
    for (; it != next_key_it; ++it) {
         new_map.emplace_hint(new_map.end(), it->first, new_value(it->second, next_key_it));
    }
}

The new_value function (or lambda) does the value transformation (or not, if the second parameter is map.end()).

The find_next_key_after(it) function returns the same as map.upper_bound(it->first), but could also be implemented as linear search for the first entry with different key.

It depends on your (expected) key distribution, which to use - if keys repeat a small, limited number of times, linear search is better; if the number of different keys is limited, with large equal key ranges, then upper_bound may be better.

For guaranteed complexity, linear search is better: The whole algorithm then has O(n) complexity. Which is as efficient as you can get.

C++ Multimap manipulation

4 Answers4