动态向量的预期内容

发布于 2024-12-03 04:39:08 字数 1109 浏览 0 评论 0原文

我必须存储映射到其他整数的整数值。一种方法是使用 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() 进行比较然后调整向量的大小会更好吗?

I have to store integer values which are mapped to other integers. One way to do it is use a std::map m. But then to retrieve the value using m[int] or m.find(int), will be an order of logN (N is number of elements) time. In my case N is pretty large (upto 2^30). I thought using a std::vector will be faster for access as each key now maps to index of a vector element, which can be accessed in O(1) time. The key is encountered in random order and they may not be contiguous. For e.g., if the vector has size 10, then not all 10 elements are valid and there could only be 6 valid elements and rest I need to fill with -1. I wrote a small program and I'm surprised to find output below:

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; 
}

The output seen is size = 6, capacity = 6, V[3] = 10, v[10] = 100. I do not understand how size and capacity are 6, but v[10] has a valid value or I did not encounter a seg. fault. Can someone explain this? My understanding is push_back function dynamically resizes the vector when vector.size > vector.capacity, does operator [] also do this? To be safe, I re-wrote the above code as :

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>;
   }
}

It seems to be working fine, but will it be better to compare key with v.capacity() and then resize the vector.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

秋风の叶未落 2024-12-10 04:39:08

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

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

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

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

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

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

No, it does not. If you access past the end of your vector using operator[], the behaviour of your code is undefined. You have to explicitly resize the vector to make sure it is large enough for any access through operator[].

std::vector::at() is similar to operator[] but does perform error checking and may therefore be useful in spotting out-of-bounds access (but there's going to be a performance cost of carrying out those extra checks).

If you expect your data structure to be relatively sparse, it may be worth considering std::unordered_map for the job.

In any case, I hope you realize that 2^30 ints will take a fair amount of RAM (4GB if int is 32 bits wide). Even if your hardware/OS will allow you to have an array that big, you may have to pre-allocate it rather than grow it through repeated reallocations.

滿滿的愛 2024-12-10 04:39:08
std::vector<int> v;
v.assign(6, -1); 
v[3] = 10; 
v[10] = 100;  // Unlucky with this statement

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

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

The size of the vector is just 6. And the accessing index is from 0 to 5. Your first snippet has undefined behavior that you got unlucky that it didn't break when accessing an index 10. If there is a notion a key association with a value, then associative containers like std::map or std::multimap would be better than a sequence container like std::vector.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文