C++ Vector (STL)

在OPENGL 中由於需要用到陣列及向量，因此使用標準資料庫中的Vector是一個很好的選擇。所以有必要好好地瞭解一下。

以下是轉貼自wiki 的資料  http://zh.wikipedia.org/wiki/Vector_%28STL%29

Vector 是C++標準程式庫中的一個類，可視為會自動擴展容量的陣列，以循序(Sequential)的方式維護變數集合。vector的特色包括支援隨機存取，在集合尾端增刪元素很快，但是在集合中間增刪元素比較費時。vector是C++標準程式庫中的眾多容器（container）之一，除此之外還有list、set、map、…等等。 vector以模板(泛 型)方式實現，可以儲存任何型別的變數，包括使用者自定義的資料型態，例如：它可以是放置整數（int）型態的 vector、也可以是放置字串（string）型態的 vector、或者放置使用者自定型別（user-defined class）的 vector。

vector 定義於 <vector> 標頭檔中。與其他STL元件一樣，vector 屬於std名稱空間。
vector是C++標準程式庫裡最基本的容器，大多數狀況下都很有效率。vector設計之初即是為了改善C語言原生陣列的種種缺失與不便，而欲提供一種更有效、更安全的陣列。vector的的使用介面刻意類比C語言原生陣列，較明顯的差異在於記憶體管理，原生陣列必須在宣告陣列的時候明確指定陣列長度(例如 int a[5])，但是 vector 不需要指定，而是會在執行期依據狀況自我調整長度，動態增大容量。
vector的表現一如資料結構中的陣列， 允許隨機存取(Random Access)，以索引值(index)存取任一元素只要花費常數時間 O(1)，在集合尾端增加或刪除元素也是花費常數時間O(1)，若在vector集合中間增加或刪除元素時間複雜度是線性時間O(n)，較為費時。雖然 C++標準並沒有規定實作方式，但大多數 vector 內部均使用動態陣列方式實作。


 基本使用
使用vector之前，必須先 #include<vector>。
宣告一個vector變數的方法如下:

std::vector<T> v;  // T = template => type/typedef/struct/class... 

幾個vector的基本操作。

您可以建構一個元素為空的vector物件：


vector<int> ivector;

如果打算將元素放入vector中，可以使用push_back()，例如：

for(int i = 0; i < 5; i++) {
ivector.push_back(i);
}

如果打算將元素循序取出，則可以begin()與end()方法分別傳回起始位置的iterator與結束位置的iterator，例如：

for(vector<int>::iterator it = ivector.begin();
it != ivector.end();
it++) {

cout << *it << " ";
}
cout << endl;

  

vector 型別是以容器（Container） 模式為基準設計的，也就是說，基本上它有 begin()，end()，size()，max_size()，empty() 以及 swap() 這幾個方法。
 

• 存取元素的方法
  • vec[i] - 存取索引值為 i 的元素參照。 (索引值從零起算，故第一個元素是vec[0]。)
  • vec.at(i) - 存取索引值為 i 的元素的參照，以 at() 存取會做陣列邊界檢查，如果存取越界將會拋出一個例外，這是與operator[]的唯一差異。
  • vec.front() - 回傳 vector 第一個元素的參照。
  • vec.back() - 回傳 vector 最尾元素的參照。
• 新增或移除元素的方法
  • vec.push_back() - 新增元素至 vector 的尾端，必要時會進行記憶體配置。
  • vec.pop_back() - 刪除 vector 最尾端的元素。
  • vec.insert() - 插入一個或多個元素至 vector 內的任意位置。
  • vec.erase() - 刪除 vector 中一個或多個元素。
  • vec.clear() - 清空所有元素。
• 取得長度/容量
  • vec.size() - 取得 vector 目前持有的元素個數。
  • vec.empty() - 如果 vector 內部為空，則傳回 true 值。
  • vec.capacity() - 取得 vector 目前可容納的最大元素個數。這個方法與記憶體的配置有關，它通常只會增加，不會因為元素被刪減而隨之減少。
• 重新配置／重設長度
  • vec.reserve() - 如有必要，可改變 vector 的容量大小（配置更多的記憶體）。在眾多的 STL 實做，容量只能增加，不可以減少。
  • vec.resize() - 改變 vector 目前持有的元素個數。
• 迭代 (Iterator)
  • vec.begin() - 回傳一個Iterator，它指向 vector 第一個元素。
  • vec.end() - 回傳一個Iterator，它指向 vector 最尾端元素的下一個位置（請注意：它不是最末元素）。
  • vec.rbegin() - 回傳一個反向Iterator，它指向 vector 最尾端元素的。
  • vec.rend() - 回傳一個Iterator，它指向 vector 的第一個元素。

iterator是標準函式庫定義類別（Class），它是一個指標，指向iterator物件的真正位址，對它進行++的動作，表示移動至 iterator的下一個元素，對它使用*運算子（Dereferences operator），表示提取出iterator目前位址的值，如果iterator走訪至結束位置的iterator的位址，表示元素走訪完畢。

雖然您可以使用下標運算子[ ]來存取vector的元素，但實際上要知道vector與陣列本質上是不相同的，當您如最上頭那樣宣告一個空的vector物件時，其容量 （capacity）為0，長度（size）也為0，所以此時您不能使用ivector[0]來取得第一個元素值，因為實際上ivector中還沒有任何 的元素。

當使用push_back()將元素加入vector時，vector的長度會自動增長，由於每次增長度都要配置記憶體過於沒有效率，所以vector會 自動先增加足夠的容量，當元素的長度超過容量時，才會再重新配置新的容量，您可以使用capacity()取得，使用size()取得元素長度，下面這個 程式綜合以上的幾個介紹作了示範：

#include <iostream> 
#include <vector>
using namespace std; 

int main() { 
    vector<int> ivector;
 
    for(int i = 0; i < 10; i++) {
        ivector.push_back(i);
    }
 
    for(vector<int>::iterator it = ivector.begin();
        it != ivector.end();
        it++) {
 
        cout << *it << " ";
    }
    cout << endl;
 
    cout << "capacity: " << ivector.capacity() << endl
         << "size: " << ivector.size() << endl;
 
    return 0; 
}

結果如下：

0 1 2 3 4 5 6 7 8 9 capacity: 16 size: 10

 

其他

如果打算對vector進行排序、尋找、反轉等操作，可以使用標準函式庫中的泛型演算法，要使用泛型演算法必須先含入表頭檔：

#include <algorithm>

下面這個程式直接示範了排序、尋找、反轉等操作：

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() { 
    int iarr[] = {30, 12, 55, 31, 98, 11, 41, 80, 66, 21};
    vector<int> ivector(iarr, iarr + 10);
 
    // 排序 
    sort(ivector.begin(), ivector.end());
 
    for(vector<int>::iterator it = ivector.begin();
        it != ivector.end();
        it++) {
 
    cout << *it << " ";
    }
    cout << endl;

    cout << "輸入搜尋值：";
    int search = 0;
    cin >> search;
 
    vector<int>::iterator it = 
    find(ivector.begin(), ivector.end(), search);
 
    if(it != ivector.end()) {
        cout << "找到搜尋值！" << endl;
    }
    else {
        cout << "找不到搜尋值！" << endl;
    }
 
    // 反轉 
    reverse(ivector.begin(), ivector.end());
 
    for(vector<int>::iterator it = ivector.begin();
        it != ivector.end();
        it++) {
 
        cout << *it << " ";
    }
    cout << endl;
 
    return 0; 
}

執行結果：

11 12 21 30 31 41 55 66 80 98 輸入搜尋值：41 找到搜尋值！ 98 80 66 55 41 31 30 21 12 11

參考網址 

http://www.cplusplus.com/reference/vector/vector/

http://openhome.cc/Gossip/CppGossip/vector2.html