string

1. string的size(), length()返回的大小包括截至符吗？sizeof求数组呢？strlen()函数呢？

    char arr[] = "abcde";
    int arraysize = sizeof(arr);    // 6
    int strlensize = strlen(arr);   // 5

    std::string str("abcde");
    int strsize = str.size();       // 5

作为字符串取大小都不包含截止符

 

string类包含的常用接口：insert，substr (字符串截取)，replace (字符串替换)，find

 

vector

1. vector的扩容逻辑

不同编译器结果不一样，如下测试代码：

std::vector<int> v;
int t = -1;
for (int i = 0; i < 1000000; i++) {
    if (t != v.capacity()) {
        std::cout << v.capacity() << std::endl;
        t = v.capacity();
    }
    v.push_back(i);
}

Linux下g++是两倍，

0
1
2
4
8
16
32
64
128
256
512
1024

Windows下vs没看出规律，

0
1
2
3
4
6
9
13
19
28
42
63
94
141

2. 二维数组初始化

先看一维数组初始化：vector<int> v(5, 1) // 表示5个1

二维数组初始化：vector<vector<int>> vv(5, vector<int>(6, 2)) //表示5行6列元素都为2

 

stack

内部实现是有双端队列容器封装而来，所以又叫做容器设配器

将双端队列的头部输入输出接口禁用即为栈

没有提供迭代器，无法通过接口遍历，想要遍历可以再构造一个栈，将一个栈的元素不断取出后加入到另一个栈中实现遍历。

queue

队列，常用接口front (队首元素，最先放入的)，back (队尾元素，最近放入的)

 由双端队列封装，将头部的进和尾部的出禁用掉几位队列，本质也是容器适配器

没有提供迭代器，无法通过接口遍历，想要遍历可以不断将队列首放在队列位来实现。

 

deque

双端队列，是有下标的顺序容器，允许在首尾两端快速的插入删除。

访问时间复杂度是o(1)，内部结构是有一个顺序的指针表，通过指针表访问数据，而数据所在的内存空间是不连续的，有指针表保证访问的高效性。

 

proprity_queue

优先队列

属于容器适配器，提供常数时间最大元素查找，对数代价的插入与删除。

内部数据结构是一个由数组形成的二叉树堆，对于二叉树插入删除是log级别，查找最大值也就是树根就是o(1)。

用用户提供的 Compare 更改顺序，例如，用 std::greater<T> 将导致最小元素作为 top() 出现。

// 小顶堆，先弹出小元素
std::priority_queue<int, std::vector<int>, std::greater<int> > q;

 对于自定义类型的排序，可以通过重载自定义类中的小于号；或者使用lambda表达式传入；或者传入一个类，这个类中重载()括号操作符。

Note：涉及到排序的容器必须指定排序方法，重载操作符时必须重载小于号。

 

set

存自定义结构时需要指定排序规则。

set内部数据结构是平衡树（红黑树），需要排序规则。插入查找都是对数级。

 

unordered_set

set的无序版本，用hash表实现，搜索，插入，删除有平均常数级时间复杂度。

unordered_map

同unordered_set

同样还有：

unordered_multiset

unordered_multimap