C++ std::map, rotation of keys

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.

---

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));

---

It's an amusing problem, but more about algorithms than data structures.

I'd note that Map^i[n] can be solved in constant time... if instead of modifying the structure you tweak the access.

From my understanding of the problem, the values simply "cycle": [15, 20, 12, 18] -> [20, 12, 18, 15] -> [12, 18, 15, 20] -> [18, 15, 20, 12]

Formula:

• let N be the size of the sequence - 1 and n in [0, N] an index in the sequence
• let i in [0, N] be an iteration
• Value^i[n] = Value[n+i%(N+1)]

The keys are different though:

• [0.5, 1, 2.3, 3.7] -> [0.5, 1.8, 3.2, 3.7] -> [1.3, 2.7, 3.2, 3.7] -> [1.4, 1.9, 2.4, 3.7]
• Let's try to see a pattern: [a, b, c, d] -> [b-a, c-a, d-a, d] -> [c-b, d-b, d-b+a, d] -> [d-c, d-c+a, d-c+b, d]

Make the pattern more pronounced:

0: [a    , b      , c      , d      , e      , f]
1: [b-a  , c-a    , d-a    , e-a    , f-a    , f]
2: [c-b  , d-b    , e-b    , f-b    , f-(a-b), f]
3: [d-c  , e-c    , f-c    , f-(a-c), f-(b-c), f]
4: [e-d  , f-d    , f-(a-d), f-(b-d), f-(b-e), f]
5: [f-e  , f-(a-e), f-(b-e), f-(c-e), f-(d-e), f]

Note that this is also cycles, somewhat, since applying the transformation once more would yield the original sequence.

Formula (we reuse the previous variables):

Key^i[n] = | n = N    => Key[N]
           | i = 0    => Key[n]
           | n <= N-i => Key[n+i] - Key[i-1]
           | n >  N-i => Key[N] - (Key[n+i % (N+1)] - Key[i-1])

The latter 3 lines can be aggregated in (Key[n+i % (N+1)] - Key[i-1]) % Key[N], if we define (arbitrarily) Key[-1] = 0.

Now that we have our formulas, we need a structure with Random Access, I'll simply pick a vector.

Compilable example provided below (or see ideone), gives:

[ 0.5: 15, 1: 20, 2.3: 12, 3.7: 18 ]
[ 0.5: 20, 1.8: 12, 3.2: 18, 3.7: 15 ]
[ 1.3: 12, 2.7: 18, 3.2: 15, 3.7: 20 ]
[ 1.4: 18, 1.9: 15, 2.4: 20, 3.7: 12 ]

Example:

#include <cassert>
#include <algorithm>
#include <iostream>
#include <vector>

typedef std::pair<double, double> Pair;
typedef std::vector<Pair> Vector;

double key(Vector const& vec, size_t const i, size_t const n) {
  assert(n < vec.size() && "Wrong index");
  if (i == 0) { return vec[n].first; }

  size_t const N = vec.size() - 1;

  if (n == N) { return vec.back().first; }

  double const partial = vec[(n+i) % (N+1)].first - vec[(i-1) % (N+1)].first;
  return (n <= N-i) ? partial : partial + vec[N].first;
} // key

double value(Vector const& vec, size_t const i, size_t const n) {
  assert(n < vec.size() && "Wrong index");
  return vec[(n+i) % vec.size()].second;      
} // value

int main() {
  Vector vec{ Pair(0.5, 15), Pair(1, 20), Pair(2.3, 12), Pair(3.7, 18) };
  sort(vec.begin(), vec.end()); // just to be sure

  size_t const size = vec.size();
  for (size_t i = 0; i != size; ++i) {
    std::cout << "[ ";
    for (size_t n = 0; n != size; ++n) {
      if (n != 0) { std::cout << ", "; }
      std::cout << key(vec, i, n) << ": " << value(vec, i, n);
    }
    std::cout << " ]\n";
  }
}

---

Rotating values and keeping keys

One possibility is to use deque as mentioned by @Eugene. Then, of course, you do not have the fast O(log n) access to the keys. If you want to keep the map then the following would be possible to "rotate" the map m by n rounds:

void rotate(map<double, double>& m, int n) {
    vector<double> values(m.size());
    int j = 0;
    for (map<double, double>::const_iterator i = m.begin(); i != m.end(); ++i, ++j) {
        values[j] = (*i).second;
    }
    j = n;
    for (map<double, double>::iterator i = m.begin(); i != m.end(); ++i, ++j) {
        m[(*i).first] = values[j % m.size()];
    }   
}

If you want to rotate several times by various number of rounds then you could make the vector values global and fill it only once. Also, it should be considered that rotating by n1 and then by n2 equals the rotation by n1 + n2. So, e.g. to get all rotations you would call:

rotate(m, 1);
rotate(m, 1); // 1 again
...

Just a remark: it is rather problematic to use doubles as keys.

Rotating values and changing keys (edited)

In this case a completely new map needs to be constructed as @abcdef already does. However, it seems that the new keys are not defined properly in the question. The keys k1, k2, ..., kn are transformed to k2-k1, k3-k1, ..., kn-k1, kn. We get duplicate keys if e.g. k[n-1] - k1 = kn, as when transforming (-1, 2, 5, 6) to (3, 6, 7, 6).

---

I assumed that std::map is based on tree structure and its elements have an ascending order. Described rotation operation does not change relative key positions. So key changes should not brake the map structure. I've created rotate function that modifies key values. It seems to be bad practice, still it works on both msvs and gcc.

typedef std::map<double,double> Map;
typedef Map::iterator MapIter;

void rotate( Map &m ) {
    if ( m.empty() ) return;
    MapIter prev, iter = m.begin(), max_iter = m.end();
    Map::key_type rem_key = iter->first;
    Map::mapped_type rem_val = iter->second;
    for( prev = iter++; iter != max_iter; prev = iter++ )  {
        Map::key_type *key = const_cast<Map::key_type*>(&prev->first);
        *key = iter->first - rem_key;
        prev->second = iter->second;
    }
    prev->second = rem_val;
}

EDIT: described rotation operation does not change related keys positions only in case all keys are nonnegative. In other case my algorithm modifies the map structure incorrectly and thereby cannot be used.

---

Here is another idea.

Use two data structures instead of one. Keep the values in a list<double>, and represent your map as map<double, list<double>::iterator>.

That is, map from double keys to iterators (i.e. pointers) into the value list.

Also keep track of how many rotations you have performed total; call it k. To perform a lookup, look up the key in the map, add k to the iterator, and dereference it. (Yes, this is O(k).) Also, for this to work, you need a circular linked list; or more easily, implement your own march through the list that handles wrap-around.

Note that in general, you do not rotate the list itself; you just increment k. All of the cost is incurred during lookup.

Note that insertions are still O(log n) since inserting in a list does not invalidate its iterators, and you can obtain the location to insert into the list in O(log n) time from the map.

Now here is the original bit. When k reaches sqrt(n), then you actually rotate the list to reset k to zero. This operation is O(n), but you only do it once every O(sqrt(n)) rotations... Meaning the amortized (i.e. average) cost of your rotate operation is also O(sqrt(n)). And k is never greater than sqrt(n), so lookups are also O(sqrt(n)).

Thus, this formulation provides:

Insert: O(log n) Delete: O(log n) Lookup: O(sqrt(n)) Rotate: O(sqrt(n))

Which you might or might not consider better than the other suggestions, but at least it's different...

Also with this formulation you can trade off lookup for rotation speed. For example, if you do the "reset" operation when k reaches log n, your rotations will take O(n / log n) on average but lookups will still be O(log n). (Most of the other proposals here either have rotations taking O(n) or insertions taking O(n), so this version beats those... Although only by a factor of log n.)

---

I read your comment but I still felt like providing an answer and show how it can be done by using the original map. So, here's the code:

#include <map>
#include <iostream>
#include <utility>

int main() {
    std::map <double, double> test;

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

    std::pair<double, double> first = *test.begin();
    test.erase(test.begin());
    std::map<double, double>::iterator i = test.begin();
    while ( i != test.end() ) {
        test[i->first - first.first] = i->second;
        std::map <double, double>::iterator prev = i;
        ++i;
        test.erase(prev);
    }
    test[test.rbegin()->first + first.first] = first.second;

    for ( i = test.begin(); i != test.end(); ++i ) {
        std::cout << "test[" << i->first << "] = " << i->second << "\n";
    }
}

A few notes:

• std::map keys cannot be modified, so you have to remove old elements and insert new ones;
• The problem statement guarantees that the newly inserted elements will not overwrite existing ones;
• Removing elements from a map doesn't invalidate iterators that do not point to removed elements.

---

You can do rotation in O(log N)

#include<map>

using namespace std;

map<double, double> m;
double diff; //the keys in m are actually diff bigger then in needed map

void rotate()
{
     double savedValue = m.begin()->second;
     double removedKey = m.begin()->first - diff;//save the value of first element
     m.erase(m.begin()); //erase first element
     diff += removedKey; //do the (key -=) thing
     m[m.rbegin()->second + removedKey] = savedValue;//add new value
}

//dont need to do this, just remember that key = storedKey - diff
map<double, double> getMap()
{
        map<double, double> res;
        for(map<double, double>::iterator it = m.begin(); it != m.end(); ++it)
                m[it->first-diff] = it->second;
        return res;
}

---

I note that, as long as keys are neither added nor removed from the map by any other means, it is possible to keep track of the key changes during rotation.

First of all, note that the largest key in the map never changes.

Now notice that, except for key values that get "wrapped round" from one extreme of the map to another, you can summarise the effect of the rotations by keeping track of the total value of the keys that are subtracted.

Look what happens to the smallest key - you can imagine that it is subtracted by itself, to produce a value of zero. But now we decide that the value 0 is too small to put up with, and just like modular arithmetic, we can add a modulus to it to bring it back into range. That value is the (unchanging) largest key in the map. So the rule for predicting keys forwards, is to subtract the sum of all the smallest keys dealt with so far, and then add the largest key value as many times as is required to bring the value into range. Similarly, the rule for deducing keys backwards will be to subtract the sum of all the smallest keys dealt with so far, and then to add the largest key value as many times as is required to bring the value into range.

Using this, you should be able to allow users to rotate the map and to look up key values at O(1) cost, only having to handle the O(n log n) - (or possibly O(n) depending on how tricky and careful you want to be) job of rewriting the map when they add or remove key values.

I think that looking up values by order index (e.g. 1st value, 2nd value, 3rd value) is the same principle - keep track of a value to add or subtract that accounts for the total rotation so far, and add or subtract the total number of items in the map to bring things back into range.

---

If after rotations you only need to perform lookups effectively then you should go for Matthieu's solution. In his excellent answer he only forgot that rather than Key^i[n] you need an inverse of that function ie given some value k and number of rotations i what will be the rank (index) n of key k after i rotations (if such a key exists).

I don't think the inverse function can be found in analytical terms and computed in O(1) the way Key^i[n] was, but you can do effective lookups in O(log n) time using a binary search.

double get(Vector const& vec, size_t const i, double key) {
    assert(n < vec.size() && "Wrong index");
    size_t rank = binarySearch(vec, i, 0, vec.size()-1, key);
    if (rank < 0) {
        // not found, return NaN or something
    }
    return vec[rank].second;    
}

size_t binarySearch(Vector const& vec, size_t const i, size_t const low, size_t const high, double value) {
    if (high < low)
        return -1; // not found
    mid = low + (high - low) / 2;
    if (key(vec, i, mid) > value)
        return binarySearch(vec, i, low, mid-1, value);
    else if (key(vec, i, mid) < value)
        return binarySearch(vec, i, mid+1, high, value);
    else
        return mid; // found
}

This solution gives you O(1) rotations (you only need to increment rotations counter and remember it) and O(log n) lookups. If you want to modify the map (like insert a new element) you'd have to reset the whole map using the getMap() function, this takes O(n) time.

So if you need to do effectively lookups and insertions (removals, etc) after rotations then you should stick to kilotaras' solution, which gives you uniformly O(log n) time for all the operations including rotations, lookups and modifications.