[数据结构与算法]STL(标准模板库)

概念：

STL：标准模板库，是C++标准库的重要组成部分，STL，英文全称 standard template library，中文可译为标准模板库或者泛型库，其包含有大量的模板类和模板函数，STL 是一些容器、算法和其他一些组件的集合，所有容器和算法都是总结了几十年来算法和数据结构的研究成果，注意，这里提到的容器，本质上就是封装有数据结构的模板类，例如 list、vector、set、map 等，

由概念便可以知道，STL中的所有数据结构都是以模板的方式创建的

容器(数据结构)，算法（算法），迭代器(算法访问容器元素的工具)，

C++ STL 一共提供了六大组件，包括?容器，算法，迭代器，仿函数，配接器和配置器?，彼此可以组合套用。

容器通过配置器取得数据存储空间；

算法通过迭代器存取容器内容；

仿函数可以协助算法完成不同的策略变化；

配接器可以应用于容器、仿函数和迭代器。

1. 容器：包括各种数据结构，如vector，queue， deque,，set， map，用来存放数据，分为序列式容器和关联式容器，实现的角度来讲是一种类模板。

容器可分为：序列式容器，关联式容器

序列式：容器中的元素有顺序关系

关联式：容器中的元素不要求有顺序关系

2、算法：各种常用的算法，问题的解法，如sort (插入，快排，堆排序)， search (二分查找），从实现的角度来讲是一种方法模板。

3、迭代器：从实现的角度来看，迭代器是一种将 operator，operator->，operator++，operator-等指针相关操作赋予重载的类模板，所有的 STL 容器都有自己的迭代器。是容器和算法的粘合剂，算法要通过迭代器才可以访问容器中的元素，迭代器会通过自己的方法找到容器中的元素，

4、仿函数：从实现的角度看，仿函数是一种重载了 operator() 的类或者类模板。可以帮助算法实现不同的策略。

5、配接器：一种用来修饰容器或者仿函数或迭代器接口(参数)的东西。

6、配置器：负责空间配置与管理，从实现的角度讲，配置器是一个实现了动态空间配置、空间管理,空间释放的类模板。

vector(向量)

怎么使用：

1. 包含头文件vector和命名空间std

vector 容器以类模板 vector<T>（ T 表示存储元素的类型）的形式定义在 <vector> 头文件中，并位于 std 命名空间中。

1. 五种创建容器方法：

(1)先创建空容器，再添加容器容量和元素

(2)创建的同时初始化容器元素

vector<T> v5{a,b,c...}

vector<T> v5={a,b,c...}

1. 创建的同时指定容器容量，不给出容器元素

vector<T> v4(n)
说明：包含n个重复执行了值初始化的对象（即值为0）

1. 创建的同时指定容器容量和重复元素

vector<T> v3(n,val)
说明：包含n个重复的val元素

(5)通过存储元素类型相同的其它 vector 容器，也可以创建

的 vector 容器，例如：

vector<T> v1

vector<T> v2(v1)

vector<T> v2 = v1

如果不想复制其它容器中所有的元素，可以用一对指针或者迭代器来指定初始值的范围，例如：

纯文本复制

1. int?array[]={1,2,3};
2. std::vector<int>values(array,?array+2);//values 将保存{1,2}
3. std::vector<int>value1{1,2,3,4,5};
4. std::vector<int>value2(std::begin(value1),std::begin(value1)+3);//value2保存{1,2,3}

vector模板的成员函数：

resize()增加容器元素个数才可以增加容器元素，reserve()增加容器容量，不可以增加容器元素

仅通过 reserve() 成员函数增加 value 容器的容量，其大小并没有改变；但通过 resize() 成员函数改变 value 容器的大小，它的容量可能会发生改变。另外需要注意的是，通过 resize() 成员函数减少容器的大小（多余的元素会直接被删除），不会影响容器的容量。

圆括号 () 和大括号 {} 是有区别的，前者（vector<int>v(20) ）表示元素的个数，而后者（vector<int>v{20} ） 则表示 vector 容器中只有一个元素 20。

我们可能需要将容器的容量和大小保存在变量中，要知道 vector<T> 对象的容量和大小类型都是 vector<T>::size_type 类型。因此，当定义一个变量去保存这些值时，可以如下所示：

1. vector<int>::size_type cap =?value.capacity();
2. vector<int>::size_type size =?value.size();

size_type 类型是定义在由 vector 类模板生成的 vecotr 类中的，它表示的真实类型和操作系统有关，在 32 位架构下普遍表示的是 unsigned int 类型，而在 64 位架构下普通表示 unsigned long 类型。

迭代器的使用：

什么是迭代器：

迭代器就是地址

迭代器和?C++?的指针非常类似，它可以是需要的任意类型，通过迭代器可以指向容器中的某个元素，如果需要，还可以对该元素进行读/写操作。

注意迭代器不是引用，可以用迭代器作实参传递去改变容器内容，但是形参不要定义为引用，直接定义为：

template<typename I>

void container_change(I i){};

?vector 支持迭代器的成员函数

vector<int>::iterator//vector<>模板类中的迭代器

vector<>模板和普通数组很相似，也叫单端数组。

vector<>容器和普通数组的区别：

普通数组的容量是固定的，vector<>容器的容量是可以变的，即动态的。

vector<>容量的动态扩展不是在原有空间的基础上增加新空间，而是找到更大的空间，把原数据拷贝到找到的空间，再释放原空间

vector<int>v2(v1.begin(),v1.end());

将v1中所有的数据复制到v2中

同样功能可以用：

vector<int>v2;

v2.assign(v1.begin(),v1.end());

怎么访问vector容器中的元素：

1. v.at(n)返回容器位置为n的元素的引用（注意第一个位置为0）
2. vector容器也是数组，可以用v[n]访问

所谓泛型编程就是模板编程，泛型就是广泛可以使用的类型，即模板

五类主要的序列容器：

vector,array,list,deque,forward_list

array容器不是array数组，它如同其他容器拥有自己的成员函数

和其它容器不同，array 容器的大小是固定的，无法动态的扩展或收缩，这也就意味着，在使用该容器的过程无法借由增加或移除元素而改变其大小，它只允许访问或者替换存储的元素。

每一个容器的使用都要包含自己的头文件，头文件在std命名空间中

array容器的头文件：<array>

array容器的初始化：

1，array<double, 10> values;

由此，就创建好了一个名为 values 的 array 容器，其包含 10 个浮点型元素。但是，由于未显式指定这 10 个元素的值，因此使用这种方式创建的容器中，各个元素的值是不确定的（array 容器不会做默认初始化操作）

2，array<double,10>values{};

将所有的元素初始化为 0 或者和默认元素类型等效的值：

3,当然，在创建 array 容器的实例时，也可以像创建常规数组那样对元素进行初始化：array<double, 10> values {0.5,1.0,1.5,,2.0};

这里只初始化了前 4 个元素，剩余的元素都会被初始化为 0.0

访问array容器中单个元素

首先，可以通过容器名[]的方式直接访问和使用容器中的元素，这和?C++?标准数组访问元素的方式相同，例如：

1. values[4]?=?values[3]?+?2.O*values[1];

此行代码中，第 5 个元素的值被赋值为右边表达式的值。需要注意的是，使用如上这样方式，由于没有做任何边界检查，所以即便使用越界的索引值去访问或存储元素，也不会被检测到。(越界无检索)

为了能够有效地避免越界访问的情况，可以使用 array 容器提供的 at() 成员函数，例如 :

2，values.at?(4)?=?values.at(3)?+?2.O*values.at(1);

这行代码和前一行语句实现的功能相同，其次当传给 at() 的索引是一个越界值时，程序会抛出 std::out_of_range 异常。因此当需要访问容器中某个指定元素时，建议大家使用 at()，除非确定索引没有越界。（越界可检索）

3，array 容器提供了 data() 成员函数，通过调用该函数可以得到指向容器首个元素的指针

4，在 <array> 头文件中还重载了 get() 全局函数，该重载函数的功能是访问容器中指定的元素，并返回该元素的引用。需要注意的是，该模板函数中，参数的实参必须是一个在编译时可以确定的常量表达式，所以它不能是一个循环变量。

重载函数get()：

形式：get<n>(name)

n为指定容器元素，name为容器名称

LIST--container：

list节点：

list节点是一个双向指针，实质是一个模板结构体

template<class T>

struct _list_node

{
    typedef void* void_pointer;
    void_pointer prev;//previous
    void_pointer next;
    T data;
};

可见，list的节点是一个以结构体形成的双向链表，

而且是一个环状的双向链表

所以list的节点不要求连续

list--iterator:

源码：

?list迭代器是一个模板结构体?

因为list的节点不要求一定连续，所以不同于vector以指针作为迭代器

list--container:

list容器是一个模板类

list的所有的函数，迭代器都是这个模板类的成员

list container的成员函数：

1，begin()

2，end()

3，void push_back(const T& x)

功能：插入一个节点作为尾节点

实现原理：

?4，void push_front(const T& x)

插入一个节点作为头节点

和push_back()相对应

5，iterator erase(iterator position)

移除迭代器position所指的节点

6，void pop_front()

移除头节点

7，void pop_back()

移除尾节点

8，void list<T,Alloc>::clear()

清除所有节点（删除整个链表）

9，void list<T,Alloc>::remove(const T& x)

清除数值为x的所有节点

10，void? list<T,Alloc>::?unique()

清除数值相同的连续节点，保留一个

list成员函数列表：