使用std::map时，以下做法是否合适？

Question

我对使用 std::map 有一些问题：

1. Is using an enum as the key in std::map a good practice? Consider the following code:

   enum Shape{
       Circle,
       Rectangle
   };
   
   int main(int argc, char* argv[])
   {
        std::map<Shape,std::string> strMap;
        // strMap.insert(Shape::Circle,"Circle"); // This will not compile
        strMap[Shape::Circle] = "Circle";         // But this will work
        return 0;
   }
   

2. In the above example, why is the call to insert() generating a compiler error while the overloaded [] operator works correctly? Which of these methods is recommended for inserting items into a std::map?

3. I understand that when the find() method is used on the std::map class, it is not doing a sequential search in the container but doing some logarithmic search which will be much faster than sequential search. Is this understanding correct?

- Appu

Answer 1

1. 将枚举类型作为键并不是一件坏事。(修改) 但如果你只使用连续的枚举值，那么使用具有O(1)访问时间复杂度的std::vector会更好。
2. insert应该像这样使用：mapVar.insert(make_pair(key, value)); 参见cppreference.com。
3. 是的，std::map具有O(log(n))的查找时间复杂度，这是由标准保证的，如果n足够大，则比O(n)更快。

- gimpf

---

关于您的编辑，我不太清楚。想象一下形状增长到七个：圆形、矩形、三角形、蛋形等等。然后您有一个类Piece，它有一个“形状”变量，并希望访问相关值。使用映射会更快。 - Daniel Daranas

给丹尼尔：正如家长所提到的，由于其O(logn)与向量的常数时间相比，地图会更慢。 - Iraimbilanja

是的，但也许我忽略了什么。使用map的整个意义在于你拥有一个键，并搜索与其相关联的值！我知道键为Circle，并想要在map中访问"Circle"，但是我无法通过使用vector来做到这一点。我可以创建一个键的向量和一个值的向量，但无法进行查找操作。 - Daniel Daranas

给丹尼尔 - 您可以这样索引vector<string>：vec[Triangle]，因为枚举可以转换为整数。 - Iraimbilanja

枚举类型是一个整数类型，因此您可以将其用作向量的索引（=键），而无需进行任何搜索。这对于其他键类型不起作用，并且仅在枚举值连续时才有效（而不是位图的值，如2/4/8/16等），并且在空间方面工作得比较合理。 - gimpf

有趣的技巧。我之前没有想过利用默认转换和枚举键从0开始的默认值。 - Daniel Daranas

Answer 2

插入失败，因为value_type是std::pair

- Alan

---

为什么这个被投票否决了？map 的值类型是 std::pair。你们这些人真刻薄！ - Alan

Answer 3

1）在std :: map中将枚举保留为键是一个好习惯吗？

对于效率而言，对于这样的小枚举，最好使用值的vector或tr1 :: array（如果您的值类型支持'empty'值）或智能指针。例如：vector<string>

对于正确性 - 我认为你没问题。 Map可以使用任何可排序的键类型 - 即具有operator<或为其提供排序函数的类型。枚举默认具有排序功能。

2）在strMap.insert（Shape :: Circle，“Circle”）中，为什么insert方法会[给出]编译器错误？

因为insert不接受两个值。它需要一对pair。尝试：

#include <utility>
...
strMap.insert(make_pair(Circle, string("Circle")));

3) 利用map类的find()方法时，它会执行一些对数搜索 ... 对吗？

是的。map::find的时间复杂度为O(lg(map::size()))。map将其键值对存储在按照键排序的数据结构中。插入和删除的时间复杂度为O(lg(n))，查找同样如此。此外，它还提供双向迭代器，这意味着您可以在O(1)常数时间内找到地图中的下一个或上一个项目，但不能一次向前或向后跳过超过一个元素。

编辑：更正了枚举类型默认具有排序功能。

- Aaron

---

既然枚举类型是整数，你真的需要提供排序吗？我认为不需要。 - Konrad Rudolph

你不能有一个 vector<Shape, string>。但你可以拥有一个包含 vector<Shape> 和 vector<string> 的向量。对于键值查找，你 必须 使用 map。 - Daniel Daranas

@Daniel -- vector<string> 是一种关联数据结构。它将顺序无符号整数映射到值。枚举是无符号整数，并且默认情况下是连续的。请参见gimpf答案上的注释。 - Aaron

@Aaron，我已经阅读并同意它们。我所指的是第3行中提到了“vector<Shape，string>”这一事实。 - Daniel Daranas

@Daniel：哎呀，那个怎么出现了？思维漏洞已经修复了。 - Aaron

Answer 4

尝试使用

strMap.insert(std::pair<Shape, std::string>(Circle,"Circle"));

使用 instead（而不是 Shape::Circle！）。

在 C++ 中，枚举值与其所在的枚举作用域可见（非常丑陋，我绝对不喜欢，但事实就是如此！）

- rstevens

Answer 5

在像这样的情况下，通常只需要将枚举静态映射到字符串，因此可以更轻松地执行以下操作：

enum Shape{
    Circle,
    Rectangle,
    NShapes,
};

char *ShapeNames[] = 
{  
    "Circle",
    "Rectangle",    
};

void CheckShapeNames()
{
    // Use a static_assert here instead if you have it in your library
    int ShapeNamesCount[(sizeof(ShapeNames)/sizeof(char*)) == NShapes];
}

从那时起，访问形状名称只是访问ShapeNames数组的简单问题：

string name = ShapeNames[Shape::Circle];

或者甚至：

for (int i=0; i < Shape::NShapes; ++i)
{
    cout << ShapeNames[i];
}

- Josh