1.vectorvector是 C 标准模板库STL中最常用的序列容器之一。它封装了动态数组能够自动管理内存支持随机访问且在尾部增删元素效率极高。vector的核心特点连续内存存储元素在内存中紧挨着排列支持O(1)的随机访问通过下标[]或at()。动态扩容当容量不足时会重新分配一块更大的内存通常为当前容量的 2 倍或 1.5倍并将旧元素拷贝/移动过去。尾部高效在末尾插入push_back或删除pop_back元素均摊时间复杂度为O(1)。头部/中间低效在非尾部位置插入或删除元素需要移动大量元素时间复杂度为O(n)。1.1 vector的常用接口演示vector的常用接口以及初始化和string类并没有太多差别照葫芦画瓢即可。1.1.1构造与初始化#include iostream #include vector #include algorithm // for sort, find using namespace std; // 1. 构造与初始化 vectorint v1; // 空 vector vectorint v2(5, 10); // 5 个元素每个都是 10 vectorint v3 {1, 2, 3, 4, 5}; // 列表初始化 (C11)通过{}进行初始化 vectorint v4(v3); // 拷贝构造 v1 v3; //运算符重载1.1.2对容量的操作// 2. 容量相关 cout v3 大小: v3.size() endl; // 元素个数: 5 cout v3 容量: v3.capacity() endl; // 当前分配的内存能容纳多少元素 cout v3 是否为空: v3.empty() endl; // 0 (false) v3.reserve(20); // 预留至少 20 个元素的容量不改变 size cout reserve 后容量: v3.capacity() endl; // 20 v3.shrink_to_fit(); // 请求将容量缩减为刚好匹配 sizeC11非强制 cout shrink 后容量: v3.capacity() endl; v3.resize(10); // 调整 size 为 10新增元素用默认值 (0) 填充 v3.resize(5, 7); // 调整 size 为 5多余元素删除新增元素填充 71.1.3元素访问// 3. 元素访问 // operator[] 和 at() 均为 O(1) cout v3[0] v3[0] endl; // 不检查边界 cout v3.at(1) v3.at(1) endl; // 检查边界越界抛 std::out_of_range cout v3 第一个元素: v3.front() endl; // 首元素引用 cout v3 最后一个元素: v3.back() endl; // 尾元素引用 int* ptr v.data(); // 获取原始指针 等价于 v[0]1.1.4迭代器遍历// 4. 迭代器遍历 cout 使用迭代器遍历: ; for (auto it v3.begin(); it ! v3.end(); it) { cout *it ; } cout endl; cout 使用范围 for 遍历: ; for (auto e : v3) { // C11 范围 for cout e ; } cout endl; // 反向迭代器 cout 反向遍历: ; for (auto rit v3.rbegin(); rit ! v3.rend(); rit) { cout *rit ; } cout endl;1.1.5修改操作// 5. 修改操作增、删、改 // --- 尾部增删 --- v3.push_back(6); // 尾部添加元素 v3.pop_back(); // 删除尾部元素 // --- 任意位置插入/删除 --- auto it v3.begin() 2; // 指向第 3 个元素 v3.insert(it, 99); // 在迭代器位置插入 99元素后移 v3.erase(v3.begin() 1); // 删除第 2 个元素 strs.emplace_back(5, a); // 直接构造 aaaaa无需临时对象 strs.emplace_back(world); // 直接构造 world 避免临时对象的多次构造和析构 // --- 清空与交换 --- vectorint v5 {100, 200}; v3.swap(v5); // 交换 v3 和 v5 的内容 v3.clear(); // 清空所有元素size 0容量不变 //重新分配 v3.assign(4, 8); // 用 4 个 8 替换 v3 当前所有内容 v3.assign({1, 2, 3}); // 用列表替换1.2vector的模拟实现1.2.1 迭代器的分类迭代器分类从弱到强InputIterator← 只读、单次遍历↓OutputIterator← 只写、单次遍历单独分支↓ForwardIterator← 可读写、多次遍历、单向↓BidirectionalIterator← 可双向移动 和 --↓RandomAccessIterator← 支持跳跃、下标访问1.2.2 模拟实现#pragma once #includeiostream #includeassert.h using namespace std; namespace Myvector { templateclass T class vector { public: using iterator T*; using const_iterator const T*; void Print(const vectorT v) { for (auto e : v) { cout e ; } cout endl; } //迭代器的实现 iterator begin() { return _start; } iterator end() { return _finish; } const_iterator begin()const { return _start; } const_iterator end()const { return _finish; } //构造与初始化 vector() { } //初始化列表 vector(initializer_listT il) { reserve(il.size()); for (const auto e : il) { push_back(e); } } //v2(v1) 拷贝构造 vector(const vectorT x) { reserve(x.capacity()); for (const auto e : x) { push_back(e); } } //v1 v2 赋值运算符重载 vectorT operator(const vectorT v) { if (this ! v) { clear(); reserve(v.capacity()); for (const auto e : v) { push_back(e); } } return *this; } //n个“x值 vector(size_t n, const T val T())//匿名对象 内置类型也支持构造和析构函数 { reserve(n); while (n--) { push_back(val); } } //使用迭代器初始化 //函数模板实现迭代器不一定是vector迭代器也可以是其他容器的迭代器 templatetypename InputIterator vector(InputIterator first, InputIterator last) { while (first ! last) { push_back(*first); first; } } //析构函数 ~vector() { if (_start) { delete[] _start; _start _finish _end_of_storage nullptr; } } void clear() { _finish _start; } //容量 bool empty() { return _start _finish; } size_t capacity()const { return _end_of_storage - _start; } size_t size()const { return _finish - _start; } void reserve(size_t n) { if (n capacity()) { size_t sz size(); T* tmp new T[n]; if(_start) { memcpy(tmp, _start, sz*sizeof(T)); delete[] _start; } _start tmp; _finish _start sz; _end_of_storage _start n; } } void resize(size_t n, T val T()) { if (n size()) { _finish _start n; } reserve(n); while (_finish _start n) { *_finish val; _finish; } } //元素访问 T operator[](size_t i)const { assert(i size()); return *(_start i);//_start[i] } T front() { return *(_start); } T back() { return *(--_finish); } //修改操作 void push_back(const T x) { if (_finish _end_of_storage) { reserve(capacity() 0 ? 4 : capacity() * 2); } *_finish x; _finish; } void pop_back() { assert(!empty()); _finish--; } iterator insert(iterator pos,const T x) { assert(pos _start); assert(pos _finish); if (_finish _end_of_storage) { size_t len pos - _start;//保存len长度的原因可能地址发生变化如内存不够重新找的地址原地址会造成非法访问 reserve(capacity() 0 ? 4 : capacity() * 2); pos _start len;// } //后移 iterator end _finish - 1; while (end pos) { *(end 1) *end; end--; } *pos x; _finish; return pos; } iterator erase(iterator pos) { assert(pos _start); assert(pos _finish); iterator it pos 1; while (it ! _finish) { *(it - 1) *it; it; } _finish--; return pos; } private: iterator _start nullptr; iterator _finish nullptr; iterator _end_of_storage nullptr; }; }1.3vector的现代写法vector(const vectorT v) { vectorT tmp(v.begin(), v.end()); swap(tmp); } //v1v2 vectorT operator(vectorT v) { swap(v); return *this; } void swap(vectorT v) { std::swap(_start, v._start); std::swap(_finish, v._finish); std::swap(_end_of_storage, v._end_of_storage); }2.liststd:list是 C 标准库中的双向链表容器。它允许在常数O(N)时间内进行任意位置的插入和删除但不支持通过下标快速访问元素。核心特性底层结构双向链表每个元素有指向前后节点的指针。迭代器双向迭代器支持和--但不支持it n这样的跳跃访问。内存分配元素在内存中不连续每次插入新节点都会独立分配内存。异常安全操作失败时容器状态通常不变强异常保证因为不涉及大规模数据移动。2.1list常用接口演示2.1.1 构造与初始化std::listint l1; // 空链表 std::listint l2 {1, 2, 3, 4, 5}; // 直接初始化 std::listint l3(5, 10); // 5个值为10的元素2.2.2 对容量的操作std::listint l1 {1,5,8}; coutl1.empty()endl; //true coutl1.size()endl; //32.2.3 元素访问//访问元素 (只能访问首尾) std::cout 第一个元素: l2.front() std::endl; std::cout 最后一个元素: l2.back() std::endl;2.2.4 迭代器遍历迭代器失效问题std::listint lst {10, 20, 30, 40, 50}; // 1. 正向遍历 (使用迭代器) std::cout 正向遍历: ; for (std::listint::iterator it lst.begin(); it ! lst.end(); it) { std::cout *it ; } std::cout std::endl; // 10 20 30 40 50 // 2. 反向遍历 (使用反向迭代器) std::cout 反向遍历: ; for (std::listint::reverse_iterator rit lst.rbegin(); rit ! lst.rend(); rit) { std::cout *rit ; } std::cout std::endl; //50 40 30 20 10 // 3. 使用 auto 简化写法 (C11 起) std::cout 使用 auto: ; for (auto it lst.begin(); it ! lst.end(); it) { std::cout *it ; } std::cout std::endl; // 4. 范围的 for 循环 (C11 起, 最推荐) std::cout 范围 for: ; for (auto val : lst) { std::cout val ; } std::cout std::endl;2.2.5 修改操作std::listint l2 {1, 2, 3, 4, 5}; //插入操作 l2.push_back(6); // {1,2,3,4,5,6} l2.push_front(0); // {0,1,2,3,4,5,6} // - insert: 在指定位置前插入 (需要先定位迭代器) auto it l2.begin()2 if (it ! l2.end()) { l2.insert(it, 99); // 在3之前插入99 } //删除操作 l2.pop_back(); // 移除最后一个 l2.pop_front(); // 移除第一个 // erase: 删除指定位置的元素 auto itDel std::find(l2.begin(), l2.end(), 99); if (itDel ! l2.end()) { l2.erase(itDel); // 删除99 } printList(l2, 删除99后); //清空 l2.clear(); // { }2.2 list的模拟实现2.2.1 对节点的封装templateclass T struct list_node { list_node* _prev; list_node* _next; T _data; list_node(const T x T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) { } };2.2.2 对迭代器的封装templateclass T,class Ref //Ref是T引用 struct list_iterator { using Node list_nodeT; using Self list_iteratorT,Ref; Node* _node; list_iterator(Node* node) :_node(node) { } //*it1 Ref operator*() { return _node-_data; } Self operator() { _node _node-_next; return *this; } Self operator(int) { Self tmp(*this); _node _node-_next; return tmp; } Self operator--() { _node _node-_prev; return *this; } Self operator--(int) { Self tmp(*this); _node _node-prev; return tmp; } bool operator!(const Self s)const { return _node ! s._node; } bool operator(const Self s)const { return _node s._node; } }; templateclass T struct list_const_iterator { using Self list_const_iteratorT; using Node list_nodeT; Node* _node; list_const_iterator(Node* node) :_node(node) { } //*it1 const T operator*() { return _node-_data; } Self operator() { _node _node-_next; return *this; } Self operator(int) { Self tmp(*this); _node _node-_next; return tmp; } Self operator--() { _node _node-_prev; return *this; } Self operator--(int) { Self tmp(*this); _node _node-prev; return tmp; } bool operator!(const Self s)const { return _node ! s._node; } bool operator(const Self s)const { return _node s._node; } };2.2.3 list中迭代器的实现templateclass T class list { public: using Node list_nodeT; using iterator list_iteratorT,T; using const_iterator list_iteratorT, const T; iterator begin() { return iterator(_head-_next); } iterator end() { return iterator(_head); } const_iterator begin()const { return const_iterator(_head-_next); } const_iterator end()const { return const_iterator(_head); } private: Node* _head; size_t _size 0; };2.2.4 构造与初始化的实现//实现均在list类中 void empty_init() { _head new Node; _head-_prev _head; _head-_next _head; } //构造空链表 list() { empty_init(); } //列表初始化 list(initializer_listT il) { empty_init(); for (auto e : il) { push_back(e); } } //迭代器区间初始化 templateclass InputIterator list(InputIterator first, InputIterator last) { empty_init(); while (first ! last) { push_back(*first); first; } } list(size_t n, T val T()) { empty_init(); for (size_t i 0; i n; i) //size_t 范围更大避免int数据溢出 { push_back(val); } } list(int n, T val T()) { empty_init(); for (size_t i 0; i n; i) { push_back(val); } } //拷贝构造 list(const listT lt) { empty_init(); for (auto e : lt) { push_back(e); } } //赋值运算符重载 listT operator(const listT lt) { if (this ! lt) { clear(); for (auto e : lt) { push_back(e); } } return *this; } /////////////现代写法 list(const list lt) { empty_init(); list tmp(lt.begin(), lt.end()); swap(tmp); } listT operator(listT tmp) { swap(tmp); return *this; } void swap(listT lt) { std::swap(_head, lt._head); std::swap(_size, lt.size); }2.2.5 其他函数的模拟实现void insert(iterator pos, const T x) { Node* cur pos._node; Node* prev cur-_prev; Node* newnode new Node(x); prev-_next newnode; newnode-_prev prev; newnode-_next cur; cur-_prev newnode; _size; } iterator erase(iterator pos) { Node* cur pos._node; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; --_size; return iterator(next); } void push_back(const T x) { insert(end(), x); } void push_front(const T x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } size_t size() const { return _size; } ~list() { clear(); delete _head; _head nullptr; _size 0; }2.2.6 list模拟实现的完整代码#pragma once #includeiostream using namespace std; namespace My_list { templateclass T struct list_node { list_node* _prev; list_node* _next; T _data; list_node(const T x T()) :_next(nullptr) ,_prev(nullptr) ,_data(x) { } }; templateclass T,class Ref //Ref是T引用 struct list_iterator { using Node list_nodeT; using Self list_iteratorT,Ref; Node* _node; list_iterator(Node* node) :_node(node) { } //*it1 Ref operator*() { return _node-_data; } Self operator() { _node _node-_next; return *this; } Self operator(int) { Self tmp(*this); _node _node-_next; return tmp; } Self operator--() { _node _node-_prev; return *this; } Self operator--(int) { Self tmp(*this); _node _node-prev; return tmp; } bool operator!(const Self s)const { return _node ! s._node; } bool operator(const Self s)const { return _node s._node; } }; templateclass T,class Ref struct list_const_iterator { using Self list_const_iteratorT,Ref; using Node list_nodeT; Node* _node; list_const_iterator(Node* node) :_node(node) { } //*it1 const Ref operator*()const { return _node-_data; } Self operator()const { _node _node-_next; return *this; } Self operator(int)const { Self tmp(*this); _node _node-_next; return tmp; } Self operator--()const { _node _node-_prev; return *this; } Self operator--(int) const { Self tmp(*this); _node _node-prev; return tmp; } bool operator!(const Self s)const { return _node ! s._node; } bool operator(const Self s)const { return _node s._node; } }; templateclass T class list { public: using Node list_nodeT; using iterator list_iteratorT,T; using const_iterator list_iteratorT, const T; iterator begin() { return iterator(_head-_next); } iterator end() { return iterator(_head); } const_iterator begin()const { return const_iterator(_head-_next); } const_iterator end()const { return const_iterator(_head); } void empty_init() { _head new Node; _head-_prev _head; _head-_next _head; } //构造空链表 list() { empty_init(); } //列表初始化 list(initializer_listT il) { empty_init(); for (auto e : il) { push_back(e); } } //迭代器区间初始化 templateclass InputIterator list(InputIterator first, InputIterator last) { empty_init(); while (first ! last) { push_back(*first); first; } } list(size_t n, T val T()) { empty_init(); for (size_t i 0; i n; i) //size_t 范围更大避免int数据溢出 { push_back(val); } } list(int n, T val T()) { empty_init(); for (size_t i 0; i n; i) { push_back(val); } } list(const list lt) { empty_init(); list tmp(lt.begin(), lt.end()); swap(tmp); } listT operator(listT tmp) { swap(tmp); return *this; } void swap(listT lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); } void clear() { iterator il begin(); while (il ! end()) { il erase(il); } } void insert(iterator pos, const T x) { Node* cur pos._node; Node* prev cur-_prev; Node* newnode new Node(x); prev-_next newnode; newnode-_prev prev; newnode-_next cur; cur-_prev newnode; _size; } iterator erase(iterator pos) { Node* cur pos._node; Node* prev cur-_prev; Node* next cur-_next; prev-_next next; next-_prev prev; delete cur; --_size; return iterator(next); } void push_back(const T x) { insert(end(), x); } void push_front(const T x) { insert(begin(), x); } void pop_back() { erase(--end()); } void pop_front() { erase(begin()); } size_t size() const { return _size; } ~list() { clear(); delete _head; _head nullptr; _size 0; } private: Node* _head; size_t _size 0; }; }2.3 list和vector对比3.dequestd::deque是 C 标准库中的双端队列容器全称double-ended queue。它支持在常数时间内在两端进行高效的插入和删除操作同时允许随机访问元素。如果说vector是只能在后端快速操作的动态数组那deque就是在头尾两端都能快速操作的动态数组。我们这里主要式了解一下它的常见接口。文档https://legacy.cplusplus.com/reference/deque/3.1 deque常见接口代码演示#include iostream #include deque int main() { // 1. 构造和初始化 std::dequeint dq1; // 空 std::dequeint dq2 {1, 2, 3, 4, 5}; // 初始化列表 std::dequeint dq3(5, 10); // 5个10 // 2. 两端插入 (高效) dq2.push_back(6); // 尾部插入: {1,2,3,4,5,6} dq2.push_front(0); // 头部插入: {0,1,2,3,4,5,6} // 3. 两端删除(高效) dq2.pop_back(); // 删除尾部: {0,1,2,3,4,5} dq2.pop_front(); // 删除头部: (1,2,3,4,5} // 4. 随机访问 (像数组一样) std::cout dq2[2] std::endl; // 输出: 3 std::cout dq2.at(3) std::endl; // 输出: 4 (会检查边界),越界抛异常 // 5. 中间插入和删除 (性能不如两端,涉及到移动数据) auto it dq2.begin() 2; // 指向元素3 dq2.insert(it, 99); // {1,2,99,3,4,5} it dq2.begin() 3; // 指向元素3 dq2.erase(it); // 删除元素3: {1,2,99,4,5} // 6. 访问首尾元素 std::cout dq2.front() std::endl; // 1 std::cout dq2.back() std::endl; // 5 // 7. 大小和清空 std::cout dq2.size() std::endl; // 5 dq2.clear(); // 清空所有元素 std::cout dq2.empty() std::endl; // true return 0; }4.容器适配器简单来说容器适配器Container Adapter不是“从零造轮子”而是“给现有容器套上一层受限的接口”。它通过封装和强制策略把一个通用容器如deque、vector变成一个行为特定的数据结构栈或队列。4.1 stack文档https://legacy.cplusplus.com/reference/stack/stack的接口很少也很简单看函数名基本就能明白它的功能。我们直接来模拟实现stack。templateclass T, class Container dequeT //底层容器 class stack { stack() { } void push(const T x) { _con.push_back(x); } void pop() { _con.pop_back(); } const T top() { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; };4.2 queue文档https://legacy.cplusplus.com/reference/queue/queue的接口同样很简洁。模拟实现templateclass T, class Container dequeT class queue { public: void push(const T x) { _con.push_back(x); } void pop() { _con.pop_front(); } const T front() { return _con.front(); } const T back() { return _con.back(); } size_t size() const { return _con.size(); } bool empty() const { return _con.empty(); } private: Container _con; };这里我们模拟实现stack和queue就是封装了deque这个容器通过它的接口来实现或者达到stack/queue的功能。选择deque作为底层容器是因为它的接口完美符合stack和queue的特性。stack栈默认底层容器是deque双端队列。因为deque支持push_back、pop_back和back()完美契合栈的LIFO后进先出需求。queue队列默认底层容器也是deque。因为它需要push_back入队和pop_front出队而deque这两者效率都很高。4.3 priority_queuepriority_queue优先级队列也是一种容器适配器它的底层容器默认是vector。当然也可以是任意类型的容器只需满足底层容器支持随机访问迭代器访问并支持以下操作empty()、size()、front()、push_back()、pop_back()。priority_queue的本质就是一个堆且默认为大堆排降序。模拟实现#pragma once #includevector namespace My_priority_queue { //默认大的优先级高 templateclass T,class Container std::vectorint class priority_queue { public: templateclass InputIterator priority_queue(InputIterator first, InputIterator last) :_con(first,last) { //建堆 } //强制编译器生产默认构造函数 priority_queue() default; void adjust_up(int child) { int parent (child - 1) / 2; while (child 0) { if (_con[child] _con[parent]) { std::swap(_con[child], _con[parent]); child parent; parent (child - 1) / 2; } else { break; } } } void adjust_dowm(int parent) { int child parent * 2 1; while (child _con.size()) { if (child 1 _con.size() _con[child 1] _con[child]) { child; } if (_con[parent] _con[child]) { std::swap(_con[parent], _con[child]); parent child; child parent * 2 1; } else { break; } } } void push(const T x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { std::swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_dowm(0); } const T top() { return _con[0]; } bool empty() { return _con.empty(); } private: Container _con; }; }