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

我必须存储映射到其他整数的整数值。一种方法是使用std::map m。但是随后使用m [int]或m.find(int)检索值将是logN(N是元素数)时间的顺序。在我的情况下，N非常大(最多2 ^ 30)。我认为使用std::vector可以更快地进行访问，因为每个键现在都映射到vector元素的索引，可以在O(1)时间访问。密钥以随机顺序遇到，并且它们可能不是连续的。例如，如果 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，容量= 6，V [3] = 10，v [10] =100。我不知道大小和容量如何为6，但是v [10]具有有效值，或者我没有遇到段。故障。有人可以解释吗？我的理解是，当vector.size> vector.capacity时，push_back函数会动态调整 vector 的大小，操作符[]也会这样做吗？为了安全起见，我将以上代码重新编写为:

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 的大小。

最佳答案

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

vector 的大小仅为 6 。访问索引为 0到5 。您的第一个代码段具有未定义的行为，您很不幸在访问索引 10 时没有中断。如果存在与值关联的键，则诸如std::map或std::multimap的关联容器将比诸如std::vector的序列容器更好。

关于c++ - 动态 vector 的预期内容，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/7310624/