c++ - 使用 std::vector 作为 std::map 的键在未找到和使用 reserve() 时不返回 end()

Question

我在一个程序中使用 c++ STL Map 和 Vector 类，其中我有一个将 vector 作为指向整数的键的映射。通常在 map 中搜索值时，如果未找到该值，myMap.find() 将返回 myMap.end()。

当我尝试使用 myVector.reserve(int) 在我的 vector 中预分配空间(以防止在我使用它们时不断调整大小)时，我的麻烦就来了。出于某种原因，在我的 map 中搜索一个我知道不存在的 vector 时，当我搜索的 vector 已分配空间时，将不会返回 myMap.end()，无论我是否实际填充该 vector (示例 1)。

但是，当 vector 不在 map 中时(示例 2)，只需将对象插入我希望搜索的 vector 中即可为我提供正确的 myMap.end() 位置。

示例 1:

#include <map>
#include <vector>
#include <iostream>

using namespace std;

int main(){

 vector<int> v, v1;
 v.reserve(1);
 v1.reserve(1);
 v[0] = 1;
 v1[0] = 2;
 map<vector <int>, int> m;

 m.insert(make_pair(v, 0));

 cout << int(m.find(v1) == m.end());
}

返回 0

示例 2:

#include <map>
#include <vector>
#include <iostream>

using namespace std;

int main(){

 vector<int> v, v1;
 v.reserve(1);
 v[0] = 1;
 v1.push_back(5);
 map<vector <int>, int> m;

 m.insert(make_pair(v, 0));

 cout << int(m.find(v1) == m.end());
}

返回 1

我希望能够在我的 vector 中保留一定量的空间，但似乎让 map 如图所示工作的唯一方法是即时插入元素并动态调整 vector 大小。这样对吗？有什么解决方法吗？谁能解释这种(明显的)异常行为？

Answer 1

首先，这段代码并不像您想象的那样。 reserve() 不会调整大小()。

vector<int> v;
v.reserve(100);
v[0] = 1;  //undefined
cout << v.size(); //prints 0

再编辑一下:我意识到这实际上是“预期的”行为，因为在第一种情况下，v 和 v1 都是空 vector ，因为 reserve 不影响 ==、<= 的语义等。一旦您了解 reserve 实际上除了将段错误变成令人困惑的行为之外什么都不做，这应该是有道理的。我建议永远不要使用保留，直到你证明它会产生性能差异(过早优化)。

我对 <= 和 => 的描述以及您在这里可能不需要的 map ，但将其留作引用，因为它仍然可能会影响您解决此问题的工作。

其次， map 不关心事物是否==。他们关心事物是否在两个方向上 <= - 这个词是“等价的”。例如

Foo foo1(1);
Foo foo2(2);

map<Foo, int> m;
m.insert(makepair(foo1, 1));
m.find(foo2) == m.end(); //will be true iff foo1 <= foo2 && foo2 <= foo1
//even if foo1 != foo2 or !(foo1 == foo2)

所以如果在某个类 Foo 中，if(foo1 <= foo2 && foo2 <= foo1) then somemap.insert(makepair(foo1, 1));即使 foo1 != foo2 或 !(foo1 == foo2)，somemap.find(foo2) 也会找到 foo1。

其次， vector 上的 <= 运算符是什么？它不是在测试是否具有相同的大小和逐点 ==。我认为每个 vector 都是“等效的”，意思是 <= 在两个方向上，对于空 vector ，但我不确定 - 在任何情况下都要考虑这种行为，因为这就是问题所在。