全网最全面的STL总结与常见面试题，值得收藏（一）-阿里云开发者社区

1 STL概述

为了建立数据结构和算法的一套标准，并且降低他们之间的耦合关系，以提升各自的独立性、弹性、交互操作性(相互合作性,interoperability),诞生了STL。

程序员必备资源，值得收藏！点击下载

STL提供了六大组件，彼此之间可以组合套用，这六大组件分别是:容器、算法、迭代器、仿函数、适配器（配接器）、空间配置器。

容器：各种数据结构，如vector、list、deque、set、map等,用来存放数据，从实现角度来看，STL容器是一种class template。

算法：各种常用的算法，如sort、find、copy、for_each。从实现的角度来看，STL算法是一种function tempalte.

迭代器：扮演了容器与算法之间的胶合剂，共有五种类型，从实现角度来看，迭代器是一种将operator* , operator-> , operator++,operator–等指针相关操作予以重载的class template. 所有STL容器都附带有自己专属的迭代器，只有容器的设计者才知道如何遍历自己的元素。原生指针(native pointer)也是一种迭代器。

仿函数：行为类似函数，可作为算法的某种策略。从实现角度来看，仿函数是一种重载了operator()的class 或者class template

适配器：一种用来修饰容器或者仿函数或迭代器接口的东西。

空间配置器：负责空间的配置与管理。从实现角度看，配置器是一个实现了动态空间配置、空间管理、空间释放的class tempalte.

STL六大组件的交互关系，容器通过空间配置器取得数据存储空间，算法通过迭代器存储容器中的内容，仿函数可以协助算法完成不同的策略的变化，适配器可以修饰仿函数。

2 STL的优点：

STL 是 C++的一部分，因此不用额外安装什么，它被内建在你的编译器之内。

STL 的一个重要特性是将数据和操作分离。数据由容器类别加以管理，操作则由可定制的算法定义。迭代器在两者之间充当“粘合剂”,以使算法可以和容器交互运作

程序员可以不用思考 STL 具体的实现过程，只要能够熟练使用 STL 就 OK 了。这样他们就可以把精力放在程序开发的别的方面。

STL 具有高可重用性，高性能，高移植性，跨平台的优点。

高可重用性：STL 中几乎所有的代码都采用了模板类和模版函数的方式实现，这相比于传统的由函数和类组成的库来说提供了更好的代码重用机会。

高性能：如 map 可以高效地从十万条记录里面查找出指定的记录，因为 map 是采用红黑树的变体实现的。

高移植性：如在项目 A 上用 STL 编写的模块，可以直接移植到项目 B 上。容器和算法之间通过迭代器进行无缝连接。STL 几乎所有的代码都采用了模板类或者模板函数，这相比传统的由函数和类组成的库来说提供了更好的代码重用机会。

3 容器

STL容器就是将运用最广泛的一些数据结构实现出来。

常用的数据结构：数组(array) , 链表(list), tree(树)，栈(stack), 队列(queue), 集合(set),映射表(map), 根据数据在容器中的排列特性，这些数据分为序列式容器和关联式容器两种。

序列式容器强调值的排序，序列式容器中的每个元素均有固定的位置，除非用删除或插入的操作改变这个位置。Vector容器、Deque容器、List容器等。

关联式容器是非线性的树结构，更准确的说是二叉树结构。各元素之间没有严格的物理上的顺序关系，也就是说元素在容器中并没有保存元素置入容器时的逻辑顺序。关联式容器另一个显著特点是：在值中选择一个值作为关键字key，这个关键字对值起到索引的作用，方便查找。Set/multiset容器 Map/multimap容器

容器底层数据结构时间复杂度有无序可不可重复

array 数组随机读改 O(1) 无序可重复

vector 数组随机读改、尾部插入、尾部删除 O(1)头部插入、头部删除 O(n) 无序可重复

deque 双端队列头尾插入、头尾删除 O(1) 无序可重复

forward_list 单向链表插入、删除 O(1) 无序可重复

list 双向链表插入、删除 O(1) 无序可重复

stack deque / list 顶部插入、顶部删除 O(1) 无序可重复

queue deque / list 尾部插入、头部删除 O(1) 无序可重复

priority_queue vector /max-heap 插入、删除 O(log2n) 有序可重复

set 红黑树插入、删除、查找 O(log2n) 有序不可重复

multiset 红黑树插入、删除、查找 O(log2n) 有序可重复

map 红黑树插入、删除、查找 O(log2n) 有序不可重复

multimap 红黑树插入、删除、查找 O(log2n) 有序可重复

unordered_set 哈希表插入、删除、查找 O(1) 最差 O(n) 无序不可重复

unordered_multiset 哈希表插入、删除、查找 O(1) 最差 O(n) 无序可重复

unordered_map 哈希表插入、删除、查找 O(1) 最差 O(n) 无序不可重复

unordered_multimap 哈希表插入、删除、查找 O(1) 最差 O(n) 无序可重复

1 array

array 是固定大小的顺序容器，它们保存了一个以严格的线性顺序排列的特定数量的元素。

方法说明

begin 返回指向数组容器中第一个元素的迭代器

end 返回指向数组容器中最后一个元素之后的理论元素的迭代器

rbegin 返回指向数组容器中最后一个元素的反向迭代器

rend 返回一个反向迭代器，指向数组中第一个元素之前的理论元素

cbegin 返回指向数组容器中第一个元素的常量迭代器（const_iterator）

cend 返回指向数组容器中最后一个元素之后的理论元素的常量迭代器（const_iterator）

crbegin 返回指向数组容器中最后一个元素的常量反向迭代器（const_reverse_iterator）

crend 返回指向数组中第一个元素之前的理论元素的常量反向迭代器（const_reverse_iterator）

size 返回数组容器中元素的数量

max_size 返回数组容器可容纳的最大元素数

empty 返回一个布尔值，指示数组容器是否为空

operator[] 返回容器中第 n（参数）个位置的元素的引用

at 返回容器中第 n（参数）个位置的元素的引用

front 返回对容器中第一个元素的引用

back 返回对容器中最后一个元素的引用

data 返回指向容器中第一个元素的指针

fill 用 val（参数）填充数组所有元素

swap 通过 x（参数）的内容交换数组的内容

get（array）形如 std::get<0>(myarray)；传入一个数组容器，返回指定位置元素的引用

relational operators (array) 形如 arrayA > arrayB；依此比较数组每个元素的大小关系

测试代码

#include<iostream>
#include<array>
using namespace std;
int main() 
{
  array<int, 8> myArr = {1,3,4,6,9};//固定大小为8
  cout << "myArr元素序列：";
  for (auto i = 0; i < 8; ++i) 
  {
    cout << myArr[i] << " ";
  }
  cout << endl;
  array<int, 8> myArr1 = {2,3,4,7,8,9};//固定大小为8
  cout << "myArr1元素序列：";
  for (auto i = 0; i < 8; ++i) 
  {
    cout << myArr1[i] << " ";
  }
  cout << endl;
  myArr.swap(myArr1);   //交换两个容器的内容
  cout << "交换myArr与myArr1"<< endl;
  cout << endl;
  cout << "myArr.at(3) = " << myArr.at(3) << endl;//任意访问
  cout << "myArr[3] = " << myArr[3] << endl;//任意访问
  cout << "myArr.front() = " << myArr.front() << endl;//获取第一个元素
  cout << "myArr.back() =  " << myArr.back() << endl;//获取最后一个元素
  cout << "myArr.data() = " << myArr.data() << endl;//获取第一个元素的指针
  cout << "*myArr.data() = " << *myArr.data() << endl;//获取第一个元素的指针指向的元素
  cout << "正向迭代器遍历容器：";
  for (auto it = myArr.begin(); it != myArr.end(); ++it) 
  {
    cout << *it << " ";
  }
  cout << endl;
  //逆向迭代器测试
  cout << "逆向迭代器遍历容器：";
  for (auto rit = myArr.rbegin(); rit != myArr.rend(); ++rit) 
  {
    cout << *rit << " ";
  }
  cout << endl;
  //正向常迭代器测试
  cout << "正向常迭代器遍历容器：";
  for (auto it = myArr.cbegin(); it != myArr.cend(); ++it) 
  {
    cout << *it << " ";
  }
  cout << endl;
  //逆向常迭代器测试
  cout << "逆向常迭代器遍历容器：";
  for (auto rit = myArr.crbegin(); rit != myArr.crend(); ++rit) 
  {
    cout << *rit << " ";
  }
  cout << endl;
  if(myArr.empty())
    cout << "myArr为空 " << endl;
  else
    cout << "myArr不为空 " << endl;
  cout << "myArr.size() = " << myArr.size() << endl;
  cout << "myArr.max_size() = " << myArr.max_size() << endl;
  return 0;
}

运行结果

vector

vector 是表示可以改变大小的数组的序列容器。

方法说明

vector 构造函数

~vector 析构函数，销毁容器对象

operator= 将新内容分配给容器，替换其当前内容，并相应地修改其大小

begin 返回指向容器中第一个元素的迭代器

end 返回指向容器中最后一个元素之后的理论元素的迭代器

rbegin 返回指向容器中最后一个元素的反向迭代器

rend 返回一个反向迭代器，指向中第一个元素之前的理论元素

cbegin 返回指向容器中第一个元素的常量迭代器（const_iterator）

cend 返回指向容器中最后一个元素之后的理论元素的常量迭代器（const_iterator）

crbegin 返回指向容器中最后一个元素的常量反向迭代器（const_reverse_iterator）

crend 返回指向容器中第一个元素之前的理论元素的常量反向迭代器（const_reverse_iterator）

size 返回容器中元素的数量

max_size 返回容器可容纳的最大元素数

resize 调整容器的大小，使其包含 n（参数）个元素

capacity 返回当前为 vector 分配的存储空间（容量）的大小

empty 返回 vector 是否为空

reserve 请求 vector 容量至少足以包含 n（参数）个元素

shrink_to_fit 要求容器减小其 capacity（容量）以适应其 size（元素数量）

operator[] 返回容器中第 n（参数）个位置的元素的引用

at 返回容器中第 n（参数）个位置的元素的引用

front 返回对容器中第一个元素的引用

back 返回对容器中最后一个元素的引用

data 返回指向容器中第一个元素的指针

assign 将新内容分配给 vector，替换其当前内容，并相应地修改其 size

push_back 在容器的最后一个元素之后添加一个新元素

pop_back 删除容器中的最后一个元素，有效地将容器 size 减少一个

insert 通过在指定位置的元素之前插入新元素来扩展该容器，通过插入元素的数量有效地增加容器大小

erase 从 vector 中删除单个元素（position）或一系列元素（[first，last)），这有效地减少了被去除的元素的数量，从而破坏了容器的大小

swap 通过 x（参数）的内容交换容器的内容，x 是另一个类型相同、size 可能不同的 vector 对象

clear 从 vector 中删除所有的元素（被销毁），留下 size 为 0 的容器

emplace 通过在 position（参数）位置处插入新元素 args（参数）来扩展容器

emplace_back 在 vector 的末尾插入一个新的元素，紧跟在当前的最后一个元素之后

get_allocator 返回与vector关联的构造器对象的副本

swap(vector) 容器 x（参数）的内容与容器 y（参数）的内容交换。两个容器对象都必须是相同的类型（相同的模板参数），尽管大小可能不同

relational operators (vector) 形如 vectorA > vectorB；依此比较每个元素的大小关系

测试代码

#include <vector>
#include <iostream>
using namespace std;
int main()
{
  //构造函数,复制构造函数(元素类型要一致),
  vector<int> vecA;  //创建一个空的的容器
  vector<int> vecB(10,20); //创建一个10个元素,每个元素值为20
  vector<int> vecC(vecB.begin(),vecB.end()); //使用迭代器,可以取部分元素创建一个新的容器
  vector<int> vecD(vecC); //复制构造函数,创建一个完全一样的容器
  //重载=
  vector<int> vecE;
  vecE = vecB;
  //vector::begin()，返回的是迭代器
  vector<int> vecF(10); //创建一个有10个元素的容器
  cout << "vecF:";
  for (int i = 0; i < 10; i++)
  {
    vecF[i] = i;
    cout << vecF[i]<< " ";
  }
  cout << endl;
  //vector::begin() 返回迭代器
  vector<int>::iterator Beginit = vecF.begin();
  cout<< "vecF.begin():" << *Beginit << endl; 
  //vector::end() 返回迭代器
  vector<int>::iterator EndIter = vecF.end();
  EndIter--; //向后移一个位置
  cout <<"vecF.end():"<< *EndIter << endl; 
  //vector::rbegin() 返回倒序的第一个元素，相当于最后一个元素
  vector<int>::reverse_iterator ReverBeIter = vecF.rbegin();
  cout << "vecF.rbegin(): "<< *ReverBeIter << endl; 
  //vector::rend() 反序的最后一个元素下一个位置，也相当于正序的第一个元素前一个位置
  vector<int>::reverse_iterator ReverEnIter = vecF.rend();
  ReverEnIter--;
  cout << "vecF.rend():"<< *ReverEnIter << endl; 
  //vector::size() 返回元素的个数
  cout << "vecF.size():"<< vecF.size() << endl; 
  //vector::max_size()
  cout << "vecF.max_size():"<< vecF.max_size() << endl; 
  //vector::resize()
  cout<< "vecF.size():" << vecF.size() << endl; 
  vecF.resize(5);
  cout<< "调整vecF大小后重新赋值:"; 
  for(int k = 0; k < vecF.size(); k++)
    cout << vecF[k] << "  "; 
  cout << endl;
  //vector::capacity()
  cout<< "调整后vecF.size():"<< vecF.size() << endl; 
  cout<< "调整后vecF.capacity():" << vecF.capacity() << endl; 
  //vector::empty()
  vecB.resize(0);
  cout<< "vecB.resize(0)后"<< endl; 
  cout  << "vecB.size():" << vecB.size() << endl; 
  cout  << "vecB.capacity():" << vecB.capacity() << endl; 
  if(vecB.empty())
      cout << "vecB为空"<< endl; 
  else
    cout << "vecB不为空"<< endl; 
  //vector::reserve() //重新分配存储空间大小
  cout<< "vecC.capacity():" << vecC.capacity() << endl; //
  vecC.reserve(4);
  cout << "vecC.reserve(4)后vecC.capacity()： "<< vecC.capacity() << endl; //10
  vecC.reserve(14);
  cout << "vecC.reserve(14)后vecC.capacity()： "<< vecC.capacity() << endl; //14
  //vector::operator []
  cout << "vecF[0]:"<< vecF[0] << endl; //第一个元素是0
  //vector::at()
  try
  {
    cout << "vecF.size = " << vecF.size() << endl; //5
    cout << vecF.at(6) << endl; //抛出异常
  }
  catch(out_of_range)
  { 
    cout << "at()访问越界" << endl;
  }
  //vector::front() 返回第一个元素的值
  cout << "vecF.front():"<< vecF.front() << endl; //0
  //vector::back()
  cout << "vecF.back():"<< vecF.back() << endl; //4
  //vector::assign()
  cout <<"vecA.size():"<< vecA.size() << endl; //0
  vector<int>::iterator First = vecC.begin();
  vector<int>::iterator End = vecC.end()-2;
  vecA.assign(First,End);
  cout << vecA.size() << endl; //8
  cout << vecA.capacity() << endl; //8
  vecA.assign(5,3); //将丢弃原来的所有元素然后重新赋值
  cout << vecA.size() << endl; //5
  cout << vecA.capacity() << endl; //8
  //vector::push_back()
  cout << *(vecF.end()-1) << endl; //4
  vecF.push_back(20);
  cout << *(vecF.end()-1) << endl; //20
  //vector::pop_back()
  cout << *(vecF.end()-1) << endl; //20
  vecF.pop_back();
  cout << *(vecF.end()-1) << endl; //4
  //vector::swap()
  cout << "vecF:";
  for (int i = 0; i < vecF.size(); i++)
  {
    vecF[i] = i;
    cout << vecF[i]<< " ";
  }
  cout << endl;
  cout << "vecD:";
  for (int d = 0; d < vecD.size(); d++)
  {
    vecD[d] = d;
    cout << vecD[d]<< " ";
  }
  cout << endl;
  vecF.swap(vecD); //交换这两个容器的内容
  cout <<"vecD与vecF交换后：" <<endl;
  cout << "vecF:";
  for(int f = 0; f < vecF.size(); f++)
    cout << vecF[f] << " ";
  cout << endl;
  cout << "vecD:";
  for (int d = 0; d <vecD.size(); d++)
    cout << vecD[d] << " ";
  cout << endl;
  //vector::clear()
  vecF.clear();
  cout << "vecF.clear()后vecF.size()："<< vecF.size() << endl;     //0
  cout << "vecF.clear()后vecF.capacity()："<< vecF.capacity() << endl; //10
  return 0;
}

全网最全面的STL总结与常见面试题，值得收藏（一）

热门文章

最新文章

相关课程

相关电子书