动态向量的预期内容

Question

我必须存储映射到其他整数的整数值。一种方法是使用 std::map m。但是，使用 m[int] 或 m.find(int) 检索值将需要 logN（N 是元素数量）时间。就我而言，N 相当大（最多 2^30）。我认为使用 std::vector 的访问速度会更快，因为每个键现在都映射到向量元素的索引，可以在 O(1) 时间内访问该元素。密钥以随机顺序遇到，并且它们可能不连续。例如，如果向量的大小为 10，则并非所有 10 个元素都是有效的，并且只能有 6 个有效元素，其余的我需要填充 -1。我写了一个小程序，我惊讶地发现下面的输出：

int main () {
   std::vector<int> v;
   v.assign(6, -1); 
   v[3] = 10; 
   v[10] = 100;
   cout << v.size() << v.capacity() << endl ;
   cout << v[3] << v[10] << endl; 
}

看到的输出是 size = 6，capacity = 6，V[3] = 10，v[10] = 100。我不明白 size 和capacity 是如何计算的6，但是 v[10] 有一个有效值或者我没有遇到段。过错。有人可以解释一下吗？我的理解是，当 vector.size > 时，push_back 函数会动态调整向量的大小。 vector.capacity，operator [] 也可以这样做吗？为了安全起见，我将上面的代码重写为：

int main () {
   std::vector<int> v;
   v.assign(6, -1);
   int key = getKey(); 
   if (key < v.size()) 
      v[key] = <correct value>;
   else {
      v.resize(key, -1); // I want to assign -1 to invalid elements
      v[key-1] =  <correct value>;
   }
}

它似乎工作正常，但是将 key 与 v.capacity() 进行比较然后调整向量的大小会更好吗？

Answer 1

我的理解是push_back函数动态调整向量的大小
当向量大小>时vector.capacity，operator[]也可以做这个吗？

不，事实并非如此。如果您使用 operator[] 访问超过向量的末尾，则代码的行为是未定义的。您必须显式调整向量的大小，以确保它足够大，可以通过 operator[] 进行任何访问。

std::vector::at() 与 operator[] 类似，但执行错误检查，因此可能有助于发现越界访问（但有将成为执行这些额外检查的性能成本）。

如果您希望数据结构相对稀疏，则可能值得考虑使用 std::unordered_map 来完成这项工作。

无论如何，我希望您意识到 2^30 int 会占用相当多的 RAM（如果 int 是 32 位宽，则需要 4GB）。即使您的硬件/操作系统允许您拥有这么大的数组，您可能也必须预先分配它，而不是通过重复重新分配来增长它。

Answer 2

std::vector<int> v;
v.assign(6, -1); 
v[3] = 10; 
v[10] = 100;  // Unlucky with this statement

向量的大小仅为6。访问索引是从0到5。您的第一个代码段具有未定义的行为，您很不幸在访问索引 10 时它没有中断。如果存在键与值关联的概念，那么像 std::map 或 std::multimap 这样的关联容器会比像 这样的序列容器更好std::向量。