C++常用数据结构使用总结
-
六、queue(基于deque)[不支持迭代器]
只能访问 queue<T> 容器适配器的第一个和最后一个元素。只能在容器的末尾添加新元素,只能从头部移除元素
对于任何需要用 FIFO 准则处理的序列来说,使用 queue 容器适配器都是好的选择
1、初始化
#include <queue> queue<T>(); //一个空的队列 queue<T>(queue<T> q); //复制
2、增:
push(T value); //尾部加入元素
3、删:
pop(); //删除第一个元素
4、查:
front(); //返回第一个元素 back(); //返回最后的元素
5、改:
swap(queue<T>); //交换两个同类型向量的数据
6、其他方法:
empty(); //是否为空 size(); //返回元素个数
-
七、priority_queue(基于vector)[不支持迭代器]
priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。因为它是一个队列,所以只能访问第一个元素,这也意味着优先级最高的元素总是第一个被处理。但是如何定义“优先级”完全取决于我们自己。
1、初始化
#include <queue> priority_queue<T, Container, Functional>(); //T 就是数据类型,Container 就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用 list。STL里面默认用的是vector),Functional 就是比较的方式。 priority_queue<T, Container, Functional>(priority_queue<T, Container, Functional> pq);//复制 //升序队列,小顶堆 priority_queue <T,vector<T>,greater<T>> q; //降序队列,大顶堆 priority_queue <T,vector<T>,less<T>> q; //greater和less是std实现的两个仿函数(就是使一个类的使用看上去像一个函数。其实现就是类中实现一个operator(),这个类就有了类似函数的行为,就是一个仿函数类了)需要#include <functional>
2、增:
push(T value); //加入元素(并排序)
3、删:
pop(); //删除第一个元素
4、查:
top(); //返回第一个元素
5、改:
swap(priority_queue<T>); //交换两个同类型向量的数据
6、其他方法:
empty(); //是否为空 size(); //返回元素个数
-
八、map(基于红黑树)[双向迭代器]
map是STL的一个关联容器,它提供一对一的hash。第一个可以称为关键字(key),每个关键字只能在map中出现一次;第二个可能称为该关键字的值(value);
map內部的实现自建一颗红黑树,这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的
1、初始化
#include <map> map<T1,T2>(); //一个空的map map<T1, T2>(m.begin(),m.end()); //复制另一个map map<T1, T2> m = { {T1 value1, T2 value2},{T1 value1, T2 value2},...,}//直接初始化
2、增:
//使用pair插入 注意map中有这个关键字时,insert操作是不能在插入数据的 insert(make_pair<T1, T2>(T1 value1,T2 value2); insert(pair<T1, T2>(T1 value1,T2 value2); //使用value_type插入 注意map中有这个关键字时,insert操作是不能在插入数据的 insert(map<T1, T2>::value_type (T1 value1, T2 value2)); //用"array"方式插入,可以直接覆盖 m[T1 value1] = T2 value2;
3、删:
erase(T1 value); //如果刪除了會返回1,否則返回0 clear(); //清空 //迭代器 map<T1,T2>::iterator it; iterator erase(iterator it):删除向量中迭代器指向元素 iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
4、查:
find(key) != m.end(); //根据value查找值,如果找不到会返回l.end()的值 at(T1 value1); //返回的是参数键对应的对象。如果这个键不存在,就会拋出 out_of_range 异常 //遍历 for (auto &i : v){i.first;i.second} //迭代器 map<T1,T2>::iterator it; it->first; //访问key it->second; //访问value ++it; //双向迭代器特点 iterator begin(); //返回向量头指针,指向第一个元素 iterator end(); //返回向量尾指针,指向向量最后一个元素的下一个位置 //遍历 for (map<T1,T2>::iterator it = m.begin(); it != m.end(); ++it) {key = it->first;value = it->second;} //反向遍历 for (map<T1,T2>::reverse_iterator j = m.rbegin(); j != m.rend(); ++j) {key = it->first;value = it->second;}
5、改:
swap(map<T1,T2>) //交换两个同类型向量的数据 //使用array方式直接修改 m[T1 value1] = T2 value2; //迭代器 map<T1,T2>::iterator it; it->second = T2 alue;
6、其他方法:
empty(); //是否为空 count(T1 value1); //返回指定元素出现的次数 size(); //返回元素个数 max_size(); //返回最大可允许的map元素数量值(256204778801521550)
-
九、multimap(基于红黑树)[双向迭代器]
multimap容器:与map容器类似,区别只在于multimap容器可以保存键值相同的元素。
1、初始化
#include <map> multimap<T1,T2>(); //一个空的multimap multimap<T1, T2>(m.begin(),m.end()); //复制另一个multimap multimap<T1, T2> m = { {T1 value1, T2 value2},{T1 value1, T2 value2},...,}//直接初始化
2、增:
//multimap 容器的成员函数 insert() 可以插入一个或多个元素,而且插入总是成功。 //使用pair插入 insert(make_pair<T1, T2>(T1 value1,T2 value2); insert(pair<T1, T2>(T1 value1,T2 value2); //使用value_type插入 insert(multimap<T1, T2>::value_type (T1 value1, T2 value2));
3、删:
erase(T1 value); //如果刪除了會返回1,否則返回0 clear(); //清空 //迭代器 multimap<T1,T2>::iterator it; iterator erase(iterator it):删除向量中迭代器指向元素 iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
4、查:
find(key) != m.end(); //根据value查找值,如果找不到会返回l.end()的值 //遍历 for (auto &i : v){i.first;i.second} //迭代器 multimap<T1,T2>::iterator it; it->first; //访问key it->second; //访问value ++it; //双向迭代器特点 iterator begin(); //返回向量头指针,指向第一个元素 iterator end(); //返回向量尾指针,指向向量最后一个元素的下一个位置 //遍历 for (multimap<T1,T2>::iterator it = m.begin(); it != m.end(); ++it) {key = it->first;value = it->second;} //反向遍历 for (multimap<T1,T2>::reverse_iterator j = m.rbegin(); j != m.rend(); ++j) {key = it->first;value = it->second;}
5、改:
swap(map<T1,T2>) //交换两个同类型向量的数据 //迭代器 multimap<T1,T2>::iterator it; it->second = T2 alue;
6、其他方法:
empty(); //是否为空 count(T1 value1); //返回指定元素出现的次数 size(); //返回元素个数 max_size(); //返回最大可允许的map元素数量值(256204778801521550)
-
十、unordered_map(基于hash表)[正向迭代器]
unordered_map 包含的是有唯一键的键/值对元素。容器中的元素不是有序的。元素的位置由键的哈希值确定,因而必须有一个适用于键类型的哈希函数。如果用类对象作为键,需要为它定义一个实现了哈希函数的函数对象。如果键是STL 提供的类型,通过特例化 hash<T>,容器可以生成这种键对应的哈希函数
1、初始化
#include <unordered_map > unordered_map <T1,T2>(); //一个空的map unordered_map <T1, T2>(m.begin(),m.end()); //复制另一个map unordered_map <T1, T2> m = { {T1 value1, T2 value2},{T1 value1, T2 value2},...,}//直接初始化
2、增:
//使用pair插入 注意map中有这个关键字时,insert操作是不能在插入数据的 insert(make_pair<T1, T2>(T1 value1,T2 value2); insert(pair<T1, T2>(T1 value1,T2 value2); //使用value_type插入 注意map中有这个关键字时,insert操作是不能在插入数据的 insert(unordered_map<T1, T2>::value_type (T1 value1, T2 value2)); //用"array"方式插入,可以直接覆盖 m[T1 value1] = T2 value2;
3、删:
erase(T1 value); //如果刪除了會返回1,否則返回0 clear(); //清空 //迭代器 unordered_map<T1,T2>::iterator it; iterator erase(iterator it):删除向量中迭代器指向元素 iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
4、查:
find(key) != m.end(); //根据value查找值,如果找不到会返回l.end()的值 at(T1 value1); //返回的是参数键对应的对象。如果这个键不存在,就会拋出 out_of_range 异常 //遍历 for (auto &i : v){i.first;i.second} //迭代器 unordered_map<T1,T2>::iterator it; it->first; //访问key it->second; //访问value ++it; //双向迭代器特点 iterator begin(); //返回向量头指针,指向第一个元素 iterator end(); //返回向量尾指针,指向向量最后一个元素的下一个位置 //遍历 for (unordered_map<T1,T2>::iterator it = m.begin(); it != m.end(); ++it) {key = it->first;value = it->second;}
5、改:
swap(unordered_map<T1,T2>) //交换两个同类型向量的数据 //使用array方式直接修改 m[T1 value1] = T2 value2; //迭代器 unordered_map<T1,T2>::iterator it; it->second = T2 alue;
6、其他方法:
empty(); //是否为空 count(T1 value1); //返回指定元素出现的次数 size(); //返回元素个数 max_size(); //返回最大可允许的map元素数量值(256204778801521550)
-
十一、set(基于红黑树)[双向迭代器]
set为集合。除了没有单独的键,set 容器和 map 容器很相似。
1、初始化
#include <set> set<T>(); //一个空的map set<T>(s.begin(),s.end()); //复制另一个map set<T> s = { T value,T value,...,}//直接初始化
2、增:
//无法重复插入 insert(T value); //插入元素 emplace(T value); //插入元素,会返回一个 pair<iterator,bool> 对象
3、删:
erase(T value); //如果刪除了會返回1,否則返回0 clear(); //清空 //迭代器 set<T>::iterator it; iterator erase(iterator it):删除向量中迭代器指向元素 iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
4、查:
find(key) != s.end(); //根据value查找值,如果找不到会返回l.end()的值 //遍历 for (auto &i : s){i} //迭代器 set<T>::iterator it; *it //直接访问迭代器指向的元素 ++it; //双向迭代器特点 iterator begin(); //返回向量头指针,指向第一个元素 iterator end(); //返回向量尾指针,指向向量最后一个元素的下一个位置 //遍历 for (set<T>::iterator it = s.begin(); it != s.end(); ++it) {temp = *it;} //反向遍历 for (set<T>::reverse_iterator j = s.rbegin(); j != s.rend(); ++j) {temp = *it;}
5、改:
swap(set<T>) //交换两个同类型向量的数据
6、其他方法:
empty(); //是否为空 count(T value); //返回指定元素出现的次数 size(); //返回元素个数 max_size(); //返回最大可允许的set元素数量值
-
十二、multiset(基于红黑树)[双向迭代器]
multiset容器:与set容器类似,区别只在于multiset容器可以保存相同的元素。
1、初始化
#include <set> multiset<T>(); //一个空的map multiset<T>(s.begin(),s.end()); //复制另一个map multiset<T> s = { T value,T value,...,}//直接初始化
2、增:
//总是能够成功 insert(T value); //插入元素 emplace(T value); //插入元素,会返回一个 pair<iterator,bool> 对象
3、删:
erase(T value); //如果刪除了會返回1,否則返回0 clear(); //清空 //迭代器 multiset<T>::iterator it; iterator erase(iterator it):删除向量中迭代器指向元素 iterator erase(iterator first,iterator last):删除向量中[first,last)中元素
4、查:
find(key) != s.end(); //根据value查找值,如果找不到会返回l.end()的值 //遍历 for (auto &i : s){i} //迭代器 set<T>::iterator it; *it //直接访问迭代器指向的元素 ++it; //双向迭代器特点 iterator begin(); //返回向量头指针,指向第一个元素 iterator end(); //返回向量尾指针,指向向量最后一个元素的下一个位置 //遍历 for (multiset<T>::iterator it = s.begin(); it != s.end(); ++it) {temp = *it;} //反向遍历 for (multiset<T>::reverse_iterator j = s.rbegin(); j != s.rend(); ++j) {temp = *it;}
5、改:
swap(multiset<T>) //交换两个同类型向量的数据
6、其他方法:
empty(); //是否为空 count(T value); //返回指定元素出现的次数 size(); //返回元素个数 max_size(); //返回最大可允许的multiset元素数量值
-
十三、unordered_set(基于hash表)[正向迭代器]
占位
(其实可以直接参考unordered_map和set的方法直接用)
-
十四、string
占位
有点懒得整理了:http://c.biancheng.net/view/400.html
-
参考资料
大多数都从这里整理的:C++笔记 http://c.biancheng.net/skill/cpp/
等什么时候想起来再把后两个补了(摸了)
-
(为什么会有人把目录放最后
一、迭代器(针对容器的一种指针)
二、VECTOR(简单数组)[随机访问迭代器]
三、DEQUE(分段数组)[随机访问迭代器]
四、LIST(双向链表)[双向迭代器]
五、STACK(基于DEQUE)[不支持迭代器]
六、QUEUE(基于DEQUE)[不支持迭代器]
七、PRIORITY_QUEUE(基于VECTOR)[不支持迭代器]
八、MAP(基于红黑树)[双向迭代器]
九、MULTIMAP(基于红黑树)[双向迭代器]
十、UNORDERED_MAP(基于HASH表)[正向迭代器]
十一、SET(基于红黑树)[双向迭代器]
十二、MULTISET(基于红黑树)[双向迭代器]
十三、UNORDERED_SET(基于HASH表)[正向迭代器]
十四、STRING