5. C++常用数据结构使用总结

C++常用数据结构使用总结


  • 七、priority_queue(基于vector)[不支持迭代器]

    ​ priority_queue 容器适配器定义了一个元素有序排列的队列。默认队列头部的元素优先级最高。因为它是一个队列，所以只能访问第一个元素，这也意味着优先级最高的元素总是第一个被处理。但是如何定义“优先级”完全取决于我们自己。

    0_1603444949156_1601954661299.png

    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();		//返回元素个数
    回复 引用 0

  • 八、map(基于红黑树)[双向迭代器]

    ​ map是STL的一个关联容器，它提供一对一的hash。第一个可以称为关键字(key)，每个关键字只能在map中出现一次；第二个可能称为该关键字的值(value)；

    ​ map內部的实现自建一颗红黑树，这颗树具有对数据自动排序的功能。在map内部所有的数据都是有序的

    0_1603445030002_1602139094180.png

    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)
    回复 引用 0

  • 九、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)
    回复 引用 0

  • 十、unordered_map(基于hash表)[正向迭代器]

    unordered_map 包含的是有唯一键的键/值对元素。容器中的元素不是有序的。元素的位置由键的哈希值确定，因而必须有一个适用于键类型的哈希函数。如果用类对象作为键，需要为它定义一个实现了哈希函数的函数对象。如果键是STL 提供的类型，通过特例化 hash<T>，容器可以生成这种键对应的哈希函数

    0_1603445089099_1602145825896.png

    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)

    回复 引用 0

  • 十一、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元素数量值
    回复 引用 0

  • 十二、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元素数量值
    回复 引用 0

  • 十三、unordered_set(基于hash表)[正向迭代器]

    占位
    （其实可以直接参考unordered_map和set的方法直接用）

    回复 引用 0

  • 十四、string

    占位
    有点懒得整理了：http://c.biancheng.net/view/400.html

    回复 引用 0

  • 参考资料

    大多数都从这里整理的：C++笔记 http://c.biancheng.net/skill/cpp/
    等什么时候想起来再把后两个补了（摸了）

    回复 引用 0

  • （为什么会有人把目录放最后

    一、迭代器（针对容器的一种指针）

    二、VECTOR（简单数组）[随机访问迭代器]

    三、DEQUE（分段数组）[随机访问迭代器]

    四、LIST（双向链表）[双向迭代器]

    五、STACK(基于DEQUE)[不支持迭代器]

    六、QUEUE(基于DEQUE)[不支持迭代器]

    七、PRIORITY_QUEUE(基于VECTOR)[不支持迭代器]

    八、MAP(基于红黑树)[双向迭代器]

    九、MULTIMAP(基于红黑树)[双向迭代器]

    十、UNORDERED_MAP(基于HASH表)[正向迭代器]

    十一、SET(基于红黑树)[双向迭代器]

    十二、MULTISET(基于红黑树)[双向迭代器]

    十三、UNORDERED_SET(基于HASH表)[正向迭代器]

    十四、STRING

    回复 引用 0
回复
 

Copyright © 2018 bbs.dian.org.cn All rights reserved.

与 Dian 的连接断开，我们正在尝试重连，请耐心等待