C++ Standard Template Library

1 容器

std::array

#include <array>
std::array<int, 10> arr = {0};

大小固定的数组，支持快速随机访问，不能添加和删除元素。

std::vector

#include <vector>

动态数组(Dynamic Arrays)，支持快速随机访问，在尾部之外的位置插入或删除元素可能很慢。

当需要增加数据时，重新分配一块内存，将原来的数据拷贝过来并加上需要添加的数据，然后删除原来的数据。

问题：拷贝很耗时。

优化方案一：提前预留空间，减少分配内存拷贝数据次数。

优化方案二：使用emplace_back而不是push_back。

std::vector<int> vec;
vec.emplace_back(0);
vec.at(0); // Valid
vec.at(1); // Invalid, terminate called after throwing an instance of 'std::out_of_range'

std::string

#include <string>

与 std::vector 相似，专门用于保存字符，随机访问快，在尾部插入或删除速度快。

std::deque

#include <deque>

双端队列，支持快速随机访问，在头尾位置插入或删除速度很快。

std::list

#include <list>

双向链表，只支持双向顺序访问，速度较慢，在任何位置插入或删除速度都很快。

前面在讲 STL list 容器时提到，该容器的底层是用双向链表实现的，甚至一些 STL 版本中（比如 SGI STL），list 容器的底层实现使用的是双向循环链表。

std::unordered_map

#include <unordered_map>

底层实现为哈希表，元素无序，查找时间复杂度为 $O(1)$

std::map

#include <map>

底层实现为红黑树，元素有序，查找时间复杂度为 $O(log_{2}{n})$

1. 容器中的元素是键值对 (key, value)，关键字 (key) 起到索引的作用，值 (value) 则表示与索引相关联的数据；
2. 迭代器不是 const 的，允许修改元素的 value，但不允许修改 key；
3. 支持下标操作。

插入重复元素时，如果用insert，则插入失败，如果用操作符，则覆盖已有元素。

// 插入值的三种方式
map[key] = value;
map.insert(pair<key_type, value_type>(key, value));
map.insert(map<key_type, value_type>::value_type (key, value));

获取不存在的元素时，如果用at，会抛出std::out_of_range错误，如果用操作符，会创建对应的元素。正常情况下，建议用at获取元素。

// 读取数据
if (map.find(key) != map.end()) {
    value = map.at(key);
}

std::set

#include <set>

底层实现为红黑树，元素有序，查找时间复杂度为 $O(log_{2}{n})$

1. 容器中的元素为关键字 key 的简单集合，每个元素只包含一个关键字；
2. 迭代器是 const 的，不允许修改元素的值；
3. 不支持下标操作。

std::map 和 std::set 是根据关键字排序来保证其有序性的，如果允许修改 key 的话，那么首先需要删除该键，然后调节平衡，再插入修改后的键值，调节平衡，如此一来，严重破坏了容器的结构，导致 iterator 失效，不知道应该指向改变前的位置，还是指向改变后的位置。所以 STL 中将 set 的迭代器设置成 const，不允许修改迭代器的值；而 map 的迭代器则不允许修改 key 值，允许修改 value 值。

std::pair

#include <utility>

std::make_pair

2 智能指针

#include <memory>

std::auto_ptr

Since C++98, deprecated in C++11, removed in C++17.

std::unique_ptr

由 C++11 引入，旨在替代不安全的 std::auto_ptr。

unique_ptr不共享它的指针，它无法复制到其他unique_ptr，无法通过值传递到函数，也无法用于需要副本的任何标准模板库 (STL) 算法，只能移动unique_ptr。这意味着，内存资源所有权将转移到另一unique_ptr，并且原始unique_ptr不再拥有此资源。

unique_ptr实现了独享所有权的语义，一个非空的unique_ptr总是拥有它所指向的资源。转移一个unique_ptr将会把所有权也从源指针转移给目标指针（源指针被置空）。拷贝一个unique_ptr将不被允许，因为如果你拷贝一个unique_ptr，那么拷贝结束后，这两个unique_ptr都会指向相同的资源，它们都认为自己拥有这块资源，所以都会企图释放。因此unique_ptr是一个仅能移动 (move_only) 的类型。当指针析构时，它所拥有的资源也被销毁。默认情况下，资源的析构是伴随着调用unique_ptr内部的原始指针的delete操作。

Function	Description
operator bool	Return true if the stored pointer is not null.
operator=	Move assignment operator.
operator*	Dereference the stored pointer.
operator->	Return the stored pointer.
get	Return the stored pointer.
reset	The deleter will be invoked if a pointer is already owned.
release	Release ownership of any stored pointer.
swap	Exchange the pointer and deleter with another object.
get_deleter	Return a reference to the stored deleter.

使用场景：

1. 为动态申请的资源提供异常安全保证，动态申请内存后，保证在抛出异常或提前退出时释放资源

   void Func()
   {
      int *p = new int(5);
   
      // ...（可能会抛出异常）return
   
      delete p;
   }
   // 替换为下面的写法
   void Func()
   {
      unique_ptr<int> p(new int(5));
   
      // ...（可能会抛出异常）
   }

2. 返回函数内动态申请资源的所有权

   unique_ptr<int> Func(int p)
   {
       unique_ptr<int> pInt(new int(p));
       return pInt; // 返回 unique_ptr
   }
   
   int main()
   {
       int p = 5;
       unique_ptr<int> ret = Func(p);
       cout << *ret << endl;
      // 函数结束后，自动释放资源
   }

3. 在容器中保存指针

   int main()
   {
       vector<unique_ptr<int>> vec;
       unique_ptr<int> p(new int(5));
       vec.push_back(std::move(p)); // 使用移动语义
   }

4. 管理动态数组

   int main()
   {
       unique_ptr<int[]> p(new int[5] {1, 2, 3, 4, 5});
       p[0] = 0; // 重载了 operator[]
   }

5. 作为 auto_ptr 的替代品

   #include <iostream>
   #include <memory>
   #include <stdlib.h>
   struct Foo
   {
       Foo() { std::cout << "Foo::Foo\n"; }
       ~Foo() { std::cout << "Foo::~Foo\n"; }
       void bar() { std::cout << "Foo::bar\n"; }
   };
   void f(const Foo &)
   {
       std::cout << "f(const Foo&)\n";
   }
   struct D
   {
       void operator()(Foo* foo)
       {
           std::cout << "D operator()" << std::endl;
           delete foo;
       }
   };
   void TestAutoDestroy()
   {
       //1. 普通的 new 对象。
       std::cout << "TestDestroy...................." << std::endl;
       {
           std::unique_ptr<Foo> p1(new Foo);
       }
       //2. 普通的 new[] 对象。
       {
           std::unique_ptr<Foo[]> p2(new Foo[4]);
       }
       //3. 自定义的 deleter.
       {
           std::unique_ptr<Foo, D> p3(new Foo);
       }
   }
   void TestOwner()
   {
       std::cout << "TestOwner...................." << std::endl;
       //1. new object.
       std::unique_ptr<Foo> p1(new Foo);  // p1 owns Foo
       if (p1) p1->bar();
       {
           std::unique_ptr<Foo> p2(std::move(p1));  // now p2 owns Foo
           f(*p2);
           p1 = std::move(p2);  // ownership returns to p1
           p2->bar();
           std::cout << "destroying p2...\n";
       }
       p1->bar();
   }
   void TestArrayOwner()
   {
       std::cout << "TestArrayOwner...................." << std::endl;
       //1. new[] object.
       std::unique_ptr<Foo[]> p1(new Foo[4]);  // p1 owns Foo
       if (p1) p1[0].bar();
       {
           std::unique_ptr<Foo[]> p2(std::move(p1));  // now p2 owns Foo
           f(p2[0]);
           p1 = std::move(p2);  // ownership returns to p1
           p2[0].bar();
           std::cout << "destroying p2...\n";
       }
       p1[0].bar();
   }
   int main()
   {
       TestAutoDestroy();
       TestOwner();
       TestArrayOwner();
   }

   输出：

   TestDestroy....................
   Foo::Foo
   Foo::~Foo
   Foo::Foo
   Foo::Foo
   Foo::Foo
   Foo::Foo
   Foo::~Foo
   Foo::~Foo
   Foo::~Foo
   Foo::~Foo
   Foo::Foo
   D operator()
   Foo::~Foo
   TestOwner....................
   Foo::Foo
   Foo::bar
   f(const Foo&)
   Foo::bar
   destroying p2...
   Foo::bar
   Foo::~Foo
   TestArrayOwner....................
   Foo::Foo
   Foo::Foo
   Foo::Foo
   Foo::Foo
   Foo::bar
   f(const Foo&)
   Foo::bar
   destroying p2...
   Foo::bar
   Foo::~Foo
   Foo::~Foo
   Foo::~Foo
   Foo::~Foo

• C++ 11 创建和使用 unique_ptr

std::shared_ptr

空的shared_ptr指针，其初始引用计数为 0，而不是 1。

std::shared_ptr<int> p3(new int(10));
std::shared_ptr<int> p3 = std::make_shared<int>(10);
std::shared_ptr<int> p4(p3);             // Copy Constructor
std::shared_ptr<int> p4 = p3;            // Copy Assignment operator
std::shared_ptr<int> p5(std::move(p4));  // Move Constructor
std::shared_ptr<int> p5 = std::move(p4); // Move Assignment operator

如上所示，p3 和 p4 都是 shared_ptr 类型的智能指针，因此可以用 p3 来初始化 p4，由于 p3 是左值，因此会调用拷贝构造函数。需要注意的是，如果 p3 为空智能指针，则 p4 也为空智能指针，其引用计数初始值为 0；反之，则表明 p4 和 p3 指向同一块堆内存，同时该堆空间的引用计数会加 1。

而对于std::move(p4)来说，该函数会强制将 p4 转换成对应的右值，因此初始化 p5 调用的是移动构造函数。另外和调用拷贝构造函数不同，用std::move(p4)初始化 p5，会使得 p5 拥有了 p4 的堆内存，而 p4 则变成了空智能指针。

同一普通指针不能同时为多个shared_ptr对象赋值，否则会导致程序发生异常。

std::shared_ptr<int> p6(new int[10], std::default_delete<int[]>()); // 指定 default_delete 作为释放规则
void deleteInt(int*p) { // 自定义释放规则
    delete []p;
}
std::shared_ptr<int> p7(new int[10], deleteInt); // 初始化智能指针，并自定义释放规则
std::shared_ptr<int> p7(new int[10], [](int* p) {delete[]p; });

Function	Description
operator bool	Return true if the stored pointer is not null.
operator=	Move assignment operator.
operator*	Dereference the stored pointer.
operator->	Return the stored pointer.
get	Return the stored pointer.
swap	交换 2 个相同类型 shared_ptr 智能指针的内容。
reset	形参为空，当前对象重置为空指针；当传入新申请的堆内存时，则获得该存储空间的所有权，引用计数的重置为 1。
use_count	返回引用计数。
unique	判断指向堆内存的 shared_ptr 对象是否唯一。

#include <iostream>
#include <memory>

using namespace std;

int main()
{
    std::shared_ptr<int> p1(new int(10));
    std::shared_ptr<int> p2(p1);
    std::shared_ptr<int> p3(p1);

    // p1、p2、p3 指向同一块堆内存，引用基数均为 3
    std::cout << p1.get() << " " << p2.get() << " " << p3.get() << std::endl;
    std::cout << p1.use_count() << " " << p2.use_count() << " " << p3.use_count() << std::endl;

    p1.reset(); // p1 重置为空指针，p2、p3 指向同一块堆内存，p2、p3 引用计数减 1
    std::cout << p1.get() << " " << p2.get() << " " << p3.get() << std::endl;
    std::cout << p1.use_count() << " " << p2.use_count() << " " << p3.use_count() << std::endl;

    p2.reset(new int[10]); // p2 指向新的堆内存，p2 引用计数重置为 1，p3 引用计数减 1
    std::cout << p1.get() << " " << p2.get() << " " << p3.get() << std::endl;
    std::cout << p1.use_count() << " " << p2.use_count() << " " << p3.use_count() << std::endl;

    return 0;
}

• C++11 shared_ptr 智能指针

std::weak_ptr

shared_ptr是采用引用计数的智能指针，多个shared_ptr实例可以指向同一个动态对象，并维护了一个共享的引用计数器。对于引用计数法实现的计数，总是避免不了循环引用或环形引用的问题，shared_ptr也不例外。

weak_ptr是为了配合shared_ptr而引入的一种智能指针，它指向一个由shared_ptr管理的对象而不影响所指对象的生命周期，也就是将一个weak_ptr绑定到一个shared_ptr不会改变shared_ptr的引用计数。不论是否有weak_ptr指向，一旦最后一个指向对象的shared_ptr被销毁，对象就会被释放。从这个角度看，weak_ptr更像是shared_ptr的一个助手而不是智能指针。

class A;
class B;

class A
{
public:
    A() { cout << "A Constructor..." << endl; }
    ~A() { cout << "A Destructor..." << endl; }
    weak_ptr<B> pb;  // 在 A 中引用 B
    // shared_ptr<B> pb;
};

class B
{
public:
    B() { cout << "B Constructor..." << endl; }
    ~B() { cout << "B Destructor..." << endl; }
    weak_ptr<A> pa;  // 在 B 中引用 A
    // shared_ptr<A> pa;
};

int main()
{
    shared_ptr<A> spa = make_shared<A>();
    shared_ptr<B> spb = make_shared<B>();
    spa->pb = spb;
    spb->pa = spa;
}

Function	Description
lock	creates a shared_ptr that manages the referenced object

• C++11 make_shared
• How do I call ::std::make_shared on a class with only protected or private constructors?
• std::weak_ptr<T>::lock

std::make_shared

C++11 引入

make_shared与new的区别：

• std::shared_ptr<object> ptr = new object()
  由于object是先创建的，那么在将object指针传给shared_ptr时，shared_ptr只能单独分配控制块，如下图：
  

• std::shared_ptr<object> ptr = std::make_shared<object>()
object和对应的控制块是同时创建的，如下图：
  

• C++11 make_shared

std::make_unique

C++14 引入

3 多线程

#include <mutex>
#include <condition_variable>

std::thread

#include <thread>

std::mutex

基本的互斥量。同一线程lock多次会造成未定义的行为，不同线程lock会阻塞，我们使用阻塞的特性。

std::timed_mutex

有超时机制的互斥量

std::recursive_mutex

可重入的互斥量

std::recursive_timed_mutex

结合timed_mutex和recursive_mutex特点的互斥量

std::shared_timed_mutex

具有超时机制的可共享互斥量

std::shared_mutex

共享的互斥量。底层实现是操作系统提供的读写锁。

• lock和unlock分别用于获取写锁和解除写锁。
• lock_shared和unlock_shared分别用于获取读锁和解除读锁。

我们一般将写锁模式称为排他锁 (Exclusive Locking)，将读锁模式称为共享锁 (Shared Locking)。

std::lock_guard

基于作用域的互斥量管理，构造加锁，析构解锁。

std::unique_lock

独占互斥量管理，C++11 引入。

通常与shared_mutex配合使用，此对象构造时自动对shared_mutex加写锁，析构时自动对shared_mutex解写锁。

std::shared_lock

共享互斥量管理，C++14 引入。

通常与shared_mutex配合使用，此对象构造时自动对shared_mutex加读锁，析构时自动对shared_mutex解读锁。

std::scoped_lock

多互斥量避免死锁的管理

std::condition_variable

使用此对象时，需要绑定一个lock_guard或unique_lock对象。

• wait wait_for wait_until 该操作能够原子性的释放互斥量mutex上的锁，并阻塞这个线程，当被通知后，解除当前阻塞线程，恢复互斥量mutex上的锁。
• notify_one notify_all 在持有锁的期间去唤醒阻塞线程。

std::condition_variable cv;
std::mutex m;
/* A thread */
std::unique_lock<std::mutex> lock(m);
cv.wait(m); // 解锁 m，阻塞等待
/* B thread */
cv.notify_one(); // A thread 解除等待

std::async

#include <future>

Since C++11

4 算法

#include <algorithm>

std::find_if

std::any_of

std::transform

#include <algorithm>

std::move

#include <utility>

/**
 *  @brief  Convert a value to an rvalue.
 *  @param  __t  A thing of arbitrary type.
 *  @return The parameter cast to an rvalue-reference to allow moving it.
*/
template<typename _Tp>
constexpr typename std::remove_reference<_Tp>::type&& move(_Tp&& __t) noexcept {
    return static_cast<typename std::remove_reference<_Tp>::type&&>(__t);
}

• C++ 标准库使用比如vector::push_back等这类函数时，会对参数的对象进行复制，连数据也会复制。这就会造成对象内存的额外创建，本来原意是想把参数push_back进去就行了，通过std::move，可以避免不必要的拷贝操作。
• std::move是将对象的状态或者所有权从一个对象转移到另一个对象，只是转移，没有内存的搬迁或者内存拷贝，所以可以提高利用效率，改善性能.。
• 对指针类型的标准库对象并不需要这么做。

std::forward

template<class T>
constexpr T&& forward(std::remove_reference_t<T>& arg) noexcept {
    // forward an lvalue as either an lvalue or an rvalue
    return (static_cast<T&&>(arg));
}
template<class T>
constexpr T&& forward(std::remove_reference_t<T>&& arg) noexcept {
    // forward an rvalue as an rvalue
    return (static_cast<T&&>(arg));
}

forward通常是用于完美转发的，它会将输入的参数原封不动地传递到下一个函数中，这个“原封不动”指的是，如果输入的参数是左值，那么传递给下一个函数的参数的也是左值；如果输入的参数是右值，那么传递给下一个函数的参数的也是右值。

template <class... Args>
void forward(Args&&... args) {
    f(std::forward<Args>(args)...);
}

引用折叠：

&& && -> &&
& && -> &
& & -> &
&& & -> &

5 文件流

#include <iostream>
#include <fstream>

Flag	Description
std::ios::app	append
std::ios::ate	at end
std::ios::in	read
std::ios::out	write
std::ios::trunc	clear

std::fstream

该数据类型通常表示文件流，且同时具有ofstream和ifstream两种功能，这意味着它可以创建文件，向文件写入信息，从文件读取信息。

std::ifstream

该数据类型表示输入文件流，用于从文件读取信息。

std::ofstream

该数据类型表示输出文件流，用于创建文件并向文件写入信息。

6 其它

std::chrono

#include <chrono>
struct Timer
{
    std::chrono::system_clock::time_point start, end;
    std::chrono::duration<float> duration;

    Timer()
    {
        start = std::chrono::high_resolution_clock::now();
    }
    ~Timer()
    {
        end = std::chrono::high_resolution_clock::now();
        duration = end - start;
        const float seconds = duration.count();
        if (seconds < 1) {
            std::cout << "Timer took " << seconds * 1000.0f << "ms" << std::endl;
        } else if (seconds < 60) {
            std::cout << "Timer took " << seconds << "s" << std::endl;
        } else {
            std::cout << "Timer took " << seconds / 60 << "min" << std::endl;
        }
    }
};

可用于统计程序运行的时间。

7 参考文献

• C++ STL 标准库基础
• 详解 C++11 智能指针
• C++ 中 map 与 unordered_map 的区别
• C++ Map 相同 key 是否覆盖问题分析
• 浅谈 std::forward
• c++ 之 std::move 原理实现与用法总结
• C++/C++11 中 std::transform 的使用
• std::async 的使用总结