vector簡介
vector的相關文檔對于想深入了解的同學可以參考這個文檔進行學習。
-
vector是表示可變大小數組的序列容器。
-
就像數組一樣,vector也采用的連續存儲空間來存儲元素。也就是意味著可以采用下標對vector的元素進行訪問,和數組一樣高效。但是又不像數組,它的大小是可以動態改變的,而且它的大小會被容器自動處理。
-
本質講,vector使用動態分配數組來存儲它的元素。當新元素插入時候,這個數組需要被重新分配大小為了增加存儲空間。其做法是,分配一個新的數組,然后將全部元素移到這個數組。就時間而言,這是一個相對代價高的任務,因為每當一個新的元素加入到容器的時候,vector并不會每次都重新分配大小。
-
vector分配空間策略:vector會分配一些額外的空間以適應可能的增長,因為存儲空間比實際需要的存儲空間更大。不同的庫采用不同的策略權衡空間的使用和重新分配。但是無論如何,重新分配都應該是對數增長的間隔大小,以至于在末尾插入一個元素的時候是在常數時間的復雜度完成的。
-
因此,vector占用了更多的存儲空間,為了獲得管理存儲空間的能力,并且以一種有效的方式動態增長。
-
與其它動態序列容器相比(deque, list and forward_list), vector在訪問元素的時候更加高效,在末尾添加和刪除元素相對高效。對于其它不在末尾的刪除和插入操作,效率更低。比起list和forward_list統一的迭代器和引用更好。
vector的簡單說明
vector學習時一定要學會查看文檔,vector在實際中非常的重要,在實際中我們熟悉常見的接口并學會使用就可以。下面我將介紹一些常用的接口,大多數的使用跟string一樣。
注意:vector的使用要包含頭文件include<vector>
vector的定義
1.默認構造函數:
vector()
- 解釋:構造一個沒有元素的空容器。
- 示例:
#include<iostream>
#include<vector>
using namespace std;int main()
{vector<int> v; //構造一個空的int的vectorreturn 0;
}
2.有初始值的構造函數
vector(size_type n, const value_type& val = value_type())
- 解釋:構造一個n個大小空間的vector,并且每個值都初始化成val
- 示例:
vector<int> v(5, 2);
上述示例,創建了一個包含5個元素,并且每個值都是2的整形類型的vector。
3.范圍構造函數
template <class InputIterator>
vector (InputIterator first, InputIterator last,const allocator_type& alloc = allocator_type());
- 解釋:構造一個容器,其元素數與范圍 [first,last) 一樣多,每個元素按相同的順序從該范圍中的相應元素構造
- 示例:
void test_vector1()
{int arr[] = { 1,2,3,4,5 };vector<int> v(arr, arr + 5);for (auto e : v){cout << e << " "; //1 2 3 4 5}
}
創建一個包含數組中所有元素的整數類型的vector
4.拷貝構造函數
vector (const vector& x);
- 解釋:構造一個容器,其中包含 x 中每個元素的副本,順序相同
- 示例:
int main()
{vector<int> v1(5, 2); //創建一個包含5個元素,每個元素都是2的整形類型的vectorvector<int> v2(v1); //創建一個與v1相同的vector——v2for (auto e : v2){cout << e << " "; //2 2 2 2 2}
}
vector的使用
1.迭代器
begin()和end()
- 解釋:獲取第一個數據位置的iterator/const_iterator, 獲取最后一個數據的下一個位置的iterator/const_iterator
- 示例:
void test_vector2()
{// const對象使用const迭代器進行遍歷打印vector<int> v(5,10);vector<int>::const_iterator it = v.begin();//auto it = v.begin();while (it != v.end()){cout << *it << " "; //10 10 10 10 10++it;}cout << endl;
}
rbegin()和rend()
- 解釋:獲取最后一個數據位置的reverse_iterator,獲取第一個數據前一個位置的reverse_iterator
- 示例:
void test_vector2()
{// 使用列表方式初始化,C++11新語法vector<int> v{ 1,2,3,4,5 };vector<int>::reverse_iterator rit = v.rbegin();//auto rit = v.rbegin();while (rit != v.rend()){cout << *rit << " "; //5 4 3 2 1rit++;}
}
迭代器的示例:
2.vector的增刪改查操作
push_back
- 解釋:push_back用于在
vector
的尾部插入一個新的元素。跟string的用法一樣其中,value_type
表示vector
中存儲的元素類型,val
是要插入的新元素。 - 示例:
void test_vector3()
{vector<int> v;v.push_back(1);v.push_back(2);v.push_back(3);v.push_back(4);auto it = v.begin();while (it != v.end()){cout << *it << " "; //1 2 3 4++it;}
}
pop_back
- 解釋:刪除vector的最后一個元素。相當于尾刪。注意:如果容器為空,使用pop_back會產生未定義的行為。所以在用之前,要判斷vector是否為空。
- 示例:(接上面的代碼)
void test_vector3()
{v.pop_back();v.pop_back();it = v.begin();cout << "尾刪后的元素是:";while (it != v.end()){cout << * it << " "; //尾刪后的元素是:1 2++it;}
}
find
首先我們來看一下STL中的find操作。注意:vector沒有提供find方法,如果要查找只能使用STL提供的全局find
- 解釋:在[first,last)這個范圍內查找val,如果找到,會返回一個迭代器。
- 示例:
void test_vector4()
{vector<int> v{ 1,3,5,7,9,2,4,6,8 };auto p = find(v.begin(), v.end(), 8); //p的類型是int*的指針cout << *p << endl; //8
}
insert
iterator insert (iterator position, const value_type& val);
- 解釋:在positions位置之前插入val
void insert (iterator position, size_type n, const value_type& val);
- 解釋:在position位置之前插入n個val
void insert (iterator position, InputIterator first, InputIterator last);
- 解釋:在position位置之前插入[first,last)這個范圍內的數據
- 示例:
void test_vector5()
{vector<int> v1(3, 20); //創建一個包含3個元素,每個元素都是20的vectorvector<int>::iterator it;it = v1.begin();it = v1.insert(it, 40); //在it之前插入40for (auto e : v1){cout << e << " "; //40 20 20 20}cout << endl;v1.insert(it, 3, 5); //在it之前插入3個元素都是5的數據for (auto e : v1){cout << e << " "; //5 5 5 40 20 20 20}cout << endl;vector<int> v2(3, 1); //創建一個包含3個元素,每個元素都是1的vectorint array[] = { 11, 12, 13, 14, 15 };v2.insert(v2.begin(), array, array + 3); //在v2.begin()之前插入array數組中前3個元素for (auto e : v2){cout << e << " "; //11 12 13 1 1 1}cout << endl;}
erase
iterator erase (iterator position);
- 解釋:在position這個位置進行刪除數據。該函數返回一個指向被刪除元素之后元素的迭代器。注意:position要使用迭代器形式
iterator erase (iterator first, iterator last);
- 解釋:刪除指定范圍內的元素,如[first,last)區間內的元素。并返回一個指向最后一個被刪除元素之后元素的迭代器。注意:first和last要使用迭代器形式
- 示例:
void test_vector6()
{vector<int> v{ 5,4,3,2,1 };v.erase(v.begin() + 2);for (auto e : v){cout << e << " "; //5 4 2 1}cout << endl;vector<int> v1{ 5,4,3,2,1 };v1.erase(v1.begin() + 1, v1.begin() + 3);for (auto e : v1){cout << e << " "; //5 2 1//注意是左閉右開區間,所以刪除的是下標為1和2位置的元素}
}
3.vector的訪問操作
operator[]
- 解釋:它可以像數組一樣進行訪問。它的語法是
vector_name[index]
,其中vector_name
是vector
的名稱,index
是要訪問的元素的索引。索引從0開始,表示vector
中的第一個元素。 - 示例:
void test_vector7()
{vector<int> v{ 5,4,3,2,1 };//訪問操作cout << v[3] << endl; //2//修改操作v[3] = 9;cout << v[3] << endl; //9
}
empty
bool empty() const;
- 解釋:檢查vector是否為空,為空返回1,不為空時返回0。
- 示例:
void test_vector7()
{vector<int> v;int i = v.empty();cout << i << endl;if (v.empty()) //vector為空{cout << "The vector is empty" << endl;}else{cout << "The vector is not empty" << endl;}v.push_back(3);if (v.empty()) //vector不為空,{cout << "The vector is empty" << endl;}else{cout << "The vector is not empty" << endl;}
}
back和front
- 解釋:back返回的是容器中最后一個元素的引用,即最后一個元素的值。而
front()
是vector
容器的一個成員函數,返回的是容器中第一個元素的值。 - 示例:
void test_vector8()
{vector<int> v{ 5,4,3,2,1 };cout << v.front() << endl; //5cout << v.back() << endl; //1auto it1 = v.begin();auto it2 = v.end();cout << *it1 << endl; //5cout << *it2 << endl; //程序崩潰。因為end是最后一個元素的下一個位置
}
4.vector的容量操作
size
size_type size() const;
- 解釋:獲取數據個數
- 示例:
void test_vector9()
{vector<int> v;cout << "0. size: " << v.size() << '\n'; //0. size: 0for (int i = 0; i < 10; i++){v.push_back(i);}cout << "1. size: " << v.size() << '\n'; //1. size: 10v.insert(v.end(), 10, 100);cout << "2. size: " << v.size() << '\n'; //2. size: 20v.pop_back();cout << "3. size: " << v.size() << '\n'; //3. size: 19
}
capacity
size_type capacity() const;
- 解釋:獲取容量大小
- 示例:
void test_vector10()
{size_t sz;vector<int> v;sz = v.capacity();cout << "making v grow:\n";for (int i = 0; i < 100; ++i){v.push_back(i);if (sz != v.capacity()){sz = v.capacity();cout << "capacity changed: " << sz << '\n';}}
}
結果:(這是在vs2019下運行的,不同的編譯器結果會有不同)
making v grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
vs下使用的STL基本是按照1.5倍方式擴容.
resize
void resize (size_type n, value_type val = value_type());
- 解釋:調整容器的大小,使其包含 n 個元素。簡單來說是改變vector的size。
- resize函數有2種情況:
情況1 - 如果 n 小于當前容器大小,則內容將減少到其前 n 個元素,刪除超出(并銷毀它們)的元素。
情況2 - 如果 n 大于當前容器大小,則通過在末尾插入所需數量的元素來擴展內容,以達到 n 的大小。如果指定了 val,則新元素將初始化為 val 的副本,否則,它們將進行值初始化。
- 示例:
void test_vector11()
{vector<int> myvector;// set some initial content:for (int i = 1; i <= 10; i++){myvector.push_back(i);}myvector.resize(5);myvector.resize(8, 100);myvector.resize(12);cout << "myvector contains:";for (int i = 0; i < myvector.size(); i++){cout << ' ' << myvector[i]; //myvector contains: 1 2 3 4 5 100 100 100 0 0 0 0}
}
代碼解釋:先對myvector尾插了10個數據,然后使用resize將大小調整為5,所以只保留前5個元素;第2個resize是將大小調整為8,并且用100進行擴展,由于n從5變成8,所以有3個100;第3個resize是將n從8變成12,由于沒有val,所以剩余的元素用0進行擴展。
reserve
void reserve (size_type n);
- 解釋:改變vector的capacity
- 示例:
void test_vector12()
{vector<int>::size_type sz;vector<int> foo;sz = foo.capacity();cout << "making foo grow:\n";for (int i = 0; i < 100; ++i) {foo.push_back(i);if (sz != foo.capacity()) {sz = foo.capacity();cout << "capacity changed: " << sz << '\n';}}vector<int> bar;sz = bar.capacity();bar.reserve(100); // this is the only difference with foo abovecout << "making bar grow:\n";for (int i = 0; i < 100; ++i) {bar.push_back(i);if (sz != bar.capacity()) {sz = bar.capacity();cout << "capacity changed: " << sz << '\n';}}
}
結果:(這是在vs2019下運行的,不同的編譯器結果會有不同)
making foo grow:
capacity changed: 1
capacity changed: 2
capacity changed: 3
capacity changed: 4
capacity changed: 6
capacity changed: 9
capacity changed: 13
capacity changed: 19
capacity changed: 28
capacity changed: 42
capacity changed: 63
capacity changed: 94
capacity changed: 141
making bar grow:
capacity changed: 100
vector迭代器失效的問題(重點)
迭代器的主要作用就是讓算法能夠不用關心底層數據結構,其底層實際就是一個指針,或者是對指針進行了封裝,比如:vector的迭代器就是原生態指針T*
。因此迭代器失效,實際就是迭代器底層對應指針所指向的空間被銷毀了,而使用一塊已經被釋放的空間,造成的后果是程序崩潰(即如果繼續使用已經失效的迭代器,程序可能會崩潰)。
對于vector可能會導致其迭代器失效的操作有:
- 會引起其底層空間改變的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back等。
int main()
{vector<int> v{ 1,2,3,4,5,6 };auto it = v.begin();// 將有效元素個數增加到100個,多出的位置使用8填充,操作期間底層會擴容//v.resize(100, 8);// reserve的作用就是改變擴容大小但不改變有效元素個數,操作期間可能會引起底層容量改變//v.reserve(100);// 插入元素期間,可能會引起擴容,而導致原空間被釋放//v.insert(v.begin(), 0);//v.push_back(8);// 給vector重新賦值,可能會引起底層容量改變//v.assign(100, 8);/*出錯原因:以上操作,都有可能會導致vector擴容,也就是說vector底層原理舊空間被釋放掉,而在打印時,it還使用的是釋放之間的舊空間,在對it迭代器操作時,實際操作的是一塊已經被釋放的空間,而引起代碼運行時崩潰。解決方式:在以上操作完成之后,如果想要繼續通過迭代器操作vector中的元素,只需給it重新賦值即可。*/while (it != v.end()){cout << *it << " ";++it;}cout << endl;return 0;
}
- 指定位置元素的刪除操作–erase
int main()
{int a[] = { 1, 2, 3, 4 };vector<int> v(a, a + sizeof(a) / sizeof(int));// 使用find查找3所在位置的iteratorvector<int>::iterator pos = find(v.begin(), v.end(), 3);// 刪除pos位置的數據,導致pos迭代器失效。v.erase(pos);cout << *pos << endl; // 此處會導致非法訪問return 0;
}
erase刪除pos位置元素后,pos位置之后的元素會往前搬移,沒有導致底層空間的改變,理論上講迭代器不應該會失效,但是:如果pos剛好是最后一個元素,刪完之后pos剛好是end的位置,而end位置是沒有元素的,那么pos就失效了。因此刪除vector中任意位置上元素時,vs就認為該位置迭代器失效了。
現在來看一個案例:刪除vector中所有的偶數。
- 先看錯誤寫法
#include <iostream>
using namespace std;
#include <vector>int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();// vs2019進行強制檢查,erase以后認為it失效了,不能訪問,訪問就報錯while (it != v.end()){if (*it % 2 == 0)v.erase(it);++it;}return 0;
}
這是模擬實現vector中erase的寫法,上面的圖片中畫出了出錯的原因,同學們可以參考一下
- 正確寫法
int main()
{vector<int> v{ 1, 2, 3, 4 };auto it = v.begin();while (it != v.end()){if (*it % 2 == 0){it = v.erase(it);}else{++it;}}return 0;
}
- 與vector類似,string在插入+擴容操作+erase之后,迭代器也會失效
#include <string>
void TestString()
{string s("hello");auto it = s.begin();// 放開之后代碼會崩潰,因為resize到20會string會進行擴容// 擴容之后,it指向之前舊空間已經被釋放了,該迭代器就失效了// 后序打印時,再訪問it指向的空間程序就會崩潰//s.resize(20, '!');while (it != s.end()){cout << *it;++it;}cout << endl;it = s.begin();while (it != s.end()){it = s.erase(it);// 按照下面方式寫,運行時程序會崩潰,因為erase(it)之后// it位置的迭代器就失效了// s.erase(it);++it;}
}
迭代器失效解決辦法:在使用前,對迭代器重新賦值即可
注意:Linux下,g++編譯器對迭代器失效的檢測并不是非常嚴格,處理也沒有vs下極端.
vector深度剖析及模擬實現
std::vector的核心框架接口的模擬實現bit::vector
vector的模擬實現
使用memcpy拷貝問題
假設模擬實現的vector中的reserve接口中,使用memcpy進行的拷貝,以下代碼會發生什么問題?
int main()
{bite::vector<bite::string> v;v.push_back("1111");v.push_back("2222");v.push_back("3333");return 0;
}
問題分析:
- memcpy是內存的二進制格式拷貝,將一段內存空間中內容原封不動的拷貝到另外一段內存空間中
- 如果拷貝的是內置類型的元素,memcpy既高效又不會出錯,但如果拷貝的是自定義類型元素,并且自定義類型元素中涉及到資源管理時,就會出錯,因為memcpy的拷貝實際是淺拷貝。
結論:如果對象中涉及到資源管理時,千萬不能使用memcpy進行對象之間的拷貝,因為memcpy是淺拷貝,否則可能會引起內存泄漏甚至程序崩潰.