使用stl::map的std::map旋转方法或算法

Question

iam正在开发一个类，该类内部包含一个std:：map，到目前为止，函数性是最优的，但现在我有一个旋转映射的要求，我的意思是旋转映射元素id以及与这些值对应的值的变化顺序，例如：

给定：

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

应用旋转算法一次：

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

再次应用旋转算法：

好吧，我的第一个意图是编写一个执行此操作的算法，但我对c++很陌生

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

我在stl-libs中有一个我现在看不到的合适的解决方案吗？thx

Answer 1

否。

地图元素的顺序不是您可以控制的。它是固有的，基于排序键。

当然，您可以提供自己的比较器来操作容器的基本顺序。

但是，您应该而不是依赖映射中的顺序。它不是一个序列容器，也不是为使用order作为属性而设计的。

与其"旋转"，为什么不每次在容器中的不同位置开始迭代，并"环绕"呢？

Answer 2

我认为您可能混淆了"映射"one_answers"存储"。从数学（或算法）的意义上讲，如果你将一个键"映射"到一个值，那么这就是一对一的映射，直到它被更改，当你查找该键时，你总是会得到那个值。它实际上是如何工作的，也不重要用于实现映射的任何对象是否已经"旋转"。查找一个密钥，获取值。在你的情况下，在旋转之前或之后，例如，如果你查找"12"，你总是会得到2。你明白我在说什么吗？在这里点菜，没关系。因此，如果您使用STL中的std:：map，您将失去对元素存储顺序保证的控制。

现在，您所要求的与实现有关，特别是与元素的存储方式有关，因此您需要的是一个保证顺序的STL容器。一个这样的容器是向量。在我看来，你可能想要的可能是一个成对的向量。像这样的东西会起作用：

#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;
}

但是，请注意，因为您使用的是向量，所以它不会保护您添加重复的对或具有不同键但具有相同值的对，反之亦然。如果要保持一对一映射，则必须确保在中插入元素时，"键"one_answers"值"不会在矢量中的其他位置重复。在阅读了std:：vector的工作原理之后，您应该很容易理解这一点。

Answer 3

扩展Lightness的答案，我认为这是正确的答案。如果你不想更多地控制你的地图，你应该使用static matrix。

矩阵使用简单的数学提供了更多的旋转选项，而不是您试图实现的cyclical旋转。