C++ | 一文了解【STL】

迷南。 2022-09-11 08:21 210阅读 0赞

### 文章目录 ###

*   *   *  一、概述
         *   *  1.1 容器
             *  1.2 算法
             *  1.3 迭代器
         *  二、常用容器
         *   *  2.1 vector
             *   *  2.1.1 常用成员函数
             *  2.2 string
             *   *  2.2.1 常用成员函数
             *  3.3 deque
             *   *  2.3.1 常用成员函数
             *  2.4list
             *   *  2.4.1 常见成员函数
             *  2.5 set/multiset
             *   *  2.5.1 常见成员函数
             *  2.6 map/multimap
             *   *  2.6.1 常见成员函数
             *  2.7 stack
             *   *  2.7.1 常见成员函数
             *  2.8 queue
             *   *  2.8.1 常见成员函数
             *  2.9 priority\_queue
             *   *  2.9.1 常见成员函数

### 一、概述 ###

`STL(Standard Template Library)`：

>  *  功能强大基于模板的容器库；
>  *  主要分为三部分：
>     
>      *  容器 - `container`；
>      *  算法 - `alogrithm`；
>      *  迭代器 - `iterator`；

#### 1.1 容器 ####

<table> 
 <thead> 
  <tr> 
   <th>数据结构</th> 
   <th>说明</th> 
   <th>实现头文件</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>向量<code>vector</code></td> 
   <td>连续存储。数组，快速随机访问</td> 
   <td><code>&lt;vector&gt;</code></td> 
  </tr> 
  <tr> 
   <td>字符串<code>string</code></td> 
   <td>字符串处理容器</td> 
   <td><code>&lt;string&gt;</code></td> 
  </tr> 
  <tr> 
   <td>双端队列<code>deque</code></td> 
   <td>连续存储的指向不同元素的指针组成的数组。底层为一个中央控制器和多个缓冲区，支持首尾元素快速增删，也支持结点快速增删</td> 
   <td><code>&lt;deque&gt;</code></td> 
  </tr> 
  <tr> 
   <td>链表<code>list</code></td> 
   <td>由结点组成的链表，底层是双向链表</td> 
   <td><code>&lt;list&gt;</code></td> 
  </tr> 
  <tr> 
   <td>队列 <code>queue</code></td> 
   <td>先进先出，一般用deque或list实现</td> 
   <td><code>&lt;queue&gt;</code></td> 
  </tr> 
  <tr> 
   <td>栈<code>stack</code></td> 
   <td>后进先出 ，一般用deque或list实现</td> 
   <td><code>&lt;stack&gt;</code></td> 
  </tr> 
  <tr> 
   <td>优先队列<code>priority_queue</code></td> 
   <td>元素进出顺序由某个谓词或关系函数决定，底层为<code>vector</code>或<code>duque</code></td> 
   <td><code>&lt;queue&gt;</code></td> 
  </tr> 
  <tr> 
   <td>集合<code>set</code>/多重集合<code>multiset</code></td> 
   <td>由结点组成的红黑树，set中所有<code>元素</code>有序不重复，multiset中所有<code>关键字</code>有序重复</td> 
   <td><code>&lt;set&gt;</code></td> 
  </tr> 
  <tr> 
   <td>映射<code>map</code>/多重映射<code>multimap</code></td> 
   <td>由(关键字,值)对组成的集合，底层为红黑树，map的所有关键字有序但不重复，multimap中关键字有序可重复</td> 
   <td><code>&lt;map&gt;</code></td> 
  </tr> 
 </tbody> 
</table>

#### 1.2 算法 ####

> 算法主要头文件：`<algorithm>`、`<numeric>`、`<functional>`；

`<algorithm>`

> 比较、交换、查找、遍历、复制、修改、删除、排序、合并；

`<numeric>`

> 简单的数学运算模板；

`<functional>`

> 用于声明关系函数对象；

#### 1.3 迭代器 ####

>  *  `iterator`：指向容器中`存放元素`的迭代器，用于`正向遍`历容器中的元素；
>  *  `const_iterator`：指向容器中存放元素的`常量`迭代器，只能`读取`容器中的元素；
>  *  `reverse_iterator`：指向容器中存放元素的`反向`迭代器，用于反向遍历容器中的元素；
>  *  `const_reverse_iterator`：指向容器中存放元素的`常量反向`迭代器，只能`读取`容器中的元素。
>  *  `容器<数据类型>::iterator it`

**常用运算符**：

>  *  `++`：正向移动迭代器；
>  *  `-`：反向移动迭代器；
>  *  `*`：返回迭代器所指的元素值；

### 二、常用容器 ###

#### 2.1 vector ####

>  *  相当于`数组`，存储具有`相同数据`类型的一组元素；
>  *  随机访问元素；
>  *  插入、删除元素较慢；
>  *  空间不够时，会重新分配按两倍大小扩展；

##### 2.1.1 常用成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：返回当前实际元素个数；
>  *  `[ ]`：返回指定下标的元素；
>  *  `reserve(n)`：预分配n个元素的存储空间；
>  *  `capacity()`：返回当前所能容纳的个数；
>  *  `resize(n)`：调整容器大小；
>  *  `push_back()`：尾部添加元素；
>  *  `insert(pos, elem)`：在pos位置插入elem；
>  *  `front()`：获取第一个元素；
>  *  `back()`：获取最后一个元素；
>  *  `erase()`：删除某个迭代器；
>  *  `clear()`：清空所有元素；
>  *  `begin()`：返回迭代器的第一个元素；
>  *  `end()`：返回迭代器最后一个元素后面的一个位置；
>  *  `rbegin()`：返回迭代器最后一个元素；
>  *  `rend()`：返回迭代器第一个元素的前一个位置。

#### 2.2 string ####

**创建的几种方式**：

>  *  `string()`：建立一个空的字符串；
>  *  `string(const string& str)`：用str建立当前字符串；
>  *  `string(const string& str, size_type str_idx, size_type str_num)`：用str起始于`str_idx`建立，str\_num个字符；
>  *  `string(const char* cstr)`：用char \*建立；

##### 2.2.1 常用成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：返回当前实际字符个数(size\_type)；
>  *  `length()`：当前字符个数；
>  *  `[idx]`：idx位置的字符；
>  *  `at(idx)`：返回idx位置的字符，若有错误会弹出；
>  *  `compare(const string& str)`：返回当前字符串与str的`比较`结果，`0-相等，前<后-1，否则为1`；
>  *  `append(cstr)`：添加一个字符串；
>  *  `insert(size_type idx, const string& str )`：在idx处插入一个字符str；
>  *  `find(string& s, size_type pos)`：从pos开始查找s，找到则`返回其位置，否则返回-1`；
>  *  `replace(size_type idx, size_type len, const string& str)`：将当前字符串中idx开始的len个字符替换成str；
>  *  `replace(iterator beg, iterator end, const string& str)`：将当前字符串中由迭代器beg和end间字符都替换成str；
>  *  `substr(size_type idx)`：返回当前字符串起始于idx的子串；
>  *  `substr(size_type idx, size_type len)`：返回当前字符串期数idx的长度为len的子串；
>  *  `clear()`：删除所有字符；
>  *  `erase()`：删除所有字符；
>  *  `erase(size_type idx)`：删除当前字符串从idx开始的所有字符；
>  *  `erase(size_type idx, size_type len)`：删除当前字符串从idx开始的len个字符；

#### 3.3 deque ####

>  *  每个块中元素的地址时连续的；
>  *  块之间的地址是不连续的；
>  *  可快速随机访问；
>  *  在中间插入、删除速度较慢；

**创建的几种方式**：

>  *  `deque<数据类型> dq`；
>  *  `deque<数据类型> dq(10)`：指定初始大小为10；
>  *  `deque<数据类型> dq(10, 5)`：10个初始元素的初值为5；
>  *  `deque<数据类型> dq(dq1.begin(), dq1.end())`：用dq1的元素去初始化dp；

##### 2.3.1 常用成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：元素个数；
>  *  `front()`：取对头元素；
>  *  `back()`：取队尾元素；
>  *  `push_front(elem)`：在对头插入elem；
>  *  `push_back(elem)`：在队尾插入elem；
>  *  `pop_front()`：删除队头元素；
>  *  `pop_back()`：删除队尾元素；
>  *  `erase()`：删除一个或几个元素；
>  *  `clear()`：删除双端队列容器中的所有元素；
>  *  `begin()`：返回第一个元素；
>  *  `end()`：返回最后一个元素后面一个位置；
>  *  `rbegin()`：返回容器最后一个元素；
>  *  `rend()`：返回第一个元素前的一个位置；

#### 2.4list ####

**几种创建方式**

>  *  `list<数据类型> l`;
>  *  `list<数据类型> l(10)`：指定初始大小为10；
>  *  `list<数据类型> l(10, 5)`：10个初始元素的初值为5；
>  *  `list<数据类型> l(a, a+5)`：用a\[0~4\]初始化l；

##### 2.4.1 常见成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：元素个数；
>  *  `push_back()`：在队尾插入elem；
>  *  `pop_back()`：删除队尾元素；
>  *  `remove()`：删除指定值的元素；
>  *  `remove_if(cmp)`：删除满足条件的元素；
>  *  `erase()`：删除一个或几个元素；
>  *  `unique()`：删除`相邻的重复`元素；
>  *  `clear()`：删除双端队列容器中的所有元素；
>  *  `insert(pos, elem)`：在pos插入elem
>  *  `insert(pos, n, elem)`：pos位置插入n个元素elem；
>  *  `insert()`
>  *  `begin()`：返回第一个元素；
>  *  `end()`：返回最后一个元素后面一个位置；
>  *  `rbegin()`：返回容器最后一个元素；
>  *  `rend()`：返回第一个元素前的一个位置；

#### 2.5 set/multiset ####

>  *  都是集合类模板，其元素值称为关键字；
>  *  set元素的关键字是唯一的，若存在则不插入；
>  *  multiset中元素的关键字不唯一；
>  *  默认按关键字自动升序；

##### 2.5.1 常见成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：元素个数；
>  *  `insert()`：插入元素；
>  *  `erase()`：删除一个或几个元素；
>  *  `count()`：关键字出现的次数；
>  *  `find()`：若找到则返回该元素的迭代器，否则返回end()值；
>  *  `clear()`：删除双端队列容器中的所有元素；
>  *  `upper_bound()`：返回迭代器，指向关键字大于k的第一个元素；
>  *  `lower_bound()`：返回迭代器，指向关键字不小于k的第一个元素；
>  *  `begin()`：返回第一个元素；
>  *  `end()`：返回最后一个元素后面一个位置；
>  *  `rbegin()`：返回容器最后一个元素；
>  *  `rend()`：返回第一个元素前的一个位置；

#### 2.6 map/multimap ####

>  *  map和multimap都是映射类模板；
>  *  映射是实现与值关系的存储结构，可使用key来访问value；
>  *  map支持`[]`，而multimap不支持；

##### 2.6.1 常见成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：元素个数；
>  *  `map[key]`：返回关键字为key的引用，若不存在，则以key为关键字插入；
>  *  `insert()`：插入元素，返回该位置；
>  *  `find()`：查找元素；
>  *  `clear()`：删除双端队列容器中的所有元素；
>  *  `count()`：关键字出现的次数；
>  *  `begin()`：返回第一个元素；
>  *  `end()`：返回最后一个元素后面一个位置；
>  *  `rbegin()`：返回容器最后一个元素；
>  *  `rend()`：返回第一个元素前的一个位置；

#### 2.7 stack ####

>  *  具有`后进先出`的特点；
>  *  默认底层为`deque`；

##### 2.7.1 常见成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：元素个数；
>  *  `push(elem)`：元素进栈；
>  *  `top()`：返回栈顶元素；
>  *  `pop()`：元素出栈；

#### 2.8 queue ####

>  *  具有先进先出的特点；

##### 2.8.1 常见成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：元素个数；
>  *  `front()`：返回队头元素；
>  *  `back`：返回队尾元素；
>  *  `push(elem)`：元素进队；
>  *  `pop()`：元素出队；

#### 2.9 priority\_queue ####

>  *  是一种首限访问操作的存储结构；
>  *  元素可以任意顺序进入优先队列；
>  *  出队将是优先级最高的元素；

##### 2.9.1 常见成员函数 #####

>  *  `empty()`：判断是否为空；
>  *  `size()`：元素个数；
>  *  `top`：获取队头元素；
>  *  `push(elem)`：元素进队；
>  *  `pop()`：元素出队；