C++ Primer 第九章 9.4 Vector對象是如何增長的 練習和總結

9.4 Vector對象是如何增長的

vector對象為了支援快速随機通路，其實體存儲方式是連續存儲的，又因為vector是動态大小的，是以這就涉及到了一個問題。

如果目前的vector容器配置設定的存儲空間空間已經滿了，不能再添加新的元素，那麼就需要重新配置設定一塊記憶體空間，将原來的值複制過去并添加新的元素。

但是如果每次添加都重新配置設定記憶體空間的話，vector的效率會非常的低。

是以為了避免這種低效的方式，vector有自己的記憶體增長方式，需要注意的是，這種增長方式不同的标準庫實作者政策是不同的。

總的來說，vector和string通常會配置設定比新空間需求（新空間需求即：容器目前需要存進去多少元素）更大的記憶體空間。

和容量相關的成員函數如下：

1.之前說了容器實際能夠容納的元素個數通常大于或者等于目前的需求，也就是容器會有多餘的空間，使用shrink_to_fit()可以收回多餘的空間，但是這依賴于标準庫的實作者，實作者有權不收回多餘的空間。

2.capacity，表示容器在不重新配置設定記憶體空間的情況下，最多可以容納多少元素。

3.reserve，改變容器的capacity。需要注意的是，reserve(n)配置設定的記憶體空間是小于等于capacity的。且當n小于容器目前實際存儲的元素個數時，reserve是不會其作用的。也就是說reserve的n隻是一個參考，當n<size()時，reserve不會起作用，當n>size()時，capacity（）>=n

capacity()和size()的差別

前者表示在不重新配置設定記憶體空間的情況下，最多可以容納多少元素。

後者表示目前容納了多少元素。

resize()和reserve()的差別

resize()改變的是size()的大小，但是如果resize(n),n大于capacity(),就會改變capacity(),reserve()改變的是capacity()的大小，reserve(n),n<=capacity()

隻有在insert（push_back也算insert),size==capacity(),或者resize(n),reverse(n)中的n大于capacity()時，vector才會重新配置設定記憶體空間

練習

9.35

capacity表示vec在不重新配置設定記憶體空間的情況下，最多可以容納多少元素

size()表示vec目前以及容納多少元素

9.36

capacity()永遠>=size()

9.37

這個list，array的存儲接口有關，list在記憶體上并不是連續存儲的，是以插入新元素時，可以直接配置設定新的記憶體空間。array的記憶體是固定的，是以沒法開辟新的存儲空間，size（）就是它的最大容量。

9.38

VS2017的标準庫

vector<int> vec;
	cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;

	vec.push_back(1);
	cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;
	for (int i = 0; i < 10;i++) {
		vec.push_back(i);
		cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;
	}
	vec.reserve(20);
	cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;
	for (int i = 0; i < 50; i++) {
		vec.push_back(i);
		cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;
	}
           

程式的輸出：

size:0capacity:0
size:1capacity:1
size:2capacity:2
size:3capacity:3
size:4capacity:4
size:5capacity:6
size:6capacity:6
size:7capacity:9
size:8capacity:9
size:9capacity:9
size:10capacity:13
size:11capacity:13
size:11capacity:20
size:12capacity:20
size:13capacity:20
size:14capacity:20
size:15capacity:20
size:16capacity:20
size:17capacity:20
size:18capacity:20
size:19capacity:20
size:20capacity:20
size:21capacity:30
size:22capacity:30
size:23capacity:30
size:24capacity:30
size:25capacity:30
size:26capacity:30
size:27capacity:30
size:28capacity:30
size:29capacity:30
size:30capacity:30
size:31capacity:45
size:32capacity:45
size:33capacity:45
size:34capacity:45
size:35capacity:45
size:36capacity:45
size:37capacity:45
size:38capacity:45
size:39capacity:45
size:40capacity:45
size:41capacity:45
size:42capacity:45
size:43capacity:45
size:44capacity:45
size:45capacity:45
size:46capacity:67
size:47capacity:67
size:48capacity:67
size:49capacity:67
size:50capacity:67
size:51capacity:67
size:52capacity:67
size:53capacity:67
size:54capacity:67
size:55capacity:67
size:56capacity:67
size:57capacity:67
size:58capacity:67
size:59capacity:67
size:60capacity:67
size:61capacity:67
           

可以看到當size()小于10時，容器的size()和capacity（）是一樣的，大于10之後，capacity()>=size(),且越往後配置設定，當capacity()==size()時，重新配置設定的記憶體空間要比之前重新配置設定的記憶體空間的增量要大。

9.39

向svec中添加元素，添加完成之後，将vec的大小為resize()原來的1.5倍。

9.40

因為reserve(n)，capacity可能大于等于n，是以實際的結果我們是不确定的，需要根據具體的編譯器來确定。

假定reserve(n)之後，capacity等于n，那麼

讀入256個詞，capacity為1024

讀入512個詞，capacity為2014，

後面的就看具體的标準庫如何實作的了

在VS2017下

1000，capacity為1536

1048，capacity為2304

使用的代碼如下

vector<string> vec;
	vec.reserve(1024);
	cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;

	int count = 1048;
	for (int i = 0; i < count;++i) {
		vec.push_back("233");
	}
	vec.resize(vec.size()+vec.size()/2);
	cout << "size:" << vec.size() << "capacity:" << vec.capacity() << endl;