C/C++语言基础--C++STL库之容器入门(array、vector、string、deque、list、forward_list、stack、queue、prority_queue、set)等
list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。
·
本专栏目的
- 更新C/C++的基础语法，包括C++的一些新特性
前言
- STL无疑是C++史上一个重要的发明，未来我将更新STL有关的知识点，入门绝对够了(看目录就知道了👀)
- 这是第三篇，讲容器，容器就是封装好的数据结构；
- C语言后面也会继续更新知识点，如内联汇编；
- 欢迎收藏 + 关注，本人将会持续更新。
初学主要学会如何使用，常用操作如下：
vector, 变长数组，倍增的思想
size() 返回元素个数
empty() 返回是否为空
clear() 清空
front()/back()
push_back()/pop_back()
begin()/end()
[]
支持比较运算，按字典序
pair<int, int>
first, 第一个元素
second, 第二个元素
支持比较运算，以first为第一关键字，以second为第二关键字（字典序）
string，字符串
size()/length() 返回字符串长度
empty()
clear()
substr(起始下标，(子串长度)) 返回子串
c_str() 返回字符串所在字符数组的起始地址
queue, 队列
size()
empty()
push() 向队尾插入一个元素
front() 返回队头元素
back() 返回队尾元素
pop() 弹出队头元素
priority_queue, 优先队列，默认是大根堆
size()
empty()
push() 插入一个元素
top() 返回堆顶元素
pop() 弹出堆顶元素
定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;
stack, 栈
size()
empty()
push() 向栈顶插入一个元素
top() 返回栈顶元素
pop() 弹出栈顶元素
deque, 双端队列
size()
empty()
clear()
front()/back()
push_back()/pop_back()
push_front()/pop_front()
begin()/end()
[]
set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
size()
empty()
clear()
begin()/end()
++, -- 返回前驱和后继，时间复杂度 O(logn)
set/multiset
insert() 插入一个数
find() 查找一个数
count() 返回某一个数的个数
erase()
(1) 输入是一个数x，删除所有x O(k + logn)
(2) 输入一个迭代器，删除这个迭代器
lower_bound()/upper_bound()
lower_bound(x) 返回大于等于x的最小的数的迭代器
upper_bound(x) 返回大于x的最小的数的迭代器
map/multimap
insert() 插入的数是一个pair
erase() 输入的参数是pair或者迭代器
find()
[] 注意multimap不支持此操作。 时间复杂度是 O(logn)
lower_bound()/upper_bound()
unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
和上面类似，增删改查的时间复杂度是 O(1)
不支持 lower_bound()/upper_bound()， 迭代器的++，--
bitset, 圧位
bitset<10000> s;
~, &, |, ^
>>, <<
==, !=
[]
count() 返回有多少个1
any() 判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置成1
set(k, v) 将第k位变成v
reset() 把所有位变成0
flip() 等价于~
flip(k) 把第k位取反
下面对一些API进行讲解
序列式容器
string
string概念
- string是STL的字符串类型，通常用来表示字符串。而在使用string之前，字符串通常是用char表示的。string与char都可以用来表示字符串，那么二者有什么区别呢。
string和char*的比较
-
string是一个类, char*是一个指向字符的指针。
string封装了char*，管理这个字符串，是一个char*型的容器
-
string不用考虑内存释放和越界。
string管理char所分配的内存。每一次string的复制，取值都由string类负责维护，不用担心复制越界和取值越界等。
-
string提供了一系列的字符串操作函数（这个等下会详讲）
查找find，拷贝copy，删除erase，替换replace，插入insert
string的构造函数
string(); //默认构造
string(const char* ptr); //char*指向的字符串
string(const string& right); //拷贝构造
string(string&& right); //移动构造
string(iter first,iter last); //以相同顺序复制[first，last)范围内的字符
string(const size_t count,const char c); //生成count个由字符c组成的序列
string(const char *ptr,size_t count); //char*指向的字符串，前count个字符
string的存取字符操作
ostream& operator<<(ostream& out,string& right); //直接输出string
char& operator[](size_t off); //获取off下标的字符(相对于首地址的偏移)
char& at(size_t off); //同上 但是越界会抛异常
char& front(); //获取头部元素
//*********char& back(); //获取尾部元素
string容量相关
size_t size(); //获取字符串长度
size_t length(); //同上
size_t max_size(); //字符串可以存储的最大长度
size_t capacity(); //获取string内部存储字符串的内存大小，自动扩容
void reserve(size_t n); //请求更改容量，如果n大于当前字符串的容量，则使容器将其容量增加到n个字符（或更大）,小于可能不予理会(与实现有关)
void resize(size_t n,char c = '\0'); //调整字符串大小, 如果n小于当前字符串长度，则当前值将缩短为它的前n个字符，并删除第n个字符之外的字符。 如果n大于当前字符串的长度,则以c进行填充多余空间。
void clear(); //清空字符串，长度变为0
bool empty(); //判断是否为空串，即size == 0
void shrink_to_fit(); //请求sting减小其容量到合适大小(可能不予理会)
string修改
string& operator+=(string& right);
string& operator+=(char * str);
string& operator+=(char c);
//append
string& append(string& right);
string& append(string& right,size_t pos,size_t sublen = npos); //从right pos位置开始，复制sublen长度到this
string& append(char *str);
string& append(char *str,size_t n); //把str的前n个追加到当前string
string& append(size_t n,char c); //追加n个字符c
string& append(iter first,iter last); //以相同顺序追加[first，last)范围内的字符
void push_back(char c); //追加字符c
//和构造函数差不多
string& assign(...); //为字符串分配一个新值，替换其当前内容
//和append差不多，只是多了个插入位置
string& insert(size_t pos,string& str); //将str插入到pos所指示的字符之前
string& erase(size_t pos = 0,size_t len = npos); //删除从pos开始跨越len个字符的部分
iterator erase(iter p); //删除p指向的字符
iterator erase(iter first,iterator last); //删除[first,last)范围内的字符
string& replace(size_t pos,size_t len,string &str);
string& replace(iter i1, iter i2, const string& str);
string& replace(size_t pos, size_t len, const string& str,
size_t subpos, size_t sublen);
string& replace(size_t pos, size_t len, const char* s);
string& replace(size_t pos, size_t len, const char* s, size_t n);
string& replace(iter i1, iter i2, const char* s, size_t n);
string& replace(size_t pos, size_t len, size_t n, char c);
string& replace(iter i1, iter i2, size_t n, char c);
template <class Inputiter>
string& replace (iter i1, iter i2,Inputiter first, Inputiter last);
void swap(string& str); //交换两个string的内容
void swap(string& left,string& right); //全局重载
void pop_back(); //删除最后一个字符
string操作
const char* c_str(); //获取c风格字符串
const char* data(); //同上
size_t copy(char* s,size_t len,size_t pos = 0);//把当前串中以pos开始的len个字符拷贝到以s为起始位置的字符数组中，返回实际拷贝的数目。注意要保证s所指向的空间足够大以容纳当前字符串，不然会越界。
//find:返回查找到的起始下标，找不到返回string::npos
size_t find(const string& str, size_t pos = 0); //从pos位置开始查找str
size_t find(const char* s, size_t pos = 0); //从pos位置开始查找s
size_t find(const char* s, size_t pos, size_t n);//把s中的前n个字符，在string中的pos位置开始查找
size_t find(char c, size_t pos = 0); //从pos位置开始查找字符c
size_t rfind(...); //同上，只不过是反向查找
size_t find_first_of(...); //查找与参数中字符串任意一个字符匹配的第一个字符
size_t find_last_of(...); //同上，反向查找
size_t find_first_of(...); //查找与参数中字符串任意一个字符都不匹配的第一个字符
size_t find_last_of(...); //同上，反向查找
//////////////// 重点
string substr(size_t pos=0,size_t len=npos);//返回一个新构造的string对象，其值初始化为该对象的子字符串的副本。
string静态成员
- npos是一个静态成员常量值，被定义为-1，但是size_t是unsigned int，值是最大值(4294967295)
- 用作字符串成员函数中len（或sublen）参数的值时，此值表示*“直到字符串结尾”*。
array
array概念
array是一个容器，封装了固定大小的数组。
array初始化
array没有构造函数，也没有私有或保护成员，这就意味着它不会自动初始化。如果不对其初始化而直接获取其中的值，读出来的是野值。
可以使用聚合表达式（花括号）对其初始化。
array<int,5> arr = {1,2,3,4,5};
如果花括号内元素个数小于数组容量，则会为剩余元素自动赋默认值。
也可以用fill函数对其填充。
array<int,10> arr;
arr.fill(3);
对于元素类型和数组大小相同的array，可以直接进行赋值
array<int,5> a1;
array<int,5> a2 = a1;
array元素访问
Ty& operator[](size_t i);
Ty& at(size_t i);
Ty& front();
Ty& back();
Ty* data(); //返回指向数组中第一个元素的指针
array容量相关
size_t size(); //返回数组大小
size_t max_size(); //返回数组大小
size_t empty(); //返回数组是否为空
array修改
void fill(const Ty& val); //把所有元素都设置为val
void swap(array<Ty,?>& other); //交换两个array的数据，类型和大小必须一致
vector
Vector概念
vector 容器是 STL 中最常用的容器之一，它和 array 容器非常类似，都可以看做是对 C++普通数组的“升级版”。不同之处在于，array 实现的是静态数组（容量固定的数组），而 vector 实现的是一个动态数组，即可以进行元素的插入和删除，在此过程中，vector 会动态调整所占用的内存空间。
特点：vector尾部添加或移除元素非常快速。但是在中部或头部插入元素或移除元素比较费时
vector的构造函数
vector();
vector(initializer_list<_Ty> list); //可以用聚合{}的方式初始化
vector(size_t size); //指定vector初始大小
vector(size_t size, const Ty& val); //指定大小，并把每个数据都设置为val
vector(Iter first, Iter last); //以相同顺序复制[first,last)范围内的元素
vector(const vector& _Right); //拷贝构造
vector(vector&& _Right); //移动构造
vector元素访问
Ty& operator[](size_t i);
Ty& at(size_t i);
Ty& front();
Ty& back();
Ty* data(); //返回指向数组中第一个元素的指针
vector容量相关
size_t size(); //获取vector有效元素个数
size_t max_size(); //可以存储的最大元素数量
size_t capacity(); //获取当前容量，自动扩容
void reserve(size_t n); //请求更改容量，如果n大于当前字符串的容量，则使容器将其容量增加到n个字符（或更大）,小于可能不予理会(与实现有关)
void resize(size_t n); //调整vector大小为n,n小于当前size，多余的数据会被丢掉
void resize(size_t n,const Ty& val); //如果n>size,剩下的用val填充
void clear(); //清空数据，长度变为0
bool empty(); //判断是否为空串，即size == 0
void shrink_to_fit(); //请求vector减小其容量到合适大小
vector修改
void push_back(const Ty& val); //在尾部插入元素
void push_back(Ty&& val); //同上
void emplace(Iter where,_Valty&& val); //效率比较高
void emplace_back(_Valty&& val)
void pop_back(); //删除尾部元素
void assign(const size_t size, const Ty& val);//设置新的大小，并用val设置所有值
void assign(Iter First, Iter Last); //以相同顺序复制[first,last)范围内的元素
void assign(initializer_list<_Ty> Ilist); //同时赋值多个元素
iter insert(iter _Where, const Ty& Val); //指定位置插入元素
iter insert(iter _Where, const size_t Count, const Ty& val);//指定位置插入，并且可以指定插入数量
iter insert(iter _Where, Iter First, Iter Last);//指定位置插入[first,last)之间的元素
iter insert(iter _Where, initializer_list<_Ty> Ilist);
iterator erase(iter pos); //删除pos指向的元素
iterator erase(iter first,iterator last); //删除[first,last)范围内的字符
void swap(vector& str); //交换两个vector的内容
deque
Deque概念
deque是“double-ended queue”的缩写，和vector一样都是STL的容器，deque是双端队列，而vector是单端的。
deque在接口上和vector非常相似，在许多操作的地方可以直接替换。
- deque 容器也擅长在序列尾部添加或删除元素（时间复杂度为
O(1)），而不擅长在序列中间添加或删除元素。 - deque 容器也可以根据需要修改自身的容量和大小。
和 vector 不同的是，deque 还擅长在序列头部添加或删除元素，所耗费的时间复杂度也为常数阶O(1)。并且更重要的一点是，deque 容器中存储元素并不能保证所有元素都存储到连续的内存空间中。
deque构造函数
deque(); //默认构造
deque(size_t count); //指定size
deque(size_t count, Ty& val); //批量构造
deque(const deque& right); //拷贝构造
deque(deque&& right); //移动构造
deque(Iter first,Iter last); //区间构造
deque元素访问
Ty& operator[](size_t i);
Ty& at(size_t i);
Ty& front();
Ty& back();
deque容量相关
size_t size(); //获取有效元素个数
size_t max_size(); //可以存储的最大元素数量
void resize(size_t n); //调整大小为n,n小于当前size，多余的数据会被丢掉
void resize(size_t n,const Ty& val); //如果n>size,剩下的用val填充
void clear(); //清空数据，长度变为0
bool empty(); //判断是否为空串，即size == 0
void shrink_to_fit(); //请求减小其容量到合适大小
deque的修改
void push_back(const Ty& val); //在尾部插入元素
void push_back(Ty&& val); //同上
void push_front(const Ty& val); //在头部插入元素
void push_front(Ty&& val); //同上
void emplace(Iter where,_Valty&& val); //效率比较高
void emplace_back(_Valty&& val);
void emplace_front(_Valty&& val)
void pop_back(); //删除尾部元素
void assign(const size_t size, const Ty& val);//设置新的大小，并用val设置所有值
void assign(Iter First, Iter Last); //以相同顺序复制[first,last)范围内的元素
void assign(initializer_list<_Ty> Ilist); //同时赋值多个元素
iter insert(iter _Where, const Ty& Val); //指定位置插入元素
iter insert(iter _Where, const size_t Count, const Ty& val);//指定位置插入，并且可以指定插入数量
iter insert(iter _Where, Iter First, Iter Last);//指定位置插入[first,last)之间的元素
iter insert(iter _Where, initializer_list<_Ty> Ilist);
iterator erase(iter pos); //删除pos指向的元素
iterator erase(iter first,iterator last); //删除[first,last)范围内的字符
void swap(vector& str); //交换两个vector的内容
list
list简介
list 容器，又称双向链表容器，即该容器的底层是以双向链表的形式实现的。这意味着，list 容器中的元素可以分散存储在内存空间里，而不是必须存储在一整块连续的内存空间中。
list对象的默认构造
list();
list(size_t count);
list(size_t count,const Ty& val);
list(const list& right);
list(list&& right);
list(Iter first,Iter last);
list元素访问
Ty& front();
Ty& back();
list容量相关
bool empty();
size_t size();
size_t max_size();
void resize(size_t n); //调整大小为n,n小于当前size，多余的数据会被丢掉
void resize(size_t n,const Ty& val); //如果n>size,剩下的用val填充
list添加元素
void push_back(Ty& val);
void push_front(Ty& val);
void emplace_back(Args&&... args);
void emplace_front(Args&&... args);
Iter emplace(Iter pos,Args&&...args);
void assign(const size_t size, const Ty& val);//设置新的大小，并用val设置所有值
void assign(Iter First, Iter Last); //以相同顺序复制[first,last)范围内的元素
void assign(initializer_list<_Ty> Ilist); //同时赋值多个元素
iter insert(iter _Where, const Ty& Val); //指定位置插入元素
iter insert(iter _Where, Ty&& Val); //指定位置插入元素
iter insert(iter _Where, const size_t Count, const Ty& val);//指定位置插入，并且可以指定插入数量
iter insert(iter _Where, Iter First, Iter Last);//指定位置插入[first,last)之间的元素
iter insert(iter _Where, initializer_list<_Ty> Ilist);
list删除元素
iterator erase(iter pos); //删除pos指向的元素
iterator erase(iter first,iterator last); //删除[first,last)范围内的字符
void pop_front();
void pop_back();
void clear();
当使用一个容器的insert或者erase函数通过迭代器插入或删除元素"可能"会导致迭代器失效，因此我们为了避免危险，应该获取insert或者erase返回的迭代器，以便用重新获取的新的有效的迭代器进行正确的操作
lis<int> ls;
for (int i = 0; i < 10; i++)
{
ls.push_back(i);
}
list<int>::iter it;
for (it = ls.begin(); it != ls.end(); )
{
if (*it == 5)
{
it=ls.erase(it);
}
else
{
it++;
}
cout << *it << " ";
}
list的其他操作
//list拼接，x中的元素会被直接转移到当前list中，不会涉及元素的构造
void splice (Iter where, list& x); //把x插入到where位置,x会被清空
void splice (Iter where, list& x, Iter first);//把x的first位置的元素，插入到list的where位置
void splice (Iter where, list& x,Iter first, Iter last);//把x的[first,last)位置的元素，插入到list的where位置
void remove(const Ty& val); //删除所有等于val的元素。这将调用这些对象的析构函数，并通过删除元素的数量来减少容器的大小。erase按元素的位置(使用迭代器)删除元素
template<typename Predicate>
void remove_if(Predicate pred); //从容器中删除所有谓词pred返回true的元素。
void unique(); //从容器中每个相等元素的连续组中除去除第一个元素外的所有元素。
template <class Predicate>
void unique(Predicate _Pred);//以确定元素“唯一性”的特定比较函数作为参数。实际上，可以实现任何行为（并且不仅可以进行相等比较），从第二个开始）并删除如果谓词返回true，则从列表中返回i。
list<Stu> ls;
for (size_t i = 0; i < 10; i++)
{
ls.push_back(Stu(rand()%5));
}
ls.unique([](const Stu& left, const Stu& right)
{//如果left大于right 那么把right删掉
return left > right;
});
void merge(list& right); //合并两个链表，如果两个链表都有序，合并之后同样也是有序的，否则合并失败，程序中断
void sort(); //对list元素进行排序，默认是升序
void sort(Predicate _Pred); //可以自己修改排序规则
void reverse(); //反转list
通过remove删除元素时，自定义类型需要重载==运算符，而且需要加上const修饰
//需要用const修饰this指针，否则如下代码所示，会有报错
bool operator==(const Stu& right) const
{
return (this->_id == right._id);
}
// error C2678: 二进制“==”: 没有找到接受“const Stu”类型的左操作数的运算符(或没有可接受的转换)
//这是由于，test函数的两个参数都是const对象，如果不把this修饰为const，那么operator==函数，将不能把this转为const this
bool test(const Stu& val, const Stu& val2)
{
return val2 == val;
}
forward_list
单向链表。
forward_list构造函数
forward_list();
forward_list(size_t count);
forward_list(size_t count,const Ty& val);
forward_list(const list& right);
forward_list(list&& right);
forward_list(Iter first,Iter last);
forward_list迭代器
Iter before_begin(); //返回第一个元素的前一个位置，禁止解引用
forward_list元素访问
Ty& front();
forward_list容量相关
bool empty();
size_t max_size();
forward_list添加元素
void push_front(Ty& val);
void emplace_front(Args&&... args);
Iter emplace_after(Iter where,Args&&...args); //在where的下一个位置处插入新元素
void assign(const size_t size, const Ty& val);//设置新的大小，并用val设置所有值
void assign(Iter First, Iter Last); //以相同顺序复制[first,last)范围内的元素
void assign(initializer_list<_Ty> Ilist); //同时赋值多个元素
iter insert_after(iter _Where, const Ty& Val); //where下一个位置插入元素
iter insert_after(iter _Where, const size_t Count, const Ty& val);//where下一个位置插入，并且可以指定插入数量
iter insert_after(iter _Where, Iter First, Iter Last);//where下一个位置插入[first,last)之间的元素
iter insert_after(iter _Where, initializer_list<_Ty> Ilist);
forward_list删除元素
iterator erase_after(iter where); //删除where下一个位置的元素
iterator erase_after(iter first,iterator last); //删除(first,last)范围内的字符
void pop_front(); //删除头部元素
void clear(); //清空链表
forward_list的其他操作
//list拼接，x中的元素会被直接转移到当前list中，不会涉及元素的构造
void splice (Iter where, list& x); //把x插入到where下一个位置
void splice (Iter where, list& x, Iter first);//把x的first的下一个位置的元素，插入到list的where下一个位置
void splice (Iter where, list& x,Iter first, Iter last);//把x的(first,last)位置的元素，插入到list的where位置
void remove(const Ty& val); //删除所有等于val的元素。
template<typename Predicate>
void remove_if(Predicate pred); //从容器中删除所有谓词pred返回true的元素。
void unique(); //从容器中每个相等元素的连续组中除去除第一个元素外的所有元素。
template <class Predicate>
void unique(Predicate _Pred);//以确定元素“唯一性”的特定比较函数作为参数。实际上，可以实现任何行为（并且不仅可以进行相等比较），从第二个开始）并删除如果谓词返回true，则从列表中返回i。
void merge(list& right); //合并两个链表，如果两个链表都有序，合并之后同样也是有序的，否则合并失败，程序中断
void sort(); //对list元素进行排序，默认是升序
void sort(Predicate _Pred); //可以自己修改排序规则
void reverse(); //反转list
容器适配器
容器适配器都不支持迭代器
stack
Stack概念
stack是一种容器适配器，就是我们说的栈，专门设计用于在LIFO上下文（后进先出）中操作，在LIFO上下文中，仅从容器的一端插入和提取元素。
容器应支持以下操作：
- empty
- size
- back
- push
- pop
- top
标准容器类vector，deque 和list满足这些要求。默认情况下，使用标准容器 deque来作为底层容器。
stack对象的默认构造
stack() = default;
explicit stack (const container_type& _Cont);
explicit stack (container_type&& ctnr = container_type());
stack<int> s = { 1,2,3,4,5 }; //error 不能直接初始化
//如下，可以使用stack底层容器进行初始化
deque<int> dq = { 1,2,3,4,5 };
stack<int> s(dq);
stack其他
Ty& top(); //获取顶部元素
void pop(); //删除顶部元素
void push(const Ty& val); //入栈
void swap(stack& sk); //交换两个stack
size_t size(); //获取元素个数
bool empty(); //判空
template <class... _Valty>
void emplace(_Valty&&... _Val); //就地构造，提升效率
queue
queue概念
FIFO队列
queue是一种容器适配器，就是我们说的队列，专门设计用于在FIFO上下文中（先进先出）进行操作，在FIFO上下文中，将元素插入到容器的一端，并从另一端提取元素。
基础容器可以是标准容器类模板之一，也可以是其他一些专门设计的容器类。此基础容器应至少支持以下操作：
- empty
- size
- front
- back
- push_back
- pop_front
标准容器类 deque和list满足这些要求。默认情况下，如果未为特定容器指定容器类队列
类实例化，默认用标准容器 deque。
queue对象的默认构造
queue() = default;
explicit queue(const _Container& _Cont);
explicit queue(_Container&& _Cont);
queue其他
Ty& back(); //获取头部元素
Ty& front(); //获取尾部元素
void pop(); //删除头部元素
void push(const Ty& val); //入队(从尾部)
void swap(stack& sk); //交换两个queue
size_t size(); //获取元素个数
bool empty(); //判空
template <class... _Valty>
void emplace(_Valty&&... _Val); //就地构造，提升效率
priority_queue
priority_queue概念
priority_que(优先级队列)是一种容器适配器，经过专门设计，以使其按照某些*严格的弱排序（strict weak ordering）*标准，其第一个元素始终是其中包含的最大元素。
此类似于堆，可以在任何时候插入元素，并且只能检索最大堆元素（优先级队列顶部的元素）。
基础容器可以是任何标准容器类模板或某些其他专门设计的容器类。该容器应可通过随机访问迭代器访问并支持以下操作：
empty()size()front()push_back()pop_back()
标准容器类 vector和 deque满足这些要求。默认情况下，如果未为特定容器指定容器类
priority_queue 类实例化，默认使用vector作为底层容器。
需要支持随机访问迭代器，以始终在内部保持堆结构。容器适配器通过自动调用算法函数(make_heap， push_heap，pop_heap )维持堆结构。
priority_queue构造函数
priority_queue() = default;
explicit priority_queue(const _Pr& _Pred);
priority_queue (const _Pr& Pred, const Container& Cont);
priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred, const _Container& _Cont);
priority_queue(_InIt _First, _InIt _Last);
priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred);
priority_queue其他
Ty& top();
void pop();
void push(Ty& val);
void swap();
size_t size();
bool empty();
template <class... _Valty>
void emplace(_Valty&&... _Val)
关联式容器
set/multiset容器
set/multiset的简介
set是一个集合容器，其中所包含的元素是唯一的，集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
set采用红黑树变体的数据结构实现，红黑树属于平衡二叉树。在插入操作和删除操作上比vector快。
multiset与set的区别：set支持唯一键值，每个元素值只能出现一次；而multiset中同一值可以出现多次。
不可以直接修改set或multiset容器中的元素值，因为该类容器是自动排序的。如果希望修改一个元素值，必须先删除原有的元素，再插入新的元素。
set/multiset对象的默认构造
set();
set(const set& _Right);
explicit set(const key_compare& _Pred);
set(_Iter _First, _Iter _Last);
set(_Iter _First, _Iter _Last, const key_compare& _Pred);
set/multiset存取
pair<iterator, bool> insert(const value_type& _Val);
iterator insert(const value_type& _Val);
void insert(_Iter _First, _Iter _Last);
void insert(initializer_list<value_type> _Ilist);
iterator erase (const_iterator where); //返回下一个元素的位置
size_type erase (const value_type& val); //返回删除元素的个数，对于set来说，永远是1(set的值不能重复)
iterator erase (const_iterator first, const_iterator last); //区间删除
void swap(const &right); //交换set
void clear(); //清空所有元素
template <class... _Valtys>
pair<iterator, bool> emplace(_Valtys&&... _Vals);
//提示从whrere开始找，不是插入到where的位置，如果vals满足排在where指向的值的后面，那么将提高速度，否则无影响
template <class... _Valtys>
iterator emplace_hint(const_iterator _Where, _Valtys&&... _Vals)
set/multiset容量相关
bool empty();
size_t size();
size_t max_size();
set/multiset获取比较规则
//两个返回的都是一样的
key_compare key_comp（）const;
value_compare value_comp（）const;
set/multiset操作
iterator find(const key_type& _Keyval);//在容器中搜索与val等效的元素，如果找到则返回一个迭代器，否则返回end迭代器。
size_t count(const key_type& _Keyval); //在容器中搜索与val等效的元素，并返回匹配数。
//与排序规则有关
iterator lower_bound(const key_type& _Keyval);//找到第一个大于或者等于keyval的值
iterator upper_bound(const key_type& _Keyval);//找到第一个大于keyval的值
pair<iterator, iterator> equal_range(const key_type& _Keyval)
map\multimap容器
map/multimap的简介
-
map(映射)是关联容器，用于存储按特定顺序由键值和映射值的组合形成的元素，即(key,value)对。它提供基于key的快速检索能力。
-
map中key值是唯一的。集合中的元素按一定的顺序排列。元素插入过程是按排序规则插入，所以不能指定插入位置。
-
map的具体实现采用红黑树变体的平衡二叉树的数据结构。在插入操作和删除操作上比vector快。
-
map可以直接存取key所对应的value，支持[]操作符，如map[key]=value。
-
multimap与map的区别：map支持唯一键值，每个key只能出现一次；而multiset中同一key可以出现多次。map支持[]操作符，但是multmap不支持
map/multimap构造函数
map();
map(const map& _Right);
map(const key_compare& _Pred);
map(_Iter _First, _Iter _Last);
map(_Iter _First, _Iter _Last, const key_compare& _Pred);
map/multimap容量
bool empty();
size_t size();
size_t max_size();
map/multimap元素访问
mapped_type& operator[](key_type&& keyval); //根据key获取value
mapped_type& at(const key_type& _Keyval);
// 迭代器
map/multimap修改
insert
insert插入的是由键值对组成的pair<key_type,mapped_type>，可称为对组
key_type 键类型
mapped_type 值类型
value_type map装的元素内存，即pair<key_type,mapped_type>
pair<iterator,bool> insert (const value_type& val);
pair<iterator,bool> insert (value_type&& val);
假设 map<int, string> stu;
一、通过pair的方式插入对象
stu.insert(pair<int, string>(1, "maye"));
二、通过make_pair的方式插入对象
stu.insert(make_pair(2, "zoey"));
三、通过value_type的方式插入对象
stu.insert(map<int, string>::value_type(3, "lisa"));
四、通过数组的方式插入值
stu[3]= "取个名字好难";
stu[4] = "有人@我";
前三种方法，采用的是insert()方法，该方法返回值为pair<iter,bool>
iterator 指向插入的pair，bool标识是否插入成功
第四种方法非常直观，但存在一个性能的问题。
按key(3)插入元素时，若map中没有key(3),则键值对插入map，若key(3)已经存在，则修改key(3)对于的值。
string strName = stu[2]; //获取key对于的值
只有当stu存在2这个键时才是正确的取操作，否则会自动插入一个实例，键为2，值为初始化值。
earse
//删除key为keyval的元素，返回删除成功的数量
size_t erase(const key_type& _Keyval);
//删除[first,last)区间元素，返回last
iterator erase(const_iterator _First, const_iterator _Last);
//删除where指向的元素，返回下一个元素迭代器
iterator erase(const_iterator _Where);
clear
void clear(); //清空map
emplace
//就地构造，传
template <class... Args>
pair<iterator,bool> emplace (Args&&... args);
template <class... Args>
iterator emplace_hint (const_iterator position, Args&&... args);
//stu.emplace(12, "duck"); //key,mapped
map操作
//查找键key是否存在，若存在，返回该键的元素的迭代器；若不存在，返回map.end();
iterator find(const key_type& _Keyval);
//返回容器中key为keyval的pair个数，对于map要么是0，要么是1。对multimap来说，值可能大于1。
size_type count(const key_type& _Keyval);
iterator lower_bound(const key_type& _Keyval);
iterator upper_bound(const key_type& _Keyval);
//返回
pair<iterator, iterator> equal_range(const key_type& _Keyval);
unordered_set、unorder_map
这个是哈希映射，常用的就是insert、find、key、value操作等，这个主要用于快速查找。
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
29
0- 0
已为社区贡献11条内容
所有评论(0)