[ C++ ] STL---map与set的使用指南
目录
关联式容器
STL中的部分容器vector、list、deque、forward_list(C++11)等,这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身;
关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高;
键值对
键值对是表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key相对应的信息;
//键值对
template <class T1, class T2>
struct pair
{
T1 first;//key
T2 second;//value
//键值对构造函数
pair()
:first(T1())
, second(T2())
{}
//键值对拷贝构造函数
pair(const T1& a, const T2& b)
:first(a)
, second(b)
{}
};
set简介
- set是按照一定次序存储元素的容器并且set中的元素不可以重复;
- set中只存放value,但set底层实际存放由<value,value>所构成的键值对,元素的value也标识它(value即为key,类型为T),并且每个value必须是唯一的;set中的元素不能在容器中修改(元素总是const),但是可以从容器中插入或删除元素;
- 在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序;
- set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直接迭代;
- set在底层是用二叉搜索树(红黑树)实现的;
set官方文档:set - C++ Reference
set的常用接口
构造函数
//无参构造: set<Type> s1
set();
//迭代器区间构造[begin,end): set<Type> s2(s1.begin,s1.end)
template <class InputIterator>
set(InputIterator first, InputIterator last);
//拷贝构造: set<Type> s3(s1)
set(const set& x);
set的迭代器
set的容量
修改相关接口
find()函数
若在set容器中查找到值为val的元素,则返回val元素所在的位置;
若在set容器中查找不到值为val的元素,则返回set容器中最后一个元素的下一个位置;
insert()函数
pair<iterator,bool> insert (const value_type& val);
在set容器中插入元素val,若元素插入成功,返回<元素val在set中的位置,true>;
若插入元素失败,说明val已存在于set容器中,返回<元素val在set中的位置,false>;
iterator insert (iterator position, const value_type& val);
在set容器中的pos位置插入元素val,插入成功返回新插入元素val在set中的位置,插入失败返回已存在的元素val在set中的位置;一般配合find()函数使用;
int main()
{
set<int> s1;
s1.insert(5);
s1.insert(4);
s1.insert(3);
s1.insert(6);
s1.insert(7);
s1.insert(1);
s1.insert(5);
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
set<int>::iterator pos = s1.find(7);
s1.insert(pos, 8);// set容器中的pos位置插入元素8
set<int>::iterator it1 = s1.begin();
while (it1 != s1.end())
{
cout << *it1 << " ";
++it1;
}
cout << endl;
return 0;
}
运行结果:
由于set的底层结构为二叉搜索树,二叉搜索树不允许键值冗余,所以set中的元素不可以重复,因此可以使用set进行去重,由于set容器的迭代器遍历方式本质为搜索二叉树的中序遍历,因此使用set还可以进行"排序";
erase()函数
void erase (iterator position); //配合find()函数使用
//删除set容器中pos位置的元素
size_t erase (const value_type& val);
//删除set容器中值为val的元素,返回被删除元素的个数
//(由于set容器中的value唯一,若该元素存在,则返回1,否则返回0)
int main()
{
set<int> s1;
s1.insert(5);
s1.insert(4);
s1.insert(3);
s1.insert(6);
s1.insert(7);
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//erase()版本1
set<int>::iterator pos = s1.find(3);
if (pos != s1.end())
{
cout << "查找到元素val,删除val:" << endl;
s1.erase(pos);
}
for (auto& e : s1)
{
cout << e <<" ";
}
cout << endl;
//erase版本2
//删除的元素存在,返回1
size_t ret1 = s1.erase(5);
cout << "ret1=" << ret1 << endl;
//删除的元素不存在不做任何处理,返回0
size_t ret2 = s1.erase(30);
cout << "ret2=" << ret2 << endl;
return 0;
}
运行结果:
clear()函数
int main()
{
set<int> s1;
s1.insert(5);
s1.insert(4);
s1.insert(3);
s1.insert(6);
s1.insert(7);
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
cout << "size=" << s1.size() << endl;
cout << s1.empty() << endl;
s1.clear();
cout << "size=" << s1.size() << endl;
cout << s1.empty() << endl;
}
运行结果:
count函数
返回set容器中值为val的元素个数;
int main()
{
set<int> s1;
s1.insert(5);
s1.insert(4);
s1.insert(3);
s1.insert(6);
s1.insert(7);
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//使用count查找set容器中查找值为val的元素,返回值为val的元素个数
//(val在set容器中,返回1; val不在set容器中,返回0;)
if (s1.count(5))
{
cout << "在" << endl;
}
else
{
cout << "不在" << endl;
}
return 0;
}
运行结果:
lower_bound()函数
返回在set容器的迭代器区间范围[begin,end)中查找到的第一个 大于等于(>=val)的迭代器位置;
upper_bound()函数
返回在set容器的迭代器区间范围[begin,end)中查找到的第一个 大于(>val)的迭代器位置;
int main()
{
set<int> s1;
s1.insert(7);
s1.insert(3);
s1.insert(9);
s1.insert(1);
s1.insert(4);
s1.insert(6);
s1.insert(10);
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
// >= val
set<int>::iterator itlow = s1.lower_bound(2);
cout << *itlow << endl;
// > val
set<int>::iterator itup = s1.upper_bound(7);
cout << *itup << endl;
//遍历[itlow,itup)区间范围内的元素
while (itlow != itup)
{
cout << *itlow << " ";
++itlow;
}
cout << endl;
return 0;
}
运行结果:
multiset简介
multiset容器与set容器提供的成员函数接口相同,multiset与set容器的唯一区别是multiset允许键值冗余即multiset容器中存储的元素是可以重复的;
int main()
{
// 排序
multiset<int> s;
s.insert(5);
s.insert(1);
s.insert(6);
s.insert(3);
s.insert(4);
s.insert(1);
s.insert(1);
s.insert(5);
s.insert(2);
s.insert(10);
multiset<int>::iterator it = s.begin();
while (it != s.end())
{
cout << *it << " ";
++it;
}
cout << endl;
//multiset容器count函数返回值不再非1即0
cout << "cout1=" << s.count(1) << endl;
cout << "cout2=" << s.count(5) << endl;
//find()函数返回中序遍历multiset容器中第一个值为val元素的迭代器
it = s.find(5);
while (it != s.end() && *it == 5)
{
cout << *it << " ";
++it;
}
cout << endl;
return 0;
}
运行结果:
multiset官方文档:multiset - C++ Reference
map简介
- map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素;
- 在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容;键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair;
typedef pair<const key, T> value_type;
- map容器中元素的键值key不可被修改,但是元素的值value可以修改,因为map底层结构搜索二叉树是根据每个元素的键值key进行构建,而不是值value;
- 在内部,map中的元素总是按照键值key进行比较排序;
- map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列);
- map支持下标访问符,即在[]中放入key,就可以找到与key对应的value;
- map通常被实现为平衡二叉搜索树(红黑树);
map官方文档:map - C++ Reference
map的常用接口
构造函数
//无参构造: map<Type1,Type2> m1
map ();
//迭代器区间构造: map<Type1,Type2> m2(m1.begin(),m1.end())
template <class InputIterator>
map (InputIterator first, InputIterator last);
//拷贝构造函数: map<Type1,Type2> m3(m1);
map (const map& x);
map的迭代器
map的容量
修改相关接口
insert()函数
pair<iterator,bool> insert (const value_type& val);
在map容器中插入键值对val,若元素val插入成功,返回<元素val在map中的位置,true>;
若插入元素val失败,说明val已存在于map容器中,返回<元素val在map中的位置,false>;
iterator insert (iterator position, const value_type& val);
在map容器中的pos位置插入键值对val,插入成功返回新插入元素val在map中的位置,插入失败返回已存在的元素val在map中的位置;一般配合find()函数使用;
由于map容器中的元素类型value_type为pair,所以插入元素val时需要构造出一个pair,存在四种方式构造pair : 有名对象 、匿名对象、make_pair 、 { }构造(c++11);
1. 有名对象构造pair
int main()
{
map<string, string> dict;
pair<string, string> kv("courage", "勇气");
dict.insert(kv);
return 0;
}
2. 匿名对象构造pair
int main()
{
map<string, string> dict;
dict.insert(pair<string, string>("insistence", "坚持"));
return 0;
}
3. make_pair()函数构造pair
//pair<key,value> pair中的第一个元素key被设置为x,pair中的第二个元素value被设置为y
template <class T1,class T2>
pair<T1,T2> make_pair (T1 x, T2 y)
{
return ( pair<T1,T2>(x,y) );
}
int main()
{
map<string, string> dict;
dict.insert(make_pair("endeavor", "努力"));
return 0;
}
4.{ }构造
int main()
{
map<string, string> dict;
//原因:c++11支持多参数隐式类型转换(构造函数)
dict.insert({ "integrity", "正直" });
return 0;
}
示例:
int main()
{
map<string, string> dict;
dict.insert(make_pair("learn", "学习"));
dict.insert(make_pair("courage", "勇气"));
dict.insert(make_pair("insistence", "坚持"));
dict.insert(make_pair("integrity", "正直"));
dict.insert(make_pair("endeavor", "努力"));
dict.insert(make_pair("learn", "推断"));
// 迭代器遍历
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
//cout << *it << endl;(×)(it为结构体指针,*it为pair)
// 访问方式一(√)
//cout << (*it).first << ":" << (*it).second << endl;
//访问方式二(√)
cout << it->first << ":" << it->second << endl;
++it;
}
return 0;
}
运行结果:
注:键值对pair<string,string> kv1("learn","学习")与键值对pair<string,string> kv2("learn","推断")两者key相同,value不同,不会插入也不会更新;
元素访问operator[ ]
operator[]通过键值k来访问map容器中对应的值value;
如果键值k不存在,则会自动插入一个新的键值对,其中键值为k,value值为默认构造的值;
如果键值k已经存在,则会返回与该键相关联的value值;
//operator[]等价形式如下:
(*((this->insert(make_pair(k,mapped_type()))).first)).second
首先this指针调用insert()函数即this->insert(make_pair(k,mapped_type())),插入的键值对中的键值key为k,value值为mapped_type类型的默认构造函数,而insert()函数的返回值为结构体pair<iterator, bool>,结构体pair中的第一个元素为迭代器(迭代器本质为指针或者封装过的指针),当取到迭代器位置first对其解引用便可获得map容器中的与k相对应的value值;
//模拟重载如下:
value& operator[](const key& k)
{
pair<iterator, bool> ret = insert(make_pair(k, value()));
return *(ret.first).second
}
示例
int main()
{
map<string, string> dict;
dict.insert(make_pair("learn", "学习"));
dict.insert(make_pair("courage", "勇气"));
dict.insert(make_pair("insistence", "坚持"));
dict.insert(make_pair("integrity", "正直"));
dict.insert(make_pair("endeavor", "努力"));
dict.insert(make_pair("learn", "推断"));
map<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << (*it).first << ":" << (*it).second << endl;
++it;
}
cout << endl;
//[]功能一: 插入
dict["sort"];
//[]功能二: 查找
cout << dict["insistence"] << endl;
//[]功能三: 修改
dict["learn"] = "推断";
//[]功能四: 插入+修改
dict["charming"] = "迷人的";
for (auto& kv : dict)//范围for遍历时加上引用,减少拷贝,提升效率
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
return 0;
}
运行结果:
multimap简介
multismap容器与map容器提供的成员函数接口相同,multimap与map容器的唯一区别是multimap允许键值冗余即multimap容器中存储的键值对中的key是可以重复的;
注意:由于multimap容器中键值对pair中的key可以重复,若在key值相同但与之对应的value值不同的情形下,返回的值value会产生歧义,所以multiset容器中没有重载operator[ ];
int main()
{
multimap<string, string> dict;
dict.insert(make_pair("learn", "学习"));
dict.insert(make_pair("courage", "勇气"));
dict.insert(make_pair("insistence", "坚持"));
dict.insert(make_pair("integrity", "正直"));
dict.insert(make_pair("endeavor", "努力"));
dict.insert(make_pair("learn", "推断"));
// 迭代器遍历
multimap<string, string>::iterator it = dict.begin();
while (it != dict.end())
{
cout << it->first << ":" << it->second << endl;
++it;
}
return 0;
}
运行结果:
欢迎大家批评指正,博主会持续输出优质内容,谢谢各位观众老爷观看,码字画图不易,希望大家给个一键三连支持~ 你的支持是我创作的不竭动力~
原文地址:https://blog.csdn.net/m0_58963318/article/details/137537201
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!