STL 是“Standard Template Library”的缩写，中文译为“标准模板库”。STL 是 C++ 标准库的一部分，不用单独安装。

C++ 对模板（Template）支持得很好，STL 就是借助模板把常用的数据结构及其算法都实现了一遍，并且做到了数据结构和算法的分离。例如，vector 的底层为顺序表（数组），list 的底层为双向链表，deque 的底层为循环队列，set 的底层为红黑树，hash_set 的底层为哈希表。

为方便，以下省略

1
2
3
4
#include <iostream>
#include <stack>
#include <iostream>
using namespace std;

Vector

初始化

vector有许多初始化方式

1
2
3
4
5
6
7
8
vector<int> v1;// 仅声明, 没有分配空间
v1.reserve(20); // 当容量<=20时, 扩到20, 大于不做改变
vector<int> v2 (20); // 20个为0的元素
vector<int> v3(20, 3); // 20个为3的元素
vector<int> v4(v3); // 用v3初始化
vector<int> v5 {1, 2, 3};
int a[] = {1, 2, 3, 4};
vector<int> v6(a, a + 3); // 用迭代器初始化

容量和大小

1
2
3
4
5
v1.size() // 返回大小
v1.capacity() // 容量，一般比大小大
v1.resize (5); // 大小变为5，少于就增加默认值，多余就减去栈顶值
v1.resize (7, 99); // 使用默认值99，增加
s1.shrink_to_fit() // 类似于swift的sizeToFit() ? 把容量缩减为大小相等

访问

1
2
3
cout << v1.front();
cout << v1.back();
auto p = v1.data(); // vector<T> 返回 T*, 该指针指向v1

添加

1
2
v1.push_back(3);
v1.emplace_back("string");

emplace_back比push_back更有效率，如果是push_back(“123”)是构造了一个"123"的字符串然后再移动，而emplace_back()是在尾部直接构造，同时emplace_back()也允许你使用对象，像初始化的emplace一样。

值得注意的是，不能使用非成员函数去添加容器的元素

插入

1
2
3
4
5
vector<string> s1 {"first", "second"};
s1.emplace(++begin(s1), 'a', 5) // "first", "aaaaa", "second"
auto iter = s1.emplace(++s1.begin(), "two");// "first", "two", "aaaaa", "second"
// 这里iter是插入元素的迭代器，如果使用iter作为迭代器会在two的后面插入
s1.insert(++s1.begin(), "three");// "first", "three", "two", "aaaaa", "second"

如果要在指定位置插入，就用s1.begin()+n

删除

1
2
3
4
5
vector<int> v1 {1, 2, 3, 4, 5, 6, 7};
v1.pop_back() // 删除最后一个
auto iter = data.erase(v1.begin()+1); // 删除第二个元素，返回删除元素的后一个元素的迭代器
// 当然，也可以通过迭代器删除一段
auto iter = data.erase(v1.begin()+1, v1.begin()+3); // 同样的，这里会返回这段的后一个元素的迭代器

接下来看erase-remove操作

1
2
3
4
5
#include <algorithm>
vector<int> v1 {1, 2, 3, 5, 5, 7, 8, 9};
auto iter = remove(v1.begin(), v1.end(), 5); // 1, 2, 3, 7, 8, 9, 8, 9 可见是帮我们做了前移
v1.erase(iter, v1.end()); // 删除多余的
v1.erase(remove(v1.begin(), v1.end(), 5);, v1.end()); // 当然也可以直接一次性

遍历

一共有三种遍历方式

1
2
3
4
5
6
7
8
9
10
11
12
vector<int> v1 {1, 2, 3};
// 迭代器
for (auto iter = v1.begin(); iter != v1.end(); iter++)
	cout << *v1;

for (auto i : v1)
  	cout << i;

for (int i = 0; i < v1.size(); i++)
  	cout << v1[i];

for_each(v1.begin(), v1.end(), [](int value) { cout << value << endl;}); // 第三个参数是一个function， 这里使用了lambda表达式

Stack

  • top()：返回一个栈顶元素的引用，类型为 T&。如果栈为空，返回值未定义。
  • push(const T& obj)：可以将对象副本压入栈顶。这是通过调用底层容器的 push_back() 函数完成的。
  • push(T&& obj)：以移动对象的方式将对象压入栈顶。这是通过调用底层容器的有右值引用参数的 push_back() 函数完成的。
  • pop()：弹出栈顶元素。不过这个是void类型
  • size()：返回栈中元素的个数。
  • empty()：在栈中没有元素的情况下返回 true。
  • emplace()：用传入的参数调用构造函数，在栈顶生成对象。
  • swap(stack<T> & other_stack)：将当前栈中的元素和参数中的元素交换。参数所包含元素的类型必须和当前栈的相同。对于 stack 对象有一个特例化的全局函数 swap() 可以使用。

对于emplace()和swap()函数举个例子吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
struct node 
{
    int data;
    node *next;
    node(int data, node* next)
    {
        this->data = data;
        this->next = next;
    }
};

int main()
{
    stack<int> stack1, stack2;
    for (int i = 0; i < 9; i++)
    {
        stack1.push(i);
        stack2.push(8-i);
    }
    // stack1: 0 1 2 ... 8
    // stack2: 8 7 6 ... 0
    stack1.swap(stack2);
    // stack2: 8 7 6 ... 0
    // stack1: 0 1 2 ... 8

    stack<node> nodeStack;
    nodeStack.emplace(1, nullptr);

}

参考：http://c.biancheng.net/stl/