std::map rotate method or algorithm using stl::map

Question

iam developing a class that inside holds an std::map, by now the funcionality was optimal, but now i have a requirement to rotate the map, i mean by rotate change order in wich the map elements id besides the values corresponding to those values , by example:

Given:

Map[122]=1
Map[12]=2
Map[3]=45

applyng the rotation algorithm once:

Map[12]=2
Map[3]=45
Map[122]=1

applyng the rotation algorithm again:

Well, my first intention is write a algoritm that perform this operation, but i new in c++

Map[3]=45
Map[122]=1
Map[12]=2

Do i have a proper solution in stl libs that i cannot see by now¡? thx

score 4 · Answer 1 · answered Aug 14 '13 at 20:55

4

No.

The order of map elements is not something you control. It's inherent, based on sort key.

Sure, you can provide your own comparator in order to manipulate the underlying order of the container.

However, you should not be relying on order in a map. It is not a sequence container, and is simply not designed for you to use order as a property.

Instead of this "rotating", why not begin your iteration at a different place in the container each time, and "wrap-around"?

answered Aug 14 '13 at 20:55

Lightness Races in Orbit

378,754
76
643
1,055

that is an idea, i was thinking in a containner that holds the primary key an use it to alter the iterator of the map, in other words a containner that is in sync with the map and knows how to rotate properly – Ricardo_arg Aug 14 '13 at 21:10
@Ricardo_arg http://stackoverflow.com/q/2616643/560648 But I'd **really** consider re-thinking this requirement. Why do you think you need to do this? Try to make it so that you don't. Perhaps what you _really_ need is a `boost::circular_buffer>`. – Lightness Races in Orbit Aug 14 '13 at 21:11
i cannot use boost library :( – Ricardo_arg Aug 14 '13 at 21:16
@Ricardo_arg: Yes, you can. – Lightness Races in Orbit Aug 15 '13 at 09:13

Carl · Accepted Answer · 2013-08-14T21:28:44.327

I think you might be confusing "mapping" with "storage". In a mathematical (or algorithmic) sense, if you "map" a key to a value, then that is a one to one mapping and until it has been changed, when you look up that key, you will always get that value. It doesn't matter yet how it actually works or whether whatever object is used to implement the map has been "rotated" or not. Look up a key, get the value. In your case, before or after rotation, if you look up "12" for example, you will always get 2. Do you see what I'm saying? Order here, doesn't matter. Therefore, if you use std::map from the STL, you lose control over guarantees on the order in which the elements are stored.

Now, what you're asking has to do with the implementation and in particular, with how the elements are stored, so what you need is an STL container that guarantees order. One such container is a vector. It seems to me that what you might want is probably a vector of pairs. Something like this would work:

#include <vector>
#include <map> //for std::pair
#include <iostream>
#include <algorithm> //for std::rotate

typedef std::pair<int,int> entry;
typedef std::vector<entry> storage;

void print( const char* msg, const storage& obj )
{
    std::cout<<msg<<std::endl;
    for(auto i : obj)
    {
        std::cout << i.first << "," << i.second << std::endl;
    }
}

void lookup(int key, const storage& obj)
{
    for(auto i : obj)
    {
        if( i.first == key )
        {
            std::cout<<"\t"<<key<<"=>"<<i.second<<std::endl;
            return;
        }
    }
    std::cout<<key<<"not found"<<std::endl;
}

int main()
{
    storage mymap = {entry(122,1),entry(12,2),entry(3,45)};
    print("Before rotation", mymap);
    lookup(12,mymap);
    std::rotate(mymap.begin(),mymap.begin()+1,mymap.end());
    print("After one rotation", mymap);
    lookup(12,mymap);
    std::rotate(mymap.begin(),mymap.begin()+1,mymap.end());
    print("After one more rotation", mymap);
    lookup(12,mymap);
    return 0;
}

Note, however, that because you're using a vector, it will not protect you from adding duplicate pairs or pairs with different keys but the same value and vice versa. If you want to maintain a one to one mapping, you will have to make sure that when you insert elements in, that the "key" and the "value" are not repeated anywhere else in the vector. That should be pretty easy for you to figure out after some reading on how std::vector works.

score 0 · Answer 3 · answered Aug 14 '13 at 21:08

To extend Lightness's answer, which I believe is the correct one. If you wan't more control over your map you should use a static matrix instead.

Matrices provide many more rotational options using simple math, instead of the cyclical rotation you're trying to implement.

std::map rotate method or algorithm using stl::map

3 Answers3