跳转至

STL(Standard Template Library).STL是最新的C++标准函数库中的一个子集，它占据了整个库的大约80%的分量。 主要包含：容器（Container）、算法（Algorithms）、迭代器（iterators）

一、容器

  • 序列容器： vector 、 string 、 deque 和 list, initializer_list(C++11),forward_list(C++11) 。
  • 关联容器： set 、 multiset 、 map 和 multimap。
  • 适配容器： stack 、 queue 和 priority_queue。
  • 异构容器： tuple

都有的构造函数：默认构造、拷贝构造、初始化列构造、基于迭代器构造。 赋值方法：operator=, assign(<ps>,<pe>)(支持类型隐式转换) 公共方法：empty(),size(), resize(),swap(<b>),clear()，operator==,operator!= 注：可以直接比较两个list是否相等。

不要企图继承一个std容器。（早期版本没用final字段加以区分）

1.1 序列容器

删除后迭代器指向被删元素的下一个位置；insert 返回的迭代器指向新插入的元素。

X(n, t=0): 初始化n个值为t的序列容器 X(ps, pn): 基于ps到pn构造序列容器 a.insert(p,t),a.insert(p,n,t),a.insert(p,i,j) a.erase(p),a.erase(p,q),a.clear()

表达式 返回类型 容器
a.front() T& vector,list,deque,forward_list
a.back() T& vector,list,deque
a.push_back(t) void vector,list,deque
a.pop_back() void vector,list,deque
a.push_front(t) void list,deque ,forward_list
a.pop_front() void list,deque,forward_list
a[n] / a.at(n) T& vector,deque
注：operator[] 不检查越界；at(n) 会检查并在越界时抛 std::out_of_range。
注：C++11新标准引入了三个新成员： emplace 、 emplace_back 、 emplace_front ，分别对应 insert 、 push_back 、 push_front。

标准与实现

emplace_back 与 push_back 的接口/复杂度保证（均摊 O(1)）由标准定；二者的差别在于 emplace 系列直接在容器节点内构造对象（完美转发参数到构造函数），省去临时对象和一次移动/拷贝。vector::push_back 扩容时的增长因子（容量不够时翻几倍）标准未规定具体值，只要求均摊常数：libstdc++ 取 2，MSVC 取 1.5，libc++ 也取 2。因此 capacity() 的具体值跨实现不同。

1.1.1 string

构造的3:2:1原则：<string> [, <start_index> [, <len>]], <cstring> [, <clen>], <char>, <len> 转字符串：c_str(),data() 查找：find(),rfind(),find_first_of(),find_last_of(),find_first_not_of(),find_last_not_of()

  • string::npos
  • find([<char>, <string>, <cstring>], <CallerPos> = 0) 插入：insert(),append() （在前面插入）
  • insert(<pos>, <string2> [, <pos_bgn>, <pos_end>]),insert(<pos>, <n>, <char>)
  • append(<string/cstring>),append(<n>, <char>) 删除：erase(<pos> [, <cnt>])，erase(<iterStart>, <iterEnd>)（删除后返回指向后一个元素）

注：memset(<ptr>, <value>, <len>)和insert不同。STD中基本都是先长度再值。

标准与实现

std::string 是否启用 SSO（Small String Optimization，小字符串优化）、阈值多大，标准未规定，是各实现的取舍（libstdc++ 大致 ≤15 字符、libc++ ≤22、MSVC ≤15）。sizeof(std::string)、内部布局因此跨实现不同——这与 Itanium C++ ABI 及具体标准库实现共同相关，跨编译器/跨标准库版本二进制不兼容（典型如 GCC 5 的 libstdc++ _GLIBCXX_USE_CXX11_ABI 重写）。

1.1.2 list

void merge(list<T>):事先排序，x将为清空 void remove(const T& val)：删除元素 void remove_if(lambda):基于条件删除元素 void sort()：排序 void splice(iterator pos, list<T> x):向前插入，x将为清空 void unique():删除重复 void reverse():反向

forward_list是C++11加入的，仅支持前向操作。相对于list的特有方法有before_begin(),cbefore_begin,insert_after,erase_after,push_front,pop_front。

1.1.3 stack / queue / priority_queue

push(),pop(),top()

适配： std::queue<std::string, std::list<std::string>>words; std::priority_queue<Date, std::vector<Date>, std::less<Date>> q1;

priority_queue操作与queue一致，只不过是按照排序大小输出，如std::less<>先输出大值。

1.1.4 array (C++11)

至于 array 和 C 数组的区别，则在于下面几点：

  • array 不像 C 数组一样会自动退化成元素指针，而是允许值传参（非引用方式）并保留大小
  • array 支持正常的赋值操作
  • array 自动支持同类型的比较操作
  • array 支持容器共有的 begin、end 等成员函数 形式：std::array<type, size>

注：valarray 是面向数值计算的，不属于 STL。

1.2 关联容器

1.2.1 set

基本方法：insert(<obj>),count(<obj>) 常用algo:

  • std::set_union(s1.begin(), s1.end(), s2.begin(), s2.end(), )
  • std::set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(), )
  • std::set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), )

1.2.2 map

基本对象：std::pair<key, val> pr 基本对象成员：first,second 基本方法：count(<key>),insert(<pr>),m[key]=val;

1.2.3 其他

multimap：一个键可能对应多个值 特有方法：auto itPair = m.equal_range(key)

unordered_map, unordered_multimap, unordered_set, unordered_multiset

标准与实现

unordered_* 系列基于哈希。标准只规定接口 std::hash<T> 和复杂度保证（查找/插入/删除平均 O(1)、最坏 O(n)）；具体哈希算法未指定——libstdc++(GCC)、libc++(Clang)、MSVC STL 各自实现不同。因此同一份数据在不同实现上遍历顺序不同，rehash 时机也不同。若依赖顺序需改用 map/set 或自行排序。

迭代器失效规则由标准定：插入若引起 rehash，所有迭代器失效（引用和指针也失效）；删除仅使指向被删元素的迭代器失效。rehash 期间持有引用再插入是真正的未定义行为（Undefined Behavior）。

1.2.4 tuple, pair

tuple和python中的元组类似，是pair的泛化版本。参考：tuple 用法

二、函数对象和配接器

transform(gr8.begin(), gr8.end(), out, sqrt);
transform(gr8.begin(), gr8.end(), m8.begin(), out, mean);

2.1 函数模板

函数模板头文件：functional 函数模板：

  • plus,minus,multiplies,divides,modulus,negate
  • equal_to,not_equal_to,greater,less,greater_equal,less_equal
  • logical_and,logical_or,logical_not

2.2 函数适配器

三、函数对象

Callable object (function object, pointer to function, reference to function, pointer to member function, or pointer to data member) that will be bound to some arguments.

一元函数(unary function)：一个参数 二元函数（binary function）：两个参数

函数对象也称为函数符（functor）

谓词（predicate）:返回值为bool的一元函数 二元谓词（predicate）:返回值为bool的二元函数

3.1 仿函数

如果你针对某个class进行operator()重载，它就成为一个仿函数。

3.2 Lambda(闭包)

由于lambda表达式的使用能大幅提升代码的可读性和撰写效率，同时lambda表达式和std::function又有很多关联，所以，写到本章中。 一个lambda表达式不过是生成一个类并且创建一个该类的对象的手法罢了、并不存在lambda能做，而你手工做不了的事情。 默认情况下，lambda生成的闭包类中operator()成员函数会带有const饰词。即，对于一个值被拷贝的变量，lambda不会改变其值，如果我们希望能改变一个被捕获变量的值，就必须在参数列表尾加上关键字mutable。

在 C++11 中，lambda 表达式的捕获列表只能以按值捕获（[=]）或按引用捕获（[&]）的形式出现。

C++14 泛型 lambda 式（generic lambda），除了形参和返回支持auto外，还引入了广义 lambda 捕获，允许你在同一个捕获列表中混合使用按值捕获和按引用捕获，并可以明确指定每个变量的捕获方式。

  • 0：（完整形式）[capture list] (params list) mutable exception-> return type { function body }
  • 1：[capture list] (params list) -> return type {function body}
  • 2：（常用于回调）[capture list] (params list) {function body}
  • 3： [capture list] {function body}

最常用的回调函数（handler）示例 sort(lbvec.begin(), lbvec.end(), [](int a, int b) -> bool { return a < b; }); // Lambda表达式

捕获形式 说明
[] 不捕获任何外部变量
[变量名, …] 默认以值的形式捕获指定的多个外部变量（用逗号分隔），如需引用则加 & 前缀
[this] 以值的形式捕获this指针
[=] 以值的形式捕获所有外部变量。不推荐使用。捕获只能针对在创建 lambda 式的作用域内可见的非静态局部变量（包括形参）。原因 1：在类中的 lambda 表达式会自动捕获 this 指针，进而可以使用类对象中的成员，但按值捕获指针也会出现指针悬空。原因 2：捕获程序块中静态变量存在多线程的问题，lambda 表达式并不独立。而 extern 对象或翻译单元下 static 的对象并不是通过捕获得到的，容易引起歧义。
[&] 以引用形式捕获所有外部变量，不推荐使用。比起 [&] 这种不痛不痒的"要保证没有空悬"式的告诫，显式指名更让人印象深刻。
[=, &x] 变量x以引用形式捕获，其余变量以传值形式捕获
[&, x] 变量x以值的形式捕获，其余变量以引用形式捕获
[nx = x] 初始化捕获，按值捕获变量x或this->x（避免了this指针悬挂问题），在lambda表达式中以nx使用。 从长远观点来看，显示地列出lambda式所依赖的局部变量或形参是更好的软件工程实践。 支持移动捕获[data = std::move(data)],[pw = std::make_unique()]

如果lambda表达在创建后不会在当前作用域中直接运行，而是被作为函数对象传递出去，则不要使用C++11的两种默认捕获形式。（M条款31） C++11不支持移动捕获，但可以通过以下方式模拟：auto func = std::bind( [](const std::unique_ptr<Widget>& pw){ return pw->isValidated();} , std::make_unique<Widget>())

常用应用：std::for_each(it1, it2, lambdaExp)让for中的代码尽量小 脑子短路：lambda函数中的返回形式与普通函数一致，不会因为是lambda函数而直接退出定义它的普通函数。

C++14 lambda表达式中的完美转发：(M条款33)

auto f = [](auto&&... params) {return func(normalize(std::forward<decltype(params)>(params)...))}

四、函数对象的使用

五、资源管理

5.1 资源管理

以对象管理资源：（条款13）

  • 获取资源后立即放进管理对象内。RAII(Resource Acquisition Is Initialization)
  • 管理对象运用析构函数确保资源被析构。

5.2 智能指针(C++11)

共性：自动释放内存，指向的对象必须建立在堆上。

  • auto_ptr: 左右值时都可以进行所有权转换，不支持new[]。使用风险较高
  • unique_ptr:只支持临时右值或右值引用下的所有权转换，支持new[]。可在STL容器中使用，但不能调用存在赋值、复制的方法。在 unique_ptr 为右值时，允许赋值给 shared_ptr 。
  • shared_ptr:引用计数。对应delete（单对象版本）
  • boost::scoped_array:对应delete[]
unique_ptr<string> demo(const char * s){
    unique_ptr<string> temp(new string(s));
    return temp;
}

unique_ptr<string> ps1, ps2;
ps1 = demo("Uniquely special");
//ps2 = ps1; // build error
ps2 = std::move(ps1);
ps1 = unique_ptr<string>(new string("Yo!"));

unique_ptr<double[]> pda(new double[5]);
shared_ptr<string> sptr1 = demo("get unique");

5.3 适配器

生成器（generator）：不用参数就可以调用的函数符

C++98函数适配器：binder1st(f2, val) f1;，bind1st(f2, val)

C++11函数适配器：template< class F, class... Args > bind( F&& f, Args&&... args );

int add(int a, int b) {  return a + b;}  
// 使用 std::bind 将 add 函数的第一个参数绑定为 5，第二个参数使用占位符 _1  
auto bound_add = std::bind(add, 5, std::placeholders::_1);  
bound_add(2);//7

class A {public: int del(int a, int b) {return a-b;}};
//成员函数可以绑定对象
A a;
auto bound_del = std::bind(&A::del, &a, 5, std::placeholders::_1);
bound_del(3);//2

5.4 成员函数指针的使用

MyClass obj;  
    auto memberFunctionPtr = &MyClass::myMemberFunction;  
    //1. in C++11
    // 使用 std::mem_fn 将成员函数指针转换为可调用对象  
    auto callable = std::mem_fn(memberFunctionPtr);  
    // 调用可调用对象，需要传入对象实例和成员函数的参数  
    callable(&obj, 10);
    //2. in C++14
    (obj.*memberFunctionPtr)(10);

5.5 使用lambda表达式代替std::bind (M条款34)

C++14 总是优先使用lambda，没有什么场景是需要使用std::bind的。

C++11 仅在两种lambda受限的场景使用std::bind:

  • 移动捕获
  • ~~多态函数对象~~ 使用了模版参数的函数对象（因为C++11还没有auto与template对应。）

lambda明显优于std::bind的场景

  • 若输入参数使一个表达式，则表达式会直接运算，而不是在函数对象调用时计算。（M P221 中的例子）
  • 为了绕开表达式的问题，就不得不写std::bind的嵌套程序，再加上占位符，整个程序很不直观。

六、shared

使用 std::make_shared 可使内存分配从两步变为一步，具有更强的异常安全性。参考：make_shared

cpp_6-标准模板库_260718_010446.png

七、迭代器

头文件：#include <iterator>

输入迭代器：ifstream::iterator.输入迭代器：只能取指向的值，当迭代器自加后，之前指向的值就不可访问（不用此类迭代器在一个范围内遍历多次），典型的如std::istream_iterator。 输出迭代器：ostream_iterator，例：std::ostream_iterator<std::string, char> out(std::cout, " ");。输出迭代器：单纯用于写的迭代器，只能前进，且将内容写入对应容器（文件）中；读取的值是未定义的。

输入迭代器：*，->,=,==,!= 前向迭代器：支持++。只继承自输入迭代器。demo 双向迭代器：额外支持-- 随机访问迭代器：额外支持：+，-，+=，-=，[]，<，<=，>，>= cpp_6-标准模板库_260718_010540.png

在 C++ 中，迭代器的 "multiple passes"（多趟）指同一个迭代器范围可以被保存下来并多次遍历，而无需每次重新获取——前向迭代器及以上支持，输入/输出迭代器不支持。这跟"迭代器失效"是两个概念。

标准与实现

迭代器失效规则是标准明确规定的（不是未定义），各类容器在插入/删除后的失效范围：

  • vector / string：插入若引发重分配，所有迭代器失效；否则插入点之后失效；删除使被删元素及其后的失效。
  • deque：插入/删除都会让所有迭代器失效（向两端插删则只让迭代器失效、引用和指针仍有效）。
  • list / forward_list：插入不影响其他迭代器；删除仅使指向被删元素的迭代器失效。
  • map / set / multimap / multiset：插入不会使任何迭代器失效；删除仅使指向被删元素的迭代器失效。
  • unordered_*：插入若引发 rehash，所有迭代器失效（引用和指针也失效）；不 rehash 则无影响；删除仅使指向被删元素的失效。

因此原话反过来才对：节点式的 list/map/set 迭代器对插入最稳定，vector 在重分配时全部失效。用失效迭代器访问属于真正的未定义行为。

标准容器的迭代器： begin(),end(),cbegin(),cend()， before_begin()

插入容器：std::insert_iterator<std::set<int>> (s, s.begin())

八、算法

客户可以全特例化std内的templates，但不可用添加新的templates(或classes或functions或其他任何东西)到std里头。

数据结构相关的算法为：增删查改

8.1 查

std::find_if 至少是输入迭代器。

8.2 改

8.2.1 swap

考虑写出一个不抛出异常的swap函数（条款25）。成员版本swap绝不可抛出异常。 所有STL容器都提供有public swap成员函数和std::swap特例化版本。 在效率不足时，要提供member swaps、non-member swaps、std::swap特例化版本。

8.2.2 排序

for_each(c.begin(), c.end(), funcPtr):要求迭代器是前向的 sort(c.begin(), c.end() [operation]): 要求迭代器可随机访问;默认升序，即默认调用less<>；降序调用greater<>

标准与实现

std::sort 的复杂度保证（O(n log n)）由标准定；具体排序算法（introsort 等）未指定，只要满足复杂度即可。std::sort 不保证相等元素的相对顺序（即不是稳定排序）——需要稳定用 std::stable_sort（同样是 O(n log n)，但有更多内存开销保证）。

九、配置器/内存分配子

operator new 参考：new 与 operator new placement new 参考：placement new

十、异常

std::abort()可以抢先制“不明确行为”于死地。避免错误传播出去。 析构函数吐出异常是危险的，总会带来“过早结束程序”或发生不明确行为的风险。因此一般会额外使用close()函数。

异常安全性