一、什麼是vector
- vector是C++提供的一個容器(container)，其底層邏輯類似於順序表
二、vector 接口
(1) 宣告 & 初始化
std::vector<int> v; // 空 vector
std::vector<int> v(5); // 初始化為 5 個 0（不給值默認為0)
std::vector<int> v(5, 10); // 初始化為 5 個 10
std::vector<int> v = {1, 2, 3}; // 使用初始化列表
(2) 基本操作
v.push_back(4); // 新增元素到尾端
v.pop_back(); // 移除尾端元素
v.size(); // 元素個數
v.empty(); // 是否為空
v.clear(); // 清空所有元素
v.resize(n) // 調整 vector 的「長度」為 n
// 若原本長度小於 n，會自動補上預設值（如 0）
// 若原本長度大於 n，多的元素會被移除
(3) 元素存取
// 使用索引
v[0] = 10; // 不安全，沒範圍檢查
int x = v[1];
// 使用at()
v.at(1) = 20; // 有範圍檢查（會拋出 exception）
// 首尾元素
v.front(); // 第一個元素
v.back(); // 最後一個元素
(4) 遍歷
// 1. for loop
for (int i = 0; i < v.size(); ++i)
std::cout << v[i] << " ";
// 2. range-based for loop
for (int x : v)
std::cout << x << " ";
// 3. Iterator
for (auto it = v.begin(); it != v.end(); ++it)
std::cout << *it << " ";
(5) 插入刪除元素
// 1. 插入
v.insert(v.begin() + 2, 99); // 在第 3 個位置插入 99
v.push_back(4) // 尾插 4
// 2. 刪除
v.erase(v.begin() + 1); // 移除第 2 個元素
v.pop_back() // 尾刪
v.clear() // 刪除所有元素
(6) 空間管理
// 預先配置空間
v.reserve(100); // 提前分配空間（減少 realloc 次數）
// 調整vector的size
三、vector模擬實現 (閹割版)
(1) vector 類的定義
template <class T> // 定義一個模板 => 提高代碼的泛用性
class vector{
public:
typedef T* iterator; // 自定義類型（為了更符合庫中的設計）
typedef const T *const_iterator;
private:
iterator _start = nullptr; // 第一個元素的位置
iterator _finish = nullptr; // 最後一個元素的位置
iterator _end_of_storage = nullptr; // 容量
};
(2) vector 構造、析構、拷貝構造函數
std::vector<int> v; // 空 vector
std::vector<int> v(5); // 初始化為 5 個 0（不給值默認為0)
std::vector<int> v(5, 10); // 初始化為 5 個 10
// 1. 空 vector
vector(){}
// 2. 初始化為5個0 & 初始化為5個10
vector(size_t n, T& val = T()){
resize(n,val);
}
// 3. 迭代器初始化 [first,last)
template <class InputIterator>
vector(InputIterator first, InputIterator last)
{
while (first != last)
{
push_back(*first);
first++;
}
}
// 析構
~vector()
{
if (_start)
{
delete[] _start;
_start = nullptr;
_finish = nullptr;
_end_of_storage = nullptr;
}
}
// 拷貝構造函數
// 深拷貝 => 默認為淺拷貝，對於自定義類型而言，若使用淺拷貝會發生問題
vector(const vector<T> &v)
{
_start = new T[v.capacity()];
// memcpy(_start, v._start, sizeof(T) * v.size()); // 所以不能使用memcpy
for (size_t i = 0; i < v.size(); ++i)
{
_start[i] = v._start[i];
}
_finish = _start + v.size();
_end_of_storage = _start + v.capacity();
}
(3) 迭代器
iterator begin()
{
return _start;
}
iterator end()
{
return _finish;
}
const_iterator begin() const
{
return _start;
}
const_iterator end() const
{
return _finish;
}
迭代器失效知識點：
vector erase和insert迭代器對象後，不能再訪問這個迭代器我們認為他失效，訪問結果是未定義
為什麼會有迭代器失效的問題？
insert後可能會擴容，而擴容後不一定是原地擴容，如果是異地擴容相當於當前的迭代器就不是指向新的空間，就會導致發生問題
erase 會讓
it所指的那個位置從記憶體中移除，且後面元素整個搬移造成：
it所指的位置內容變動了- 甚至之後的
it + 1,it + 2全部失效解決方法：接回傳的 iterator
庫中對iterator回傳值的說明
An iterator pointing to the new location of the element that followed the last element erased by the function call. This is the container end if the operation erased the last element in the sequence.
(4) 元素個數 & 空間大小
size_t size() const
{
return _finish - _start; // 因爲_finish這個位置就是我們最後一個元素的位置 所以和第一個元素的位置相減就可以得到元素個數
}
size_t capacity() const
{
return _end_of_storage - _start;
}
(4) 增刪街口
void push_back(const T &x)
{
// if (_finish == _end_of_storage)
// {
// // 擴容邏輯
// size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
// reserve(new_capacity);
// }
// *_finish = x;
// ++_finish;
insert(end(), x);
}
void pop_back()
{
erase(--end());
}
iterator insert(iterator pos, const T &x)
{
assert(pos >= _start && pos <= _finish);
if (_finish == _end_of_storage)
{
size_t len = pos - _start; // 保存pos的位置
// 擴容邏輯
size_t new_capacity = capacity() == 0 ? 4 : capacity() * 2;
reserve(new_capacity);
// 解決迭代器失效問題
pos = _start + len;
}
iterator _end = _finish - 1;
while (_end >= pos)
{
*(_end + 1) = *_end;
--_end;
}
*pos = x; // pos的類型是 T* 用解引用就可以直接改變pos指向的位置的值
++_finish;
return pos;
}
iterator erase(iterator pos)
{
assert(pos >= _start && pos <= _finish);
iterator it = pos + 1;
while (it != _finish)
{
*(it - 1) = *it;
++it;
}
--_finish;
return pos;
}
(5) 空間配置
// 1. resize()
void resize(size_t n, T &val = T())
{
if (n < size())
{
_finish = size() + 1;
}
else
{
reserve(n);
while (_finish != _start + n)
{
*_finish = val;
++_finish;
}
}
}
// 2. reserve()
void reserve(size_t n)
{
if (n > capacity()) // n 如果大於有效空間 就要擴容
{
size_t sz = size();
T *tmp = new T[n];
if (_start)
{
// memcpy(tmp, _start, sizeof(T) * sz); // memcpy 自定義類型會有問題
// 調用深拷貝
for (size_t i = 0; i < sz; ++i)
{
tmp[i] = _start[i];
}
delete[] _start;
}
_start = tmp;
_finish = _start + sz; // 不能直接調用size() 會崩潰
_end_of_storage = _start + n;
}
}
(6) 運算符重載
void swap(vector<T> &v)
{
std::swap(_start, v._start);
std::swap(_finish, v._finish);
std::swap(_end_of_storage, v._end_of_storage);
}
// 賦值
// v1 = v2
vector<T> &operator=(vector<T> v)
{
swap(v); // 直接拷貝一個v2 然後在將 v1 的內容與 v2 相互對調即可 （因爲v2的拷貝構造出了此作用域後就會被銷毀）
return *this;
}
T &operator[](size_t pos)
{
assert(pos < size());
return _start[pos];
}