C++ std::map, rotation of keys

Question

I need to implement something like "first key rotation" in map. A more detailed explanation of the problem. There is a map:

std::map <double, double> test;

The following elements are inserted:

test[0.5] = 15;
test[1] = 20;
test[2.3] = 12;
test[3.7] = 18

The rotation algorithm could be rewritten as:

a] Remember first element in map (element with the lowest key): rem_el = map[0] //Symbolic notation

b] Remove first element from map

c] Set new keys for all remaining elements in map:

map[i].key = map[i].key - rem_el.key

d] Add remembered key to the map with the new key: the sum of the last key and remembered key

test[rem_el.key + test[n-1].key] = rem_el.value

First rotation:

test[0.5] = 20;
test[1.8] = 12;
test[3.2] = 18;
test[3.7] = 15;

Second rotation:

test[1.3] = 12;
test[2.7] = 18;
test[3.2] = 15;
test[3.7] = 20;

There are n-1 rotation for such a map...

How to implement this operation as much as efficient (map with thousands of items)? I used list of all keys and another temporary map created from the rotated list, but this procedure is probably not optimal.

I could ask for some code samples? Thanks.

Answer 1

Looks like you need a deque of pairs, not a map:

std::deque<std::pair<double, double> > test;

You have to keep it sorted yourself if it's needed. Then it is all straightforward:

std::pair<double, double> rem_el = test.front();
test.pop_front();
for (std::deque<std::pair<double, double> >::
     iterator it = test.begin(); it != test.end(); ++it)
{
    it->first -= rem_el.first;
}
assert(!test.empty());
test.push_back(std::make_pair(rem_el.first + test.back().first, rem_el.second));