0

我正在开发一个内部包含 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 库中有一个我现在看不到的正确解决方案吗？谢谢

4

3 回答 3

4

不。

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

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

但是，您不应该依赖地图中的顺序。它不是一个序列容器，而且根本不是为您设计的，可以将 order 用作属性。

而不是这种“旋转”，为什么不每次都在容器中的不同位置开始迭代，然后“环绕”呢？

于 2013-08-14T20:55:41.553 回答
1

我认为您可能会将“映射”与“存储”混淆。在数学（或算法）的意义上，如果你将一个键“映射”到一个值，那么这是一对一的映射，直到它被改变，当你查找那个键时，你总是会得到那个值。它实际上如何工作或用于实现地图的任何对象是否已“旋转”都无关紧要。查找键，获取值。在您的情况下，在旋转之前或之后，例如，如果您查找“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;
}

但是请注意，由于您使用的是向量，因此它不会保护您免于添加重复的对或具有不同键但值相同的对，反之亦然。如果要保持一对一的映射，则必须确保在插入元素时，“键”和“值”不会在向量中的其他任何地方重复。在阅读了一些关于std::vector 的工作原理之后，这应该很容易让您弄清楚。

于 2013-08-14T21:22:46.983 回答
0

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

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

于 2013-08-14T21:08:21.023 回答