【C++】朝花夕拾——STL vector，朝花夕拾stlvector

【C++】朝花夕拾——STL vector，朝花夕拾stlvector

STL之vector篇

　　N久之前是拿C的數組實現過vector中的一些簡單功能，什麼深拷貝、增刪查找之類的，以為vector的實現也就是這樣了，現在想想真是...too young too naive...ORZ

====================我是分割線=============================

vector屬於順序容器，它的底層實現就是基於array，所以它可以支持隨機訪問，但是它比array更有效率，因為它動態分配的內存空間。

 

動態分配的內存空間:

　　　每當vector的capacity==size，並且有新element需要加入時，vector會申請一段大小等於2*capacity的連續內存空間，將原來的數據深拷貝到新的內存地址，然後釋放掉原來的內存，並添加新的element到內存中。(這一系列內存操作大大影響了vector的存儲效率)

　　    因為，不同的環境下，vector的實現方式有所出入，所以初始化時的capacity大小不一樣，但是capacity一定會大於所需的內存大小，預留一定的空間，已減少內存操作。

 

以下是簡單的測試:

環境如下:

g++ 4.8.4

ubuntu 14.04

 

test1:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    vector<char> v2;
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;
    return 0;
}

結果如下: 

v1 size = 0
v1 capacity = 0
v1 max_size = 4611686018427387903
v2 size = 0
v2 capacity = 0
v2 max_size = 18446744073709551615

max_size返回vector可以保持的element個數的上限，這個上限與系統的底層實現有關，不一定可以達到(當內存不夠時，不能繼續分配）

這裡可以看出，此時初始化的capacity==0

 

test2:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 1; ++i)v1.push_back(i);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    vector<char> v2;
    for (int i = 0; i < 1; ++i)v2.push_back(char(i));
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;
    return 0;
}

 

結果如下:

v1 size = 1
v1 capacity = 1
v1 max_size = 4611686018427387903
v2 size = 1
v2 capacity = 1
v2 max_size = 18446744073709551615

此時，插入一個元素，capacity==1，size也為1

 

test3:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 2; ++i)v1.push_back(i);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    vector<char> v2;
    for (int i = 0; i < 2; ++i)v2.push_back(char(i));
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;
    return 0;
}

 

結果如下:

v1 size = 2
v1 capacity = 2
v1 max_size = 4611686018427387903
v2 size = 2
v2 capacity = 2
v2 max_size = 18446744073709551615

 

當插入兩個元素時，capacity = 2 * capacity(即為2），然後拷貝之前的數據到新的內存空間，添加新元素，則size==2

 

test4:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 3; ++i)v1.push_back(i);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    vector<char> v2;
    for (int i = 0; i < 3; ++i)v2.push_back(char(i));
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;
    return 0;
}

 

結果如下:

v1 size = 3
v1 capacity = 4
v1 max_size = 4611686018427387903
v2 size = 3
v2 capacity = 4
v2 max_size = 18446744073709551615

又接著添加一個新元素，capacity翻倍(變成4），size增加1，即3

 

添加新元素的原理get  >   <

===========================第二分割線===================================

以下為刪除原理

test5:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 129; ++i)v1.push_back(i);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    vector<char> v2;
    for (int i = 0; i < 129; ++i)v2.push_back(char(i));
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;
    return 0;
}

 

結果如下:

v1 size = 129
v1 capacity = 256
v1 max_size = 4611686018427387903
v2 size = 129
v2 capacity = 256
v2 max_size = 18446744073709551615

 

test6:

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 129; ++i)v1.push_back(i);
    v1.pop_back();
    v1.pop_back();
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    vector<char> v2;
    for (int i = 0; i < 129; ++i)v2.push_back(char(i));
    v2.pop_back();
    v2.pop_back();
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;
    return 0;
}

結果如下:

v1 size = 127
v1 capacity = 256
v1 max_size = 4611686018427387903
v2 size = 127
v2 capacity = 256
v2 max_size = 18446744073709551615

 

(⊙v⊙)嗯，看來內存的動態改變並不會隨著size的減小的縮減capacity，避免了不必要的內存操作。

C++手冊中也有說明，pop_back的操作只是size減1

=============================第三分割線==================================

接著，是各個函數的底層理解

assign() 

　　有三種形參形式(iterator begin，iterator end)初始化為迭代器指向的容器之間的內容；(n, value)初始化N個值為value的元素；(initializer_list<value_type> il)深拷貝

back()

　　返回vector中最後一個值，當vector為空時，調用該函數會報錯

front()

　　返回vector中第一個值，當vector為空時，調用該函數會報錯

begin()

　　返回指向第一個element的迭代器

end()

　　返回指向past-the-end element的迭代器，past-the-end element是理論上應該跟在最後一個element後面的位置，但是那個位置上並沒有存放element

cbegin()

　　返回一個首個元素的const_iterator迭代器，用該迭代器訪問元素是是不可以用來改變元素本身值的(即便元素本身並非const類型）

cend()

　　返回一個past-the-last element的const_iterator迭代器

crbegin()

　　r表示逆序，c表示const，此處返回vector中逆序第一個element的const_iterator

crend()

　　此處返回vector中第一個element的const_iterator，功能與cbegin()相同

rbegin()

　　返回逆序第一個element的迭代器，即為指向end()的前一個位置的迭代器

rend()

　　返回逆序的最後一個element的迭代器，即指向第一個element

capacity()

　　返回vector容器已開辟的內存可存放element的個數

size()

　　返回當前vector中已有的element個數，size <= capacity

max_size()

　　返回一個理論上允許的capacity上限值，但不一定能達到

data()

　　返回一個指向當前容器內存起始地址的指針，由於vector的內存分配是連續的，所以可以直接用指針offset來為容器中的element賦值

　　std::vector<int> myvector (5);

　　int* p = myvector.data();

　　*p = 10;

　　++p;

　　*p = 20;

    p[2] = 100;

emplace()

 關於emplace和insert的區別，如下:

(emplace會調用類的構造函數,代碼搬運自:http://stackoverflow.com/questions/14788261/c-stdvector-emplace-vs-insert）

struct Foo
{
  Foo(int n, double x);
};

std::vector<Foo> v;
v.emplace(someIterator, 42, 3.1416);
v.insert(someIterator, Foo(42, 3.1416));

 

emplace_back()

　　調用構造函數，然後把element加到末尾

insert()

　　可以把element插入到迭代器指定的element之前的位置。

　　由於底層實現時array，除了在末尾插入element，在其他的位置插入，都需要將指定插入位置後面的element移位，這將導致效率低下

　　如果插入之後size>capacity，則參考push_back的重新申請內存空間

erase()

　　刪除指定區間或者位置的element，同樣，除了刪除末尾的element，刪除其他位置的element都需要把後面的element往前移動，也是導致效率低的原因

clear()

　　把所有element都移除，size=0，此時capacity不一定為0(不一定會有釋放內存的操作）//正確的釋放內存姿勢——swap()

empty()

　　size >= 0, 返回false；否則返回true

get_allocator()

　　返回該容器的allocator

operator=

　　拷貝，STL中的拷貝都是深拷貝

operator[]

　　訪問節點

push_back()

　　在末尾增加一個element，當size超出時，capacity翻倍(具體看此博文開頭)，size++

pop_back()

　　移除末尾一個element, size--

reserve()

　　v.reserve（n）;表示此時V的capacity至少要大於等於300，若capacity<300，則重新申請內存；反之則不用做其他操作；

　　

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 129; ++i)v1.push_back(i);
    v1.pop_back();
    v1.pop_back();
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    vector<char> v2;
    for (int i = 0; i < 129; ++i)v2.push_back(char(i));
    v2.reserve(300);
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;
    return 0;
}

結果為:

v1 size = 127
v1 capacity = 256
v1 max_size = 4611686018427387903
v2 size = 129
v2 capacity = 300
v2 max_size = 18446744073709551615

 

resize()

　　v.resize（n）將會把v中的size調整為n大小，若n > size，則用0補足element；若n < size，則取容器中的前n個element，其與元素移除；

　　v.resize（n，m）將會把v中的size調整為n大小，若n > size，則用m補足element

　　

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 10; ++i)v1.push_back(i);
    for (int i = 0; i < v1.size(); i ++)cout << v1[i] << " ";
    cout << endl;
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;

    v1.resize(7);
    for (int i = 0; i < v1.size(); i ++)cout << v1[i] << " ";
    cout << endl;
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;

    v1.resize(20, 200);
    for (int i = 0; i < v1.size(); i ++)cout << v1[i] << " ";
    cout << endl;
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;

    v1.resize(50);
    for (int i = 0; i < v1.size(); i ++)cout << v1[i] << " ";
    cout << endl;
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    return 0;
}

 

結果如下:

0 1 2 3 4 5 6 7 8 9
v1 size = 10
v1 capacity = 16
v1 max_size = 4611686018427387903
0 1 2 3 4 5 6
v1 size = 7
v1 capacity = 16
v1 max_size = 4611686018427387903
0 1 2 3 4 5 6 200 200 200 200 200 200 200 200 200 200 200 200 200
v1 size = 20
v1 capacity = 20
v1 max_size = 4611686018427387903
0 1 2 3 4 5 6 200 200 200 200 200 200 200 200 200 200 200 200 200 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
v1 size = 50
v1 capacity = 50
v1 max_size = 4611686018427387903

 

shrink_to_fit()

　　一般來說capacity滿足，capacity>=size；v.shrink_to_fit()操作可以使得，capacity==size，這也是釋放內存的操作之一!！!

　　

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 10; ++i)v1.push_back(i);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;

    v1.resize(7);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;

    v1.shrink_to_fit();
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;

    return 0;
}

結果如下:

v1 size = 10
v1 capacity = 16
v1 max_size = 4611686018427387903
v1 size = 7
v1 capacity = 16
v1 max_size = 4611686018427387903
v1 size = 7
v1 capacity = 7
v1 max_size = 4611686018427387903

 

swap()

　　v.swap(v2)的操作可以將v，和v2中的element交換

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 10; ++i)v1.push_back(i);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;

    vector<int> v2;
    for (int i = 0; i < 20; ++i)v2.push_back(i);
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;

    v1.swap(v2);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    cout << "v1 max_size = " << v1.max_size() << endl;
    cout << "v2 size = " << v2.size() << endl;
    cout << "v2 capacity = " << v2.capacity() << endl;
    cout << "v2 max_size = " << v2.max_size() << endl;

    return 0;
}

結果如下:

v1 size = 10
v1 capacity = 16
v1 max_size = 4611686018427387903
v2 size = 20
v2 capacity = 32
v2 max_size = 4611686018427387903
v1 size = 20
v1 capacity = 32
v1 max_size = 4611686018427387903
v2 size = 10
v2 capacity = 16
v2 max_size = 4611686018427387903

 

小結:

vector是不會自動釋放內存的，但是如果size的極大值很大的話會造成capacity很大，浪費內存。

所以以下有幾種方法可以釋放vector的內存:

　　①shrink_to_fit

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 20; ++i)v1.push_back(i);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;

    v1.clear();
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;

    v1.shrink_to_fit();
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;
    

    return 0;
}

 

結果:

v1 size = 20

v1 capacity = 32

v1 size = 0
v1 capacity = 32
v1 size = 0
v1 capacity = 0

　　

　　②swap

　　

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v1;
    for (int i = 0; i < 20; ++i)v1.push_back(i);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;

    vector<int>().swap(v1);
    cout << "v1 size = " << v1.size() << endl;
    cout << "v1 capacity = " << v1.capacity() << endl;

    return 0;
}

 

結果如下:

v1 size = 20
v1 capacity = 32
v1 size = 0
v1 capacity = 0

 

　　　　③指針釋放

　　　　

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> v;
    vector<int>* v1 = &v;
    for (int i = 0; i < 20; ++i)v1->push_back(i);
    cout << "v size = " << v.size() << endl;
    cout << "v capacity = " << v.capacity() << endl;

    delete v1;
    return 0;
}

 

========================我是第四分割線============================

C++11的標准中，vector新增加的成員函數:

crbegin

crend

cbegin

cend

emplace

emplace_back

data

shrink_to_fit

========================我是第五分割線============================

最後簡單說說，高效索引之bitset和vector<bool>

 

bitset　　可以進行位操作，但是大小固定

vector<bool>   屬於vector的一種特殊形式，用bool類型的allocator構造，但是在實現的時候優化了，所以它的element類型並不是bool，而是bit