c++ - 动态 vector 的预期内容

Question

我必须存储映射到其他整数的整数值。一种方法是使用 std::map m。但是然后使用 m[int] 或 m.find(int) 检索值，将是 logN(N 是元素数)时间的顺序。在我的例子中，N 非常大(高达 2^30)。我认为使用 std::vector 访问速度会更快，因为现在每个键都映射到 vector 元素的索引，可以在 O(1) 时间内访问它。 key 以随机顺序出现，它们可能不连续。例如，如果 vector 的大小为 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]有有效值或者我没有遇到seg。过错。有人可以解释一下吗？我的理解是 push_back 函数在 vector.size > vector.capacity 时动态调整 vector 的大小，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() 进行比较然后调整 vector 大小会更好吗？

Answer 1

My understanding is push_back function dynamically resizes the vector when vector.size > vector.capacity, does operator [] also do this?

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

std::vector::at() 类似于 operator[] 但确实执行错误检查，因此可能有助于发现越界访问(但执行这些额外检查会产生性能成本)。

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

无论如何，我希望您意识到 2^30 整数将占用大量 RAM(如果 int 为 32 位宽，则为 4GB)。即使您的硬件/操作系统允许您拥有那么大的数组，您也可能必须预先分配它，而不是通过重复重新分配来增加它。