STL概述

什么是C++标准模板库（STL）

标准模板库STL（Standard Template Library），是C++标准库的一部分，不需要单独安装，只需要#include头文件。

C++对模板（Template）支持得很好，STL就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。

C++语言的核心优势之一就是便于软件的复用。

C++语言有两个方面体现了复用：

• 面向对象的继承和多态机制

• 通过模板的概念实现了对泛型程序设计的支持

C++中的模板，就好比英语作文的模板，只换主题，不换句式和结构。对应到C++模板，就是只换类型，不换方法。

STL的优势

STL封装了很多实用的容器，省时省力，能够让你将更多心思放到解决问题的步骤上，而非费力去实现数据结构诸多细节上

STL六大组件

1、容器（数据结构）：用来存数据的。

• 序列式容器 vector、list、deque
• 关联式容器 set、map
• 无序关联式容器 unordered_set、unordered_map

2、迭代器：看成是一种指针，称为泛型指针。

3、算法：可以对容器中的数据进行相应的操作。

4、适配器

• 容器适配器 优先级队列
• 算法适配器
• 迭代器的适配器 （源码）

5、函数对象（仿函数）：做定制化操作。

6、空间配置器（allocator）：空间的申请与释放。（研究基本使用 + 原理 + 源码）

程序 = 容器（数据结构） + 算法

序列式容器

1、初始化

三种序列化容器：vector、list、deque都支持以下5种初始化的方式

// 1、创建空对象
vector<类型名> 变量名;

// 2、创建count个value
vector<int> number(10,3);	// 创建10个3

// 3、迭代器范围
int arr[5] = {1,2,3,4,5};
vector<int> number(arr,arr + 5);	// 左闭右开 [,)

// 4、拷贝构造函数与移动构造函数

// 5、大括号的方式
vector<int> number = {1,23,4,13};

2、遍历

三种序列式容器，其中：list是没有下标的，不支持下标访问运算符。其他的三种遍历的方式，三种容器都支持

vector<int> num = {1,2,3,4,5};
// 1.使用下标访问运算符进行遍历
for(size_t idx = 0;idx != num.size();++idx)
{
    cout << num[idx] << "   ";
}
cout << endl;

// 2.使用迭代器进行遍历
// vector的迭代器不支持it < num.end()的写法，因此循环条件只能it!=num.end()   
vector<int>::iterator it;   // 泛型指针
// vector<int>::iterator it = num.begin();
// for(;it != num.end();++it)
for(it = num.begin();it != num.end();++it)
{
    cout << *it << "    ";
}
cout << endl;

// 3.C++11新特性，for与auto
for(auto& elem : num)
{
    cout << elem << "   ";
}

注意：list不支持下标（因为list底层用的链表，链表是不支持随机访问的！）

3、插入与删除

3.1、在尾部插入和删除

三种容器在尾部进行插入与删除的操作是完全一样的

vector<int> num = {1,2,3,4,5};
num.push_back(6);	// 插入
num.pop_back();		// 删除

3.2、在头部插入和删除

deque与list支持在头部进行插入与删除，但是vector没有在头部进行插入与删除的操作

list<int> num = {1,2,3,4,5};
num.push_front(0);
num.pop_front();

Q：为什么vector不支持在头部进行插入和删除操作？

A：因为vector中的元素是连续的，如果在头部插入（删除）元素，那么后面的所有元素都要后移（前移），时间复杂度是O(N)

3.3、在任意位置插入

三种序列式容器在任意位置插入元素的四种方法：

std::vector<int> demo{1,2};
//第一种格式用法
demo.insert(demo.begin() + 1, 3);//{1,3,2}
//第二种格式用法
demo.insert(demo.end(), 2, 5);//{1,3,2,5,5}
//第三种格式用法
std::array<int,3> test{ 7,8,9 };
demo.insert(demo.end(), test.begin(), test.end());//{1,3,2,5,5,7,8,9}
//第四种格式用法
demo.insert(demo.end(), { 10,11 });//{1,3,2,5,5,7,8,9,10,11}

emplace()

emplace() 是C++11 标准新增加的成员函数，用于在 vector 容器指定位置之前插入一个新的元素。

再次强调，emplace() 每次只能插入一个元素，而不是多个。

该函数的语法格式如下：

iterator emplace (const_iterator pos, args...);

其中，pos 为指定插入位置的迭代器；args... 表示与新插入元素的构造函数相对应的多个参数；该函数会返回表示新插入元素位置的迭代器。

简单的理解 args...，即被插入元素的构造函数需要多少个参数，那么在 emplace() 的第一个参数的后面，就需要传入相应数量的参数。

3.4、vector容器在任意位置删除元素

// 删除 vector 容器中 pos 迭代器指定位置处的元素，并返回指向被删除元素下一个位置元素的迭代器。该容器的大小（size）会减 1，但容量（capacity）不会发生改变。
iterator erase(pos);


// 用erase函数删除vector中连续重复的元素
void test()
{
    vector<int> num = {1,3,6,6,6,6,6,6,7,5};
    // 注意这里不能 ++it
    for(auto it = num.begain();it != num.end();)
    {
        if(6 == *it)
        {
            num.erase(it);
        }
        else
        {
            ++it;
        }
    }
}

4、元素的清空

// 删除容器中所有的元素，使其变成空的容器。(没有回收内存)
void clear();
// 回收空间
void shrink_to_fit();

对于deque和vector，使用clear函数只是将元素清空，但并没有回收内存，需要配合shrink_to_fit()函数将内存回收；

对于list，元素删除了结点就会删除，不存在回收空间的函数。

5、vector的原理剖析

• _M_start，指向第一个元素；

• _M_finish，指向最后一个元素的下一个位置；

• _M_end_of_storage，最后一个空间的下一个位置

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class vector
{
public:
    //类型萃取（重要）
    typedef _Tp value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type* iterator;
    typedef const value_type* const_iterator;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef size_t size_type;
    typedef ptrdiff_t difference_type;
    
    //为了严格表明_Base::allocator_type是一种类型，所以加上typename关键字进行强调
    typedef typename _Base::allocator_type allocator_type;
    
    //vector的下标访问运算符的重载
    reference operator[](size_type __n)
    { 
        return *(begin() + __n); 
    }
    
    void _M_range_check(size_type __n) const 
    {
       if (__n >= this->size())
           __stl_throw_range_error("vector");
    }

    //总结：通过随机获取元素，可以使用at，也可以直接使用下标，但是at比下标访问更安全，因为有范围检查
    reference at(size_type __n)
    {
		_M_range_check(__n); 
		return (*this)[__n]; 
    }
};

6、deque的原理剖析

和 vector 容器采用连续的线性空间不同，deque 容器存储数据的空间是由一段一段等长的连续空间构成，各段空间之间并不一定是连续的，可以位于在内存的不同区域（片段内部是连续的，片段之间是不连续，即逻辑上是连续的，但是物理上是不连续）。

为了管理这些连续空间，deque 容器用数组（数组名假设为 map）存储着各个连续空间的首地址。也就是说，map 数组（中控器）中存储的都是指针，指向那些真正用来存储数据的各个连续空间

通过建立 map 数组，deque 容器申请的这些分段的连续空间就能实现“整体连续”的效果。换句话说，当 deque 容器需要在头部或尾部增加存储空间时，它会申请一段新的连续空间，同时在 map 数组的开头或结尾添加指向该空间的指针，由此该空间就串接到了 deque 容器的头部或尾部。

deque容器迭代器的底层实现

由于 deque 容器底层将序列中的元素分别存储到了不同段的连续空间中，因此要想实现迭代器的功能，必须先解决如下 2 个问题：

1. 迭代器在遍历 deque 容器时，必须能够确认各个连续空间在 map 数组中的位置；
2. 迭代器在遍历某个具体的连续空间时，必须能够判断自己是否已经处于空间的边缘位置。如果是，则一旦前进或者后退，就需要跳跃到上一个或者下一个连续空间中。

为了实现遍历 deque 容器的功能，deque 迭代器定义了如下的结构：

template <class _Tp, class _Ref, class _Ptr>
struct _Deque_iterator {
  /*......*/
  _Tp* _M_cur;
  _Tp* _M_first;
  _Tp* _M_last;
  _Map_pointer _M_node;		//_Map_pointer 等价于 T**
  /*......*/
}

迭代器内部包含 4 个指针，它们各自的作用为：

• cur：指向当前正在遍历的元素；
• first：指向当前连续空间的首地址；
• last：指向当前连续空间的末尾地址；
• node：它是一个二级指针，用于指向 map 数组中存储的指向当前连续空间的指针。

借助这 4 个指针，deque 迭代器对随机访问迭代器支持的各种运算符进行了重载，能够对 deque 分段连续空间中存储的元素进行遍历。

deque容器的底层实现

deque 容器除了维护 map 数组，还需要维护 start、finish 这 2 个 deque 迭代器。以下为 deque 容器的定义：

template <class _Tp, class _Alloc = __STL_DEFAULT_ALLOCATOR(_Tp) >
class deque : protected _Deque_base<_Tp, _Alloc> {
// ...
protected:
  _Tp** _M_map;
  iterator _M_start;
  iterator _M_finish;
}

• start 迭代器记录着 map 数组中首个连续空间的信息
• finish 迭代器记录着 map 数组中最后一个连续空间的信息

另外需要注意的是，和普通 deque 迭代器不同，start 迭代器中的 cur 指针指向的是连续空间中首个元素；而 finish 迭代器中的 cur 指针指向的是连续空间最后一个元素的下一个位置。

借助 start 和 finish，以及 deque 迭代器中重载的诸多运算符，就可以实现 deque 容器提供的大部分成员函数。

7、迭代器失效问题

迭代器的失效问题：对容器的操作影响了元素的存放位置，称为迭代器失效。

失效情况：

1. 当容器调用erase()方法后，当前位置到容器末尾元素的所有迭代器全部失效。
2. 当容器调用insert()方法后，当前位置到容器末尾元素的所有迭代器全部失效。
3. 如果容器扩容，在其他地方重新又开辟了一块内存。原来容器底层的内存上所保存的迭代器全都失效了。
4. 不同容器的迭代器，是不能进行比较运算的。

对于list而言，插入的时候，迭代器是跟着结点走了，它在使用的时候，不会存在什么问题。但是对于vector而言，插入元素的大小会影响vector底层的扩容，有可能会导致迭代器失效。所以为了解决这个问题，每次操作迭代器时候，最好可以提前更新迭代器的位置，让迭代器指向新的空间的位置，这样就保证不会出错。

特别的，对于deque而言，去进行insert操作的时候，也有可能迭代器失效，所以最好还是可以每次使用迭代器的时候，像vector一样，将迭代器的位置进行更新，指向新的空间的位置。

8、list的特殊用法

8.1、sort函数

void sort();

template< class Compare >
void sort( Compare comp );

template<typename T>
struct CompareList
{
    // 参数中的const表明该函数不能修改lhs和rhs
    // 第二个const会将成员函数声明为常量成员函数，表明这个函数内不允许修改类的数据成员
    bool operator()(const T& lhs,const T& rhs) const
    {
        return lhs < rhs;
    }
};

template<typename T>
void display(T& num)
{
    for(auto& elem : num)
    {
        cout << elem << "   ";
    }
    cout << endl;
}

void test()
{
    list<int> num = {9,37,19,0,1,7,8,7,2,3,4};
    display(num);
    num.sort(CompareList<int>());   // 自己实现比较规则
    display(num);
}

• num.sort()，默认情况，会按照从小到大的顺序进行排序
• num.sort(std::less<int>())，按照小于的比较规则进行比较（从小到大排序）
• num.sort(std::greate<int>())，按照大于的比较规则进行比较（从大到小排序）
• 自己实现比较规则

8.2、merge函数

// 两个链表进行merge的时候，需要分别将两个链表从小到大排序，然后再进行merge，以防达不到合并后排序的效果
void merge( list& other );

void test()
{
    list<int> num = {9,37,19,0,1,7,8,7,2,3,4};
    list<int> num1 = {9,2,34,5,323,3234,54523,1342,32};
    num.sort();
    num1.sort();
    num.merge(num1);
    display(num);
}

8.3、splice函数

list::splice实现list拼接的功能。将源list的内容部分或全部元素删除，并插入到目的list。

 int main()
 {
	 list<int>li1{ 1,2,3,4 };
	 list<int>li2{ 11,12,13,14 };
 
	 list<int>::iterator it = li1.begin();
	 it++; // 插入到第一个元素后面
 
	 li1.splice(it, li2);
	 if (li2.empty()) {
		 cout << "li2 is empty" << endl;
	 }
	 else
	 {
		 cout << "li2 is  not empty" << endl;
	 }
 
	 cout << "li1 is" << endl;
	 for (list<int>::iterator item = li1.begin(); item != li1.end(); ++item) {
		 cout << *item << " ";
	 }
     return 0;
}

8.4、其他

void reverse() noexcept;		// 反转容器中元素的顺序。没有引用或迭代器失效。
void unique();					// 去除重复元素（需要先将元素排序）