为什么在push_back()之后Vector的size()和Capacity()不同 [英] Why Vector's size() and capacity() is different after push_back()

查看:443
本文介绍了为什么在push_back()之后Vector的size()和Capacity()不同的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我刚刚开始学习向量,对 size() capacity()
有点困惑我对他们两个都不了解。但是为什么在此程序中两者都不相同?甚至 array(10)可以容纳10个元素并以0初始化。

I just starting to learning vectors and little confused about size() and capacity() I know little about both of them. But why in this program both are different? even array(10) is making room for 10 elements and initializing with 0.

在添加 array.push_back(5)

Before adding array.push_back(5)

所以 array.size(); 是10没关系。

所以 array.capacity(); 是10没关系。

添加 array.push_back(5)

After adding array.push_back(5)

所以 array.size(); 是11没关系(已经有10次加上0然后push_back再添加一个元素5)

所以 array.capacity(); 是15为什么? (是否为一个整数保留5个块?)

So array.capacity(); is 15 Why? ( is it reserving 5 blocks for one int? ).

#include <iostream>
#include <vector>
int main(){
    std::vector<int> array(10); // make room for 10 elements and initialize with 0
    array.reserve(10);    // make room for 10 elements
    array.push_back(5);
    std::cout << array.size() << std::endl;
    std::cout << array.capacity() << std::endl;
    return 0;
}


推荐答案

该标准要求 std :: vector< T> :: push_back()已摊销 O(1)复杂度。这意味着扩展必须在几何上进行,例如,每次填充时都要增加一倍的存储量。

The Standard mandates that std::vector<T>::push_back() has amortized O(1) complexity. This means that the expansion has to be geometrically, say doubling the amount of storage each time it has been filled.

简单示例:将 push_back 32 int 依次插入 std :: vector< int> 。您将全部存储一次,如果每次用完时将容量翻倍,也将进行31份复印。为什么是31?在存储第二个元素之前,您需要复制第一个;在存储第3个之前,您将复制元素1-2,在存储第5个之前,则复制了1-4,依此类推。因此,您复制了1 + 2 + 4 + 8 + 16 = 31次,共存储32次。

Simple example: sequentially push_back 32 ints into a std::vector<int>. You will store all of them once, and also do 31 copies if you double the capacity each time it runs out. Why 31? Before storing the 2nd element, you copy the 1st; before storing the 3rd, you copy elements 1-2, before storing the 5th, you copy 1-4, etc. So you copy 1 + 2 + 4 + 8 + 16 = 31 times, with 32 stores.

进行正式分析后,您会获得 O(N)商店和副本N 个元素。这意味着每 push_back 分摊 O(1)复杂度(通常只有一家没有

Doing the formal analysis shows that you get O(N) stores and copies for N elements. This means amortized O(1) complexity per push_back (often only a store without a copy, sometimes a store and a sequence of copies).

由于这种扩展策略,您将具有 size()<大多数情况下为Capacity()。查找 shrink_to_fit 保留来学习如何以更细粒度的方式控制向量的容量。

Because of this expansion strategy, you will have size() < capacity() most of the time. Lookup shrink_to_fit and reserve to learn how to control a vector's capacity in a more fine-grained manner.

注意:在几何增长率下,任何大于1的因子都可以,并且有一些研究声称1.5可以提供更好的性能,因为更少的浪费内存(因为在某些时候重新分配的内存可以覆盖旧内存)。

Note: with geometrical growth rate, any factor larger than 1 will do, and there have been some studies claiming that 1.5 gives better performance because of less wasted memory (because at some point the reallocated memory can overwrite the old memory).

这篇关于为什么在push_back()之后Vector的size()和Capacity()不同的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆