> For the complete documentation index, see [llms.txt](https://legacy.cookielau.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://legacy.cookielau.com/archives/1-cpp/1-containers.md).

# Container

## Container

### Vector

| Operations   |                           Meanings                          |
| ------------ | :---------------------------------------------------------: |
| constructors |      create vectors and initialize them with some data      |
| operators    |       compare, assign, and access elements of a vector      |
| assign       |                 assign elements to a vector                 |
| at, index    |          returns an element at a specific location          |
| back         |       returns a reference to last element of a vector       |
| begin        |      returns an iterator to the beginning of the vector     |
| capacity     |   returns the number of elements that vector **can** hold   |
| clear        |             removes all elements from the vector            |
| empty        |          returns true if the vector has no elements         |
| end          |     returns an iterator to the first element of a vector    |
| erase        |                remove elements from a vector                |
| front        |     returns a reference to the first element of a vector    |
| insert       |               inserts elements into the vector              |
| max\_size    | returns the maximum number of elements that vector can hold |
| pop\_back    |             removes the last element of a vector            |
| push\_back   |           add an element to the end of the vector           |
| rbegin       |     returns a reverse iterator to the end of the vector     |
| rend         |  returns a reverse iterator to the beginning of the vector  |
| reserve      |           sets the minimum capacity of the vector           |
| resize       |                changes the size of the vector               |
| size         |         returns the number of elements in the vector        |
| swap         |        swaps the contents of this vector with another       |

**Constructor 相关**

```cpp
1. vector<int> array; // 默认为空
2. vector<int> array(n); // 初始化n个0元素
3. vector<int> array(m, x); // m个元素，每个都初始化为x
4. vector<int> a2(a1);
5. vector<int> a2 = a1;
   // 上面两种方式等价，a2初始化为a1的拷贝，其中a1必须与a2类型相同
   // 也就是同为vector<int>类型，a2将具有和a1相同的容量和元素
6. vector<int> a2(a1, a1+6) // 将a1的前六个元素拿来初始化a2 
7. vector<int> {0,1,2,3,4}; // 列表初始化
8. vector<int> a2(a1.begin()+2,a1.end()-1); 
    // a1.end()指向a1的末尾元素下一位置迭代器，第二个参数指向的元素本身不会被拷贝到新数组中，到它的前一个元素截止
    // 例如 a1中元素为{0,1,2,3,4,5}上述操作a2结果为{2,3,4}。
9. vector<vector<int>> matrix(m, vector<int>(n,0)); //构建m*n的二维数组，初始化每个元素为0
```

**常用函数**

```cpp
array.push_back(element);//在末尾插入元素
array.size();//array中的元素个数

**erase**
iterator erase( iterator loc ); //删除 loc 位置上的元素
iterator erase( iterator start, iterator end ); //删除从 start 到 end 位置上的元素，不动 end
e.g. array.erase(array.begin()+i);//删除第i个元素，用begin迭代器加i
// **注意**：vector为了保证数据的连续性，会在每次删除之后将数据整体往前移，即保证头地址不动
// 后面的连续存储，所以如果是迭代器中删除，删除之后记得 iter--; 类似的操作

array.clear(); // 清空数据

TYPE array.back(); // 返回array的最后一个元素
TYPE array.front(); // 返回array的第一个元素

iterator array.begin(); // 返回指向首个元素的迭代器
iterator array.end(); // 返回指向尾部的 **下一个** 的迭代器
// 注意区别上面四个的关系，前两个 back 和 front 是返回元素，可以直接取元素的内容
// 下面两个是返回迭代器，需要前加 * 才能取里面的内容
// 而且 end 返回的是末尾的下一个，back 返回的是末尾

iterator insert( iterator loc, const TYPE& val );  
void insert( iterator loc, size_type num, const TYPE& val );  
void insert( iterator loc, input_iterator start, input_iterator end ); 
e.g. a1.insert(a1.end(),a2.begin(),a2.end());将a2数组所有元素插入到a1数组后面
```

**排序**

```cpp
sort(a.begin(), a.end()); //对a中的元素排序，默认从小到大排
sort(a.begin(), a.end(), cmp); //写成这种形式可以自定义比较函数cmp

//自定义比较函数 cmp
(static) bool cmp(const int &a,const int &b) {   
    return a>b;
}
//在转换字符串等某些场景下需要在函数返回值类型前加static，或者将该函数移到类外面，不然容易报错

//结构体：
struct ss {
    int x,y;
};
//自定义结构体比较函数 cmp
(static) bool cmp(const ss &x,const ss &y) {
    return (x.x != y.x)? x.x<y.x : x.y<y.y; //二维偏序 
}
```

**遍历访问**

```cpp
// 迭代器 iterator 访问
// it 是指向容器的迭代器指针，可以直接通过 ++,-- 移动
// *it 取指针指向的元素的内容
int main() {
    vector<int> s;
    s.push_back(1);
    for (vector<int>::iterator it=s.begin(); it!=s.end(); it++)
        cout << *it<<endl;
    return 0;
}

// 数组下标访问
int main() {
    vector<int> s;
    s.push_back(1);
    for (int i=0; i<s.size(); i++)
        cout << s[i]<<endl;
    return 0;
}
```

**修改内容** 访问下标方式：

```cpp
// 直接取是访问 vector 里面的内容，并没有修改的权限，需要加引用才能修改
if(abc.begin()!=abc.end()) {
    for (unsigned int i = 0;i<abc.size();i++) {
            abc[i] = i+1;
    }
    cout<<"原始数据："<<endl;
    vector_out(abc);
    auto &val2 = abc.back(); // val2为指向最后一个元素的引用
    val2 = 2;
    cout<<"变量为引用类型，修改后："<<endl;
    vector_out(abc);
    auto val3 = abc.back(); // 仅是abc.back()的一个拷贝
    val3 = 10;
    cout<<"变量不是一个引用,修改无效："<<endl;
    vector_out(abc);
}
```

![](/files/-M0d6P0LAWt2NJNxp8Oj)

迭代器方式：

```cpp
// 普通的迭代器 iterator 可以直接修改，直接 (*it)然后修改即可
// 特殊的放置修改的迭代器 const iterator 可以避免发生误修改，即只能读
// c++11 中的 foreach 其实用的就是迭代器

1. 
for (auto e : lists) {
    e[0] = 100; // 修改失败，因为是值传递的 iterator
} 
2. 
for (auto& e : lists) {
    e[0] = 100; // 修改成功，因为是引用传递的 iterator
}
3. 
for (const auto& e : lists) {
    e[0] = 100; // 修改失败，const 决定了是 read-only，加不加 & 无影响 
}
4. 
for (vector<int>::iterator it=lists.begin();it!=lists.end();it++) {
    (*it)[0] = 100; // 修改成功，因为 iterator 直接指向的是地址
}
5. 
for (vector<int>::const_iterator it=lists.begin();it!=lists.end();it++) {
    (*it)[0] = 100; // 修改失败，因为 const_iterator 是 read-only
}
```

**去除重复值**

e.g.

```cpp
vector<T> vec;
initialize(vec);
...

sort(vec.begin(), vec.end());  // 要先进行排序
vector<T>::iterator dup_head = unique(vec.begin(), vec.end());  // 然后使用unique返回一个iterator
vec.erase(dup_head, vec.end());  // 从返回的 dup_head 开始删除后面的所有元素

几个注意的地方：  
0. 其作用是将容器中重复的元素都移动到队尾，具体实现方式是从第一个参数开始遍历，看当前元素是否和上一个元素相同，相同则移动到对位，所以在使用 unique 之前先要进行 **排序操作**  
1. 第一个参数为开始的元素的iterator   
2. 第二个参数为末尾的下一个iterator  
3. 返回值是一个iterator指向重复序列的第一个元素  
4. 只是做了一个遍历所以容器内的元素个数不发生改变，只是位置发生了变化  
```

为什么扩容选择 1.5X or 2X <https://www.drdobbs.com/c-made-easier-how-vectors-grow/184401375> <https://www.zhihu.com/question/36538542/answer/67929747> 由于扩容时会发生空间的重新配置，因此指向原vector的迭代器会失效， 因此注意当迭代器遍历的时候尽量不要插入新数据

vector 还提供 reference front() 和 reference back() 函数， 返回第一个/最后一个值的引用，因此 v.front() 和 \*v.front() 值是一样的

erase() 会引起数据的拷贝

### List

List 内部指针为 void\* 类型指针，且有 prev 和 next，是一个双向链表 因此迭代器返回的是 bidirectional iterator

由于 List 不会引起空间的重新配置，因此在插入和拼接时不会发生迭代器失效 内部对迭代器的 ++/-- 进行了运算符重载使得其向前向后移动更加方便

List 内部刻意内置了一个空接点 node 并指向自身成环，这样的好处是：

1. 一个 node 即可表示整个链表
2. node 所在位置即链表的 end()，更加符合前闭后开区间的要求
3. 判断 empty() 更加方便：node->next == node

List 的 insert 会 insert 到当前迭代器的位置上，从结果来看即从迭代器开始数据后移 如： 1,2,3,4,5 在 \*(ite)=3 时 insert(ite, 0) 会得到 1,2,0,3,4,5 的结果

Unique 操作是 **移除连续且相同的值**，对于不连续的值无法删除 如： 1,2,3,3,4,3 unique 操作后得到 1,2,3,4,3

transfer(iterator position, iterator begin, iterator end) 迁移操作是内部非公开函数 用来辅助 List 的 splice, merge, reverse, sort 等 具体作用是将 \[begin(), end()) 的值 **移动** 插入到 position 处 由于 STL::sort 仅支持 RandomAccessIterator 因此需要调用自己的 member function list.sort() list.sort() 深度解析：<https://www.cnblogs.com/avota/archive/2016/04/13/5388865.html>

### deque

双向 vector，实现极其繁琐，本质为维护指向buffer的指针，在buffer中进行操作 相比于 vector 而言，在前端插入不会引起数据的移动，作为 stack 和 queue 的底层支持 但是排序操作会非常费时，考虑到不同的 buffer 之间的指针的移动

### stack & queue

stack：先进后出，底层用 deque，禁用了其前端出入的特性 queue：先进先出，底层用 deque，禁用了其前端入后端出的特性 两者都可以用 list 作为底层实现，方式为 stack\<int, list> 两者都不提供迭代器，因为只有单一出口方式 stack：top() 返回顶部的值，pop() **无返回值** queue：front() 返回前端的值，back() 返回后端的值，push() 将元素从后端加入，pop() 将元素从前端取出

### Priority\_queue

| Operations   |                            Meanings                           |
| ------------ | :-----------------------------------------------------------: |
| constructors | create priority\_queue and initialize them with some features |
| empty        |           returns true if the vector has no elements          |
| size         |          returns the number of elements in the vector         |
| pop          |  removes the top element of a priority queue, no return value |
| push         |        adds an element to the end of the priority queue       |
| top          |         returns the top element of the priority queue         |

**排序**

```cpp
1. 自带的排序
priority_queue <int, vector<int>, less<int>> p;
priority_queue <int, vector<int>, greater<int>> q;

// 这里的 less 和 greater 只适用于cpp能够识别的数据类型
// 换而言之，不支持自定义的结构体，支持 int, float, string, pair<int, int>等等
// 对于 pair 而言，就是先比较 first，再比较 second 的值

// less 和 greater 是设置递增递减，记忆时可以理解为趋势
// less 即变小的趋势 —— 递减，从大到小
// greater 即变大的趋势 —— 递增，从小到大

2. 自定义的排序——结构体内重载运算符实现（推荐）
priority_queue <Node, vector<Node>, greater<Node>> p
struct Node {
    int first, second;
    Node(int first, int second) : first(first), second(second) {}
    bool operator<(const Node& x) const { // 一定要注意这里两个const
        return (first==x.first)? second>x.second:first<x.first;
    }
};


3. 自定义的排序——结构体函数实现
priority_queue <int, vector<int>, cmp> q;

// 这里的cmp是自己定义的一个结构体函数，如：
class Node{ 
public: 
    int x,y;
    Node(int x, int y) : x(x), y(y) {}
};

class Solution {
public:
struct cmp
{
    bool operator () (const Node &x,const Node &y) const
    {
        return x.x<y.x;
    }
};

int main() {
    xxxxx

    priority_queue <int, vector<int>, cmp> q; // declaration

}
}
// 上面的结构体函数就可以将自定义的 Node 按照 x 进行从小到大的排序

4. 自定义的排序——结构体外重载运算符实现
// 我们知道，priority_queue 的维护实际上就是在一直比较元素大小并交换位置
// c++ 作为面向对象语言有重载运算符的特性，如果我们将结构体的大小比较做定义
// 那么就可以让机器识别我们的结构体类型了

struct Node {
        int x,y,z;
        Node(int x, int y, int z) : x(x), y(y), z(z) {}
};

// 重载小于符号，使得 less<Node> 生效
bool operator<(const Node a, const Node b) {
        return (b.x==a.x)? b.y>a.y:b.x>a.x;
}

// 重载大于符号，使得 greater<Node> 生效
bool operator>(const Node a, const Node b) {
        return (b.x==a.x)? b.y<a.y:b.x<a.x;
}

// 在声明的时候就可以直接使用原生的 less 和 greater 了
priority_queue(Node, vector<Node>, less<Node>) p; // 从小到大
priority_queue(Node, vector<Node>, greater<Node>) p; // 从大到小
```

### map/unordered\_map

两者的对比：

|  特性  |          map         |      unordered\_map     |
| :--: | :------------------: | :---------------------: |
| 内部组织 |          红黑树         |           哈希表           |
| 组织特性 |         自动排序         |          插入查找迅速         |
| 运行效率 |          较低          |            较高           |
| 占用内存 |          较低          |            较高           |
| 时间大头 |         查询删除         |            插入           |
| 使用场景 | 要求内部有序稳定的查找速率,内存需要考虑 | 不需要容器内有序,快速查找删除,不担心内存占用 |

#### RB\_tree

红黑树查找的时间复杂度为 O(lgn) 的证明： <https://blog.csdn.net/cxyj666/article/details/88636854>

#### hash\_table

桶+红黑树解决哈希冲突

#### multimap/multiset

允许出现重复 key 的 map/set，区别在于底层调用了 insert\_equal() 而不是 insert\_unique()

#### Map

| Operations   |                                                                                                     Meanings                                                                                                     |
| ------------ | :--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------: |
| begin        |                                                                                returns an iterator to the beginning of the vector                                                                                |
| clear        |                                                                                       removes all elements from the vector                                                                                       |
| count        |                                                                                returns the number of occurrences of key in the map                                                                               |
| empty        |                                                                                    returns true if the vector has no elements                                                                                    |
| end          |                                                                               returns an iterator to the first element of a vector                                                                               |
| equal\_range | <p>pair\<iterator, iterator> equal\_range( const key\_type& key )<br>return two iterators<br>one to the first element that contains key<br>another to a point just after the last element that contains key.</p> |
| erase        |                                                                                           remove elements from a vector                                                                                          |
| find         |                                                          <p>returns an iterator to key if found<br>or an iterator to the end of the map if not found</p>                                                         |
| insert       |                                                                                         inserts elements into the vector                                                                                         |
| key\_comp    |                                                                                      returns the function that compares keys                                                                                     |
| lower\_bound |                                                            returns an iterator to the first element which has a value **greater than or equal to** key                                                           |
| max\_size    |                                                                            returns the maximum number of elements that vector can hold                                                                           |
| rbegin       |                                                                                returns a reverse iterator to the end of the vector                                                                               |
| rend         |                                                                             returns a reverse iterator to the beginning of the vector                                                                            |
| size         |                                                                                   returns the number of elements in the vector                                                                                   |
| swap         |                                                                                  swaps the contents of this vector with another                                                                                  |
| upper\_bound |                                                               returns an iterator to the first element in the map with a key **greater than** key.                                                               |
| value\_comp  |                                                                                     returns the function that compares values                                                                                    |

Map 的内部使用红黑树实现，保证了时刻的有序性，所以其自带用比较函数实现的一些功能，如: `lower_bound()` 和 `upper_bound()`。特别要注意不要被英文名弄乱，`lower_bound()` 其实就是**大于等于**，`upper_bound()` 就是**大于**。

在 Leetcode No.699 中使用到 lower\_bound() 来寻找最前相交的方块。

## STL\_Feature

### iterator & reverse\_iterator

迭代器和反向迭代器 他们居然不是同一个类 在实现上面反向迭代器完全就是根据迭代器实现的，反向迭代器从尾部元素开始，到首元素的前一个(空元素)结束，反向迭代器++相当于内部维护的迭代器--。 **但是**，因为 reverse\_iterator 和iterator 不是一个东西，所以很多地方传入的参数需要的是 **迭代器类型**，而不是 **反向迭代器类型**，就需要通过新建一个迭代器然后取遍历到达反向迭代器所指元素。

具体使用的话在 LeetCode 218 SkyLine 中用过一次。

#### 使用 iterator 安全删除容器元素

当我们想要在遍历的时候删除容器内的元素时，由于对iterator的特性不熟悉容易导致iterator乱飘出现漏删或者跳跃的问题，这里统一一下方法：

```cpp
map<int, int> mp;
for (auto it = mp.begin(); it != mp.end(); ) {
    if (it->first xxx) {
        mp.erase(it++); 
    }
}
```

it++ 的操作既保留了当前需要删除的迭代器指向的副本，又将it指向了正确的下一个迭代器的位置，美哉。

### Reference

1. 《CPP STL Reference Manual》
2. [C++ STL算法系列4---unique , unique\_copy函数](https://www.cnblogs.com/heyonggang/p/3243477.html)

#### Algorithm

**lower\_bound & upper\_bound**

lower\_bound 插入使得依然有序的最早位置 upper\_bound 插入使得依然有序的最晚位置 E.g. 1 2 2 2 3 插入 2 lower\_bound: 1 | 2 2 2 3 upper\_bound: 1 2 2 2 | 3 **Caution**: 自定义comp函数要严格小于，小于等于会出现问题

**sort**

<https://mp.weixin.qq.com/s/6h1R6UoDDZwfIkBEAt63ew> 包含 \_\_introsort\_loop 内省排序 和 \_\_final\_insertion\_sort 插入排序 内省排序会根据元素的长度给出一个快速排序的深度限制 超过深度限制时会直接使用堆排序结束剩下的部分 当内省排序的数组长度小于 threshold==16 时返回给插入排序解决剩下的部分 快速排序使用了尾递归的方式减少了一半的递归调用，具体地只对后半部分进行递归操作，前半部分留给while循环操作 堆排序函数详解 <https://www.jianshu.com/p/22fe785d607b> copy\_backward也是一种整体移动的优化，避免了one by one的调整移动，底层调用memmove来高效实现。