C++ STL
概念
vector
有 3 个迭代器，分别来指向数据的头(start)，数据的尾(finish)，数组的尾(end_of_storage)。
从而得知数组大小，以及现在分配的空间大小
#include <iostream>
#include <vector>
int main() {
std::vector<int> v;
// 初始时，vector是空的，容量也是0
std::cout << "Size: " << v.size() << ", Capacity: " << v.capacity() << std::endl;
// 添加元素，直到触发扩容
for (int i = 0; i < 15; ++i) {
v.push_back(i);
// 在每次添加元素后，检查是否需要扩容
if (v.size() == v.capacity()) {
std::cout << "append " << i << " after" << std::endl;
}
std::cout<<i<<" ->"<<v.capacity()<<std::endl;
}
// 输出最终的size和capacity
std::cout << "Final Size: " << v.size() << ", Final Capacity: " << v.capacity() << std::endl;
return 0;
}vector 的动态扩容机制：如果原空间大小为 0 则分配 1 个元素，如果大于 0 则分配原空间两倍的新空间，然后把数据拷贝过去
vec[]和vec.at()区别：前者不会检查越界，后者会
需要注意的是：vector 的成员函数都不做边界检查 (at方法会抛异常)，使用者要自己确保迭代器和索引值的合法性。
总结一下 vector 的优缺点。
优点
在内存中是分配一块连续的内存空间进行存储，可以像数组一样操作，并且支持动态扩容。
因此元素的随机访问方便，支持下标访问和 vector.at() 操作。
节省空间。
缺点
由于其顺序存储的特性，vector 插入删除操作的时间复杂度是 O(n)。
只能在末端进行 pop 和 push。
当动态长度超过默认分配大小后，要整体重新分配、拷贝和释放空间。
迭代器
迭代器是STL库的三大组件之一[1]。其作为容器和算法的连接器，将算法对各种容器的遍历操作与具体的容器类型解耦，即迭代器可用于对相应的容器进行元素遍历。这是STL库的核心技术。迭代器是为了提高编程效率而开发的。
迭代器类型
STL库支持的迭代器类型是所有编程语言中最全面的[2]，共有五种：
InputIterator：输入迭代器。支持对容器元素的逐个遍历，以及对元素的读取（input)；
OutputIterator：输出迭代器。支持对容器元素的逐个遍历，以及对元素的写入（output)。
ForwardIterator：前向迭代器。向前逐个遍历元素。可以对元素读取；
BidirectionalIterator：双向迭代器。支持向前向后逐个遍历元素，可以对元素读取。
RandomAccessIterator：随机访问迭代器。支持O(1)时间复杂度对元素的随机位置访问，支持对元素的读取。
输出迭代器可以修改元素，这可能会导致内部结构的调整，进而导致原有的迭代器失效！可能的情况有：
结构和元素顺序变更：比如对map，set，priority_queue插入元素；
内存变化：比如对vector插入元素，可能导致重新申请内存并拷贝！
从上面的描述我们可以很容易的知道他们之间的关系：
实际上在标准库上的实现如下（GNU):
/// Marking input iterators.
struct input_iterator_tag { };
/// Marking output iterators.
struct output_iterator_tag { };
/// Forward iterators support a superset of input iterator operations.
struct forward_iterator_tag : public input_iterator_tag { };
/// Bidirectional iterators support a superset of forward iterator
/// operations.
struct bidirectional_iterator_tag : public forward_iterator_tag { };
/// Random-access iterators support a superset of bidirectional
/// iterator operations.
struct random_access_iterator_tag : public bidirectional_iterator_tag { };迭代器类型成员
一个迭代器的类型成员包含如下：
template<typename _Category, typename _Tp, typename _Distance = ptrdiff_t,
typename _Pointer = _Tp*, typename _Reference = _Tp&>
struct iterator
{
/// One of the @link iterator_tags tag types@endlink.
typedef _Category iterator_category;
/// The type "pointed to" by the iterator.
typedef _Tp value_type;
/// Distance between iterators is represented as this type.
typedef _Distance difference_type;
/// This type represents a pointer-to-value_type.
typedef _Pointer pointer;
/// This type represents a reference-to-value_type.
typedef _Reference reference;
};所有容器的迭代器实现必须都包含如上的五个类型成员！这些成员会作为各个算法的类型参数或者用于iterator traits。
由于各个不同的容器其内部实现不同，且元素的数据结构也不同，所以stl并没有一个统一的iterator类实现。即各个不同容器在内部实现其自己的迭代器，同时对迭代器的各个类型成员重定义，以符合struct iterator的定义规范。
该类最初本想所有的迭代器实现类均继承之，但是从一开始就没有使用过！仅仅成为了可选的实现。所以在C++17中将该类废弃了。
iterator traits
迭代器类型萃取可以提取迭代器的各个类型。
template<typename _Iterator, typename = __void_t<>>
struct __iterator_traits { };
template<typename _Iterator>
struct __iterator_traits<_Iterator,
__void_t<typename _Iterator::iterator_category,
typename _Iterator::value_type,
typename _Iterator::difference_type,
typename _Iterator::pointer,
typename _Iterator::reference>>
{
typedef typename _Iterator::iterator_category iterator_category;
typedef typename _Iterator::value_type value_type;
typedef typename _Iterator::difference_type difference_type;
typedef typename _Iterator::pointer pointer;
typedef typename _Iterator::reference reference;
};
template<typename _Iterator>
struct iterator_traits
: public __iterator_traits<_Iterator> { };迭代器的基本实现
迭代器在c++实际实现为指针。即使用指针访问对应索引的对象。为了更加直观简便的使用迭代器，各个迭代器均对该指针重载了"->"和"*"解引用操作符。而不需要向某些编程语言一样需要执行如下操作：
itr->value();
itr->next();而c++中则：
itr = container.begin();
itr++;
itr--;
*itr;
itr->...以std::list的迭代器实现为例：
template<typename _Tp>
struct _List_iterator
{
typedef _List_iterator<_Tp> _Self;
typedef _List_node<_Tp> _Node;
typedef ptrdiff_t difference_type;
typedef std::bidirectional_iterator_tag iterator_category;
typedef _Tp value_type;
typedef _Tp* pointer;
typedef _Tp& reference;
_List_iterator() _GLIBCXX_NOEXCEPT
: _M_node() { }
explicit
_List_iterator(__detail::_List_node_base* __x) _GLIBCXX_NOEXCEPT
: _M_node(__x) { }
_Self
_M_const_cast() const _GLIBCXX_NOEXCEPT
{ return *this; }
// Must downcast from _List_node_base to _List_node to get to value.
reference
operator*() const _GLIBCXX_NOEXCEPT
{ return *static_cast<_Node*>(_M_node)->_M_valptr(); }
pointer
operator->() const _GLIBCXX_NOEXCEPT
{ return static_cast<_Node*>(_M_node)->_M_valptr(); }
_Self&
operator++() _GLIBCXX_NOEXCEPT
{
_M_node = _M_node->_M_next;
return *this;
}
_Self
operator++(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _M_node->_M_next;
return __tmp;
}
_Self&
operator--() _GLIBCXX_NOEXCEPT
{
_M_node = _M_node->_M_prev;
return *this;
}
_Self
operator--(int) _GLIBCXX_NOEXCEPT
{
_Self __tmp = *this;
_M_node = _M_node->_M_prev;
return __tmp;
}
friend bool
operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node == __y._M_node; }
friend bool
operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
{ return __x._M_node != __y._M_node; }
// The only member points to the %list element.
__detail::_List_node_base* _M_node;
};具体使用
迭代器的常见使用方式有三种。
常规遍历方式
std::vector<int> vec;
...
for (std::vector<int>::iterator itr = vec.begin(); itr != vec.end(); ++itr)
{
// 需要对itr执行解引用！
...
}这是最为常用的方式！
c++11遍历方式
std::vector<int> vec;
...
for(int item : vec)
{
// item已经执行了解引用
...
}c++11工具函数
c++11增加了两个工具函数begin()/end()，支持对原生数组的迭代器访问，同时也支持对已有容器的访问。
int eles[10] = {...};
for (auto itr = begin(eles); itr != end(eles); ++itr)
{
...
}容器迭代器的获取
各个容器对象提供了一系列的获取迭代器的方法。
begin()/end()：获取的迭代器的类型是T::iterator，可通过该迭起修改对应元素。即可变。
cbegin()/end()：获取的迭代器的类型是T:const_iterator，仅能读取对应元素，不可修改之。即常量访问。
rbegin()/rend()：获取的迭代器的类型是T::reverse_iterator。反向访问元素，即从最后一个元素向第一个元素遍历。可修改对应元素，即可变。
crbegin()/crend()：获取的迭代器的类型是T::const_reverse_iterator。反向访问元素，即从最后一个元素向第一个元素遍历。不可修改对应元素，即常量访问。
从c++11开始，提供了工具函数begin()/end()。
获取容器迭代器是算法的第一步。获取后即完成了于容器的解耦。
算法的使用
标准库对容器操作提供了丰富的算法，提高开发人员的开发效率。这些算法全是模板函数，传入迭代器。迭代器的类型在类型参数中显示标明，但是实际的类型检查在运行期间才能判断出来。
下面是几个标准库中提供的函数原型：
template< class InputIt, class T >
typename iterator_traits<InputIt>::difference_type
count( InputIt first, InputIt last, const T &value );
template< class BidirIt1, class BidirIt2 >
BidirIt2 copy_backward( BidirIt1 first, BidirIt1 last, BidirIt2 d_last );
template< class ForwardIt, class UnaryPredicate >
ForwardIt partition( ForwardIt first, ForwardIt last, UnaryPredicate p );下面是一个具体的三大组件联合使用的快速排序的实例：
#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <forward_list>
template <class ForwardIt>
void quicksort(ForwardIt first, ForwardIt last)
{
if(first == last) return;
auto pivot = *std::next(first, std::distance(first,last)/2);
ForwardIt middle1 = std::partition(first, last,
[pivot](const auto& em){ return em < pivot; });
ForwardIt middle2 = std::partition(middle1, last,
[pivot](const auto& em){ return !(pivot < em); });
quicksort(first, middle1);
quicksort(middle2, last);
}
int main()
{
std::vector<int> v = {0,1,2,3,4,5,6,7,8,9};
std::cout << "Original vector:\n ";
for(int elem : v) std::cout << elem << ' ';
auto it = std::partition(v.begin(), v.end(), [](int i){return i % 2 == 0;});
std::cout << "\nPartitioned vector:\n ";
std::copy(std::begin(v), it, std::ostream_iterator<int>(std::cout, " "));
std::cout << " * " " ";
std::copy(it, std::end(v), std::ostream_iterator<int>(std::cout, " "));
std::forward_list<int> fl = {1, 30, -4, 3, 5, -4, 1, 6, -8, 2, -5, 64, 1, 92};
std::cout << "\nUnsorted list:\n ";
for(int n : fl) std::cout << n << ' ';
std::cout << '\n';
quicksort(std::begin(fl), std::end(fl));
std::cout << "Sorted using quicksort:\n ";
for(int fi : fl) std::cout << fi << ' ';
std::cout << '\n';
}容器对迭代器的支持
并不是所有的stl容器均支持迭代器！
支持迭代器的容器
array:
vector:
deque:双向队列
forward_list:单向（前向）列表
list:双向链表
set:
map:
不支持迭代器的容器
不支持迭代器的均是容器适配器，其提供对其他容器的统一接口的访问。
stack：栈
queue：
priority_queue：优先队列
迭代器失效问题
在对容器元素访问的时候，迭代器可能会失效，即迭代器指向的元素已经失效（内存不可访问）。这个是哪怕老手也很容易忽视的问题，并且一旦出问题，非常难以排查定位！
顺序型容器：在修改元素时迭代器不会失效！而删除和插入时可能导致失效。（空间动态扩增，重新申请内存再迁移了，原本内存就释放了）。
解决方法：在vector中insert后会返回一个新的迭代器 it= vec.insert(5)
关联型容器：在修改/删除/插入时均可能导致迭代器失效！
deque
1、deque容器的基本概念
Vector容器是单向开口的连续内存空间，deque则是一种双向开口的连续线性空间，又称双端动态数组。所谓的双向开口，意思是可以在头尾两端分别做元素的插入和删除操作，当然，vector容器也可以在头尾两端插入元素，但是在其头部操作效率奇差，无法被接受。
2、与vector区别不同
Deque容器和vector容器最大的差异。
一在于deque允许使用常数项时间对头端进行元素的插入和删除 操作。
二在于deque没有容量的概念，因为它是动态的以分段连续空间组合而成，随时可以增加一段新的空间并链接起来，换句话说，像vector那样，”旧空间不足而重新配置一块更大空间，然后复制元素，再释放旧空间”这样的事情在deque身上是不会发生的。也因此，deque没有必须要提供所谓的空间保留(reserve)功能. 虽然deque容器也提供了Random Access Iterator,但是它的迭代器并不是普通的指针， 其复杂度和vector不是一个量级，这当然影响各个运算的层面。
因此，除非有必要，我们应该尽可能的 使用vector，而不是deque。对deque进行的排序操作，为了最高效率，可将deque先完整的复制到一个vector中，对vector容器进行排序，再复制回deque。
3、deque容器的实现原理
Deque容器是连续的空间，至少逻辑上看来如此，连续现行空间总是令我们联想到array和vector,array 无法成长，vector虽可成长，却只能向尾端成长，而且其成长其实是一个假象，
事实上(1) 申请更大空间 (2)原数据复制新空间 (3)释放原空间 三步骤，
如果不是vector每次配置新的空间时都留有余裕，其成长假象所带来的代价是非常昂贵的。 Deque是由一段一段的定量的连续空间构成。一旦有必要在deque前端或者尾端增加新的空间，便配置一段连续定量的空间，串接在deque的头端或者尾端。Deque最大的工作就是维护这些分段连续的内存空间的整体性的假象，并提供随机存取的接口，避开了重新配置空间，复制，释放的轮回，代价就是复杂的迭代器架构。 既然deque是分段连续内存空间，那么就必须有中央控制，维持整体连续的假象，数据结构的设计及迭代器的前进后退操作颇为繁琐。Deque代码的实现远比vector或list都多得多。 Deque采取一块所谓的map(注意，不是STL的map容器)作为主控，这里所谓的map是一小块连续的内存空间，其中每一个元素(此处成为一个结点)都是一个指针，指向另一段连续性内存空间，称作缓冲区。缓冲区才是deque的存储空间的主体。
4、deque容器常用API
4.1deque构造函数
deque<T> deqT;//默认构造形式
deque(beg, end);//构造函数将[beg, end)区间中的元素拷贝给本身。
deque(n, elem);//构造函数将n个elem拷贝给本身。
deque(const deque &deq);//拷贝构造函数4.2deque赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
deque& operator=(const deque &deq); //重载等号操作符
swap(deq);// 将deq与本身的元素互换案例：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<deque>
using namespace std;
void printDequeInt(deque<int> &d)
{
deque<int>::iterator it = d.begin();
for(;it!=d.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
void test01()
{
deque<int> d1(5,100);
printDequeInt(d1);
deque<int> d2;
d2.assign(d1.begin(), d1.begin()+2);
printDequeInt(d2);
deque<int> d3(5,10);
printDequeInt(d1);
printDequeInt(d3);
d1.swap(d3);
printDequeInt(d1);
printDequeInt(d3);
}
int main()
{
test01() ;
return EXIT_SUCCESS;
}
4.3deque大小操作
deque.size();//返回容器中元素的个数
deque.empty();//判断容器是否为空
deque.resize(num);//重新指定容器的长度为num,若容器变长，则以默认值填充新位置。如果容器变 短，则末尾超出容器长度的元素被删除。
deque.resize(num, elem); //重新指定容器的长度为num,若容器变长，则以elem值填充新位置,如果 容器变短，则末尾超出容器长度的元素被删除4.4deque双端插入和删除操作
push_back(elem);//在容器尾部添加一个数据
push_front(elem);//在容器头部插入一个数据
pop_back();//删除容器最后一个数据
pop_front();//删除容器第一个数据案例：
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<deque>
using namespace std;
void printDequeInt(deque<int> &d)
{
deque<int>::iterator it = d.begin();
for(;it!=d.end(); it++)
{
cout<<*it<<" ";
}
cout<<endl;
}
void test01()
{
deque<int> d1;
d1.push_back(10);
d1.push_back(20);
d1.push_back(30);
d1.push_front(40);
d1.push_front(50);
d1.push_front(60);
printDequeInt(d1);
//尾部删除
d1.pop_back();
printDequeInt(d1);//60 50 40 10 20
d1.pop_front();
printDequeInt(d1);//50 40 10 20
cout<<d1[2]<<endl;//10
cout<<d1.at(2)<<endl;//10
d1.insert(d1.begin()+2, 3, 100);
printDequeInt(d1);//50 40 100 100 100 10 20
d1.erase(d1.begin()+2, d1.begin()+5);
printDequeInt(d1);//50 40 10 20
}
int main()
{
test01() ;
return EXIT_SUCCESS;
}
4.5deque数据存取
at(idx);//返回索引idx所指的数据，如果idx越界，抛出out_of_range。
operator[];//返回索引idx所指的数据，如果idx越界，不抛出异常，直接出错。
front();//返回第一个数据。
back();//返回最后一个数据4.6deque插入操作
insert(pos,elem);//在pos位置插入一个elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。4.7deque删除操作
clear();//移除容器的所有数据
erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。list
1、list容器基本概念
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相较于vector的连续线性空间，list就显得负责许多，它的好处是每次插入或者删除一个元素，就是配置或者释放一个元素的空间。因此，list对于空间的运用有绝对的精准，一点也不浪费。而且，对于任何位置的元素插入或元素的移除，list永远是常数时间。 List和vector是两个最常被使用的容器。 List容器是一个双向链表。
采用动态存储分配，不会造成内存浪费和溢出 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素 链表灵活，但是空间和时间额外耗费较大。
2、list容器的迭代器（双向迭代器）
List容器不能像vector一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。List迭代器必须有能力指向list的节点，并有能力进行正确的递增、递减、取值、成员存取操作。所谓”list正确的递增，递减、取值、成员取用”是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员。 由于list是一个双向链表，迭代器必须能够具备前移、后移的能力，所以list容器提供的是Bidirectional Iterators. List有一个重要的性质，插入操作和删除操作都不会造成原有list迭代器的失效。这在vector是不成立的，因为vector的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效，甚至List元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受任何影响。 list容器不仅是一个双向链表，而且还是一个循环的双向链表。
案例：怎么判断一个迭代器是随机访问迭代器还是双向迭代器
简单判断：迭代器+1，如果成功，就是随机访问迭代器，否就是双向迭代器。
int main()
{
vector<int> v;
v.begin()+1;//随机访问迭代器
list<int> l;
//l.begin() +1;//err 双向迭代器 不允许+1
}3、list容器常用的API
3.1 list构造函数
list<T> lstT;//list采用采用模板类实现,对象的默认构造形式：
list(beg,end);//构造函数将[beg, end)区间中的元素拷贝给本身。
list(n,elem);//构造函数将n个elem拷贝给本身。
list(const list &lst);//拷贝构造函数。3.2 list数据元素的插入和删除操作
push_back(elem);//在容器尾部加入一个元素
pop_back();//删除容器中最后一个元素
push_front(elem);//在容器开头插入一个元素
pop_front();//从容器开头移除第一个元素
insert(pos,elem);//在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);//在pos位置插入n个elem数据，无返回值。
insert(pos,beg,end);//在pos位置插入[beg,end)区间的数据，无返回值。
clear();//移除容器的所有数据 erase(beg,end);//删除[beg,end)区间的数据，返回下一个数据的位置。
erase(pos);//删除pos位置的数据，返回下一个数据的位置。
remove(elem);//删除容器中所有与elem值匹配的元素。3.3 list大小操作
size();//返回容器中元素的个数
empty();//判断容器是否为空
resize(num);//重新指定容器的长度为num， 若容器变长，则以默认值填充新位置。 如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem);//重新指定容器的长度为num， 若容器变长，则以elem值填充新位置。 如果容器变短，则末尾超出容器长度的元素被删除。3.4 list赋值操作
assign(beg, end);//将[beg, end)区间中的数据拷贝赋值给本身。
assign(n, elem);//将n个elem拷贝赋值给本身。
list& operator=(const list &lst);//重载等号操作符
swap(lst);//将lst与本身的元素互换3.5 list的数据存取
front();//返回第一个元素。
back();//返回最后一个元素。 3.6.4.6 list反转排序
reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序3.6 list反转排序
reverse();//反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort(); //list排序
