目录
关联式容器
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;
}运行结果：
欢迎大家批评指正，博主会持续输出优质内容，谢谢各位观众老爷观看，码字画图不易，希望大家给个一键三连支持~ 你的支持是我创作的不竭动力~
