学习STL中的vector：开启C++容器之旅的前言
- 在C++的编程世界中，标准模板库（STL）无疑是每位开发者都需要熟练掌握的工具集。其中，vector作为STL中最常用的动态数组容器之一，以其灵活、高效和易用的特性，成为了众多C++程序员的首选。
vector容器允许我们存储任意数量的同类型元素，并且能够根据需要进行动态扩展。这种灵活性使得vector在处理大量数据时变得尤为高效，无论是在科学计算、图形处理、网络编程还是游戏开发等领域，我们都能看到vector的身影。
现在让我们一起踏上学习STL中vector的旅程吧！
📒1.vector类的基本概念
vector是C++标准模板库（STL）中的一个动态数组容器，它提供了对一段连续空间的动态管理功能。与普通的C++数组相比，vector具有许多优点，如可以动态调整大小、支持随机访问等。
vector类成员函数：
class string { private: iterator _start; iterator _finish; iterator _end_of_storage; };
📕2. vector类的常用操作
🌈vector类对象的常见构造
| 构造函数声明 | 接口说明 |
| vector() | 无参构造 |
| vector（size_type n, const value_type& val = value_type()） | 构造并初始化n个val |
| vector (const vector& x); | 拷贝构造 |
| vector (InputIterator first, InputIterator last); | 使用迭代器进行初始化构造 |
int main() { vector<int> v1; // 无参构造 vector<int> v2(10, 0); // 构造并初始化n个val vector<int> v3(v2); // 拷贝构造 vector<int> v4(v2.begin(),v2.end()); // 使用迭代器进行初始化构造 return 0; }
关于 vector iterator 的使用
| iterator的使用 | 接口说明 |
| begin +end | 获取第一个数据位置的iterator/const_iterator， 获取最后一个数据的下一个位置的iterator/const_iterator |
| rbegin + rend | 获取最后一个数据位置的reverse_iterator，获取第一个数据前一个位置的reverse_iterator |
其实vector的很多用法和string类似
🌞vector类对象的容量操作
| 容量空间 | 接口说明 |
| size | 获取数据个数 |
| capacity | 获取容量大小 |
| empty | 判断是否为空 |
| resize | 改变vector的size |
| reserve | 改变vector的capacity |
int main() { vector<int> v(10, 0); cout << v.size() << endl; // 获取数据个数 cout << v.capacity() << endl; // 获取容量大小 v.reserve(20); // 改变vector的capacity cout << endl; cout << "after reserve size: " << v.size() << endl; cout << "after reserve capacity: " << v.capacity() << endl; cout << endl; v.resize(20); // 改变vector的size cout << "after resize size: " << v.size() << endl; cout << "after resize capacity: " << v.capacity() << endl; cout << v.empty() << endl; // 判断是否为空 return 0; }
注意：
- capacity的代码在vs和g++下分别运行会发现，
vs下capacity是按1.5倍增长的，g++是按2倍增长的。这个问题经常会考察，不要固化的认为，vector增容都是2倍，具体增长多少是根据具体的需求定义的。vs是PJ版本STL，g++是SGI版本STL- reserve只负责开辟空间，不会影响size的大小，如果确定知道需要用多少空间，reserve可以缓解vector增容的代价缺陷问题。
- resize在开空间的同时还会进行初始化，会影响size的大小
🌙vector类对象的增删查改
| vector增删查改 | 接口说明 |
| push_back | 尾插 |
| pop_back | 尾删 |
| insert | 在pos之前插入val |
| erase | 删除pos位置的数据 |
| swap | 交换两个vector的数据空间 |
| operator[ ] | 像数组一样访问 |
注意：
find查找，这个是算法模块实现，不是vector的成员接口
代码示例：
int main() { vector<int> v1(1, 0); v1.push_back(1); // 尾插 v1.push_back(2); v1.push_back(3); v1.push_back(5); // 尾插后v1 : 0,1,2,3,5 v1.pop_back(); // 尾删后v1 : 0,1,2,3 cout << "v1: "; for (size_t i = 0; i < v1.size(); i++) // 遍历vector数组 { cout << v1[i] << " "; // operator[]随机访问 } cout << endl; vector<int> v2(10, 0); cout << "v2: "; for (size_t i = 0; i < v2.size(); i++) { cout << v2[i] << " "; } cout << endl; v1.swap(v2); // 交换v1,v2内容 cout << "after swap v1: "; for (size_t i = 0; i < v1.size(); i++) { cout << v1[i] << " "; } cout << endl; vector<int>::iterator it = find(v1.begin(), v1.end(), 0); // 查找 cout << *it; return 0; }
注意：insert和erase在vector里面有点特殊，在vector上它使用的都是迭代器
erase往往和find搭配使用
vector<int> v{1,2,3,4,5,6,7,8,9}; auto pos = find(v.begin(),v.end(),6); v.erase(pos); //删除一个区间 v.erase(v.begin() + 1,v.end() - 1);
用
insert头插一个0
vector<int> v{1,2,3,4,5,6,7,8,9}; auto pos = v.begin(); v.insert(pos,0);
📜3. vector类的模拟实现
🍁vector的成员变量
首先我们要先搞清楚 vector的成员变量，我们清楚 vector类在底层实际上也是指针，在模拟实现 vector之前，我们创建一个属于自己的命名空间来与库里面的区分
namespace pxt { template<class T> class vector { public: // vector的迭代器是一个原生指针 typedef T* iterator; typedef const T* const_iterator; // 迭代器相关(迭代器主要就是找到头尾） iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin() const { return _start; } const_iterator end() const { return _finish; } private: // 成员变量 iterator _start; // 指向有效数据的头 iterator _finish; // 指向有效数据的尾 iterator _end_of_storage; // 指向最大空间的地方 }; }
🌸vector的构造函数
无参构造:
vector() :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) {}
带参的构造函数
vector(size_t n, const T& val = T()) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { reserve(n); // 开辟空间 for (size_t i = 0; i < n; i++) { push_back(val); // 给初始值赋值 // reserve，push_back的模拟实现下面会讲 } }
迭代器区间构造
为了实现不同类型迭代器的构造，这里需要再创建一个模板
template <class InputIterator> // 类似与STL vector(InputIterator first, InputIterator last) :_start(nullptr) , _finish(nullptr) , _end_of_storage(nullptr) { while (first != last) { push_back(*first); ++first; } }
🌷vector的析构函数
析构函数比较简单，将空间释放，各个指针置为空
~vector() { delete[] _start; _start = _finish = _end_of_storage = nullptr; }
🌻vector的拷贝构造函数
vector(const vector<T>& v) :_start(nullptr) , _finish(nullptr) , _endof_storage(nullptr) { reserve(v.capacity()); for (const auto& e : v) { push_back(e); } }
🌼vector的运算符重载
void swap(vector<T> v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); } // 现代写法 vector<T>& operator=(vector<T> tmp) { swap(tmp); return *this; }
🍂vector容量相关函数
跟容量有关的函数size，capacity，empty，resize，reverse,push_back
size_t size() const { return _finish - _start; } size_t capacity() const { return _endof_storage - _start; } bool empty() const { return _start == _finish; }
reverse
reverse只会改变capacity的大小，并不会改变size的大小
void reserve(size_t n) { if (n > capacity()) // n < capacity()时，则不需要作出反应 { size_t sz = size(); // 先保存以下size的值 T* tmp = new T[n]; // 开辟空间 if (_start) { //memcpy(tmp, _start, sizeof(T)*sz); for (size_t i = 0; i < sz; ++i) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + n; } }
resize
resize不仅会改变size大小，也会改变capacity大小
void resize(size_t n, const T& val = T()) // val=T()用了匿名对象 { if (n > capacity()) { reserve(n); // 开辟额外空间 } if (n > size()) { // 初始化填值 while (_finish < _start + n) { *_finish = val; ++_finish; } } else { _finish = _start + n; } }
注意：C++将内置类型特殊处理过，int/char等等都被升级为了类，所以可以使用int()表示匿名对象
int main() { cout << int() << endl; // int的缺省值为0，所以输出 0 return 0; }
push_back
void push_back(const T& x) { if(_finish == _end_of_storage) { size_t sz = size(); size_t cp = capacity() == 0 ? 4 : capacity() * 2; T* tmp = new <T>(cp); if(_start) { // memcpy(tmp, _start, sizeof(T) * sz); for (size_t i = 0; i < sz; ++i) { tmp[i] = _start[i]; } delete[] _start; } _start = tmp; _finish = _start + sz; _end_of_storage = _start + cp; } *_finish = x; _finish++; }
当探索并深入了解了STL中的vector容器后，我们不禁感叹其强大的功能和灵活性。随着对vector的学习和使用，我们逐渐理解到，一个高效的C++程序不仅仅是代码的堆砌，更是对数据结构、算法和STL等标准库深刻理解的体现。vector的迭代器、容量管理、元素访问以及算法支持等功能，都是我们在日常编程中不可或缺的工具
📖4. 总结
学习vector仅仅是开始。STL（Standard Template Library）还提供了诸如list、set、map等其他强大的容器，每个都有其独特的特点和适用场景。因此，鼓励大家继续深入学习STL，探索其背后的设计理念和实现原理。通过不断实践，我们不仅能够提高编程效率，还能够培养出更加优雅、健壮的代码风格。最后，我想说的是学习是一个永无止境的过程。无论是STL还是其他任何技术，都值得我们不断学习和探索。让我们保持对知识的渴望和好奇心，不断前行，在编程的道路上越走越远
