C++|树形关联式容器(set、map、multiset、multimap)介绍使用

目录

一、关联式容器介绍

1.1概念

1.2键值对

1.3树形结构的关联式容器

 1.3.1pair模板介绍 

1.3.2make_pair的介绍 

二、set的介绍和使用

2.1set介绍

2.2set使用

 2.2.1构造 

2.2.2容量

2.2.3修改

三、map的介绍和使用 

 3.1map介绍

 3.2map使用

 3.2.1构造

3.2.2容量

3.2.3修改

四、multiset和multimap简单介绍使用

---

一、关联式容器介绍

1.1概念

我们之前学过的STL中的部分容器，比如：string、vector、list、deque等。这些都是序列式容器，他们都是线性序列的数据结构，里面存储的是元素本身。

关联式容器：也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key,value>结构的键值对，在数据检索时比序列式容器效率更高

1.2键值对

在搜索二叉树中的kv模型已经介绍过了键值对了，它是用来表示具有一一对应关系的结构，该结构中包含两个成员变量，key和value，key代表键值，value表示与key对应的信息。比如：建立英汉词典互译、统计value出现的次数 

1.3树形结构的关联式容器

 为了更好的管理数据，STL设计了两种不同结构的管理式容器：树形结构与哈希结构。树形结构的关联式容器主要有四种：map、set、multimap、multiset。他们的底层采用都是平衡搜索树(即红黑树)来实现，容器中的元素是有序的序列。那么接下来在学习他们的用法前，先介绍一下pair，以方便后续理解set，map使用。在下一章节，将会模拟实现他们。

 1.3.1pair模板介绍 

pair有两个模板参数，pair类中有两个元素first，second，分别为T1，T2类型。其中T1被typedef成first_type,T2被typedef成second_type。其中，元素first，second可以修改。对于set，虽然其key值不存在pair当中，但有接口的返回值类型是pair类型。对于map，其值key和value存放在pair中。

函数声明	功能介绍
pair();	构造空pair
template<class U, class V> pair (const pair<U,V>& pr);	拷贝构造
pair (const first_type& a, const second_type& b);	分别用两个值初始化pair，即分别初始化pair中的first和second元素
pair& operator= (const pair& pr);	通过对象进行赋值

例子： 

#include <iostream>
using namespace std;int main()
{pair<int, int> p(1, 2);//初始化paircout << p.first << " " << p.second << endl;pair<int, int> pp(p);//拷贝构造pp.first = 3;pp.second = 4;cout << pp.first << " " << pp.second << endl;pair<int, int> ret = pp;//赋值ret.first = 5;ret.second = 6;cout << ret.first << " " << ret.second << endl;return 0;
}

输出结果： 

 

1.3.2make_pair的介绍 

make_pair其实就是一个pair对象。其实现如下 

根据其实现，pair<T1,T2>(x,y) 构造了一个默认pair对象并返回，也就是说，make_pair(T1 x, T2 y) == pair<T1,T2>(x,y) 。所以make_pair即一个pair对象，采用make_pair的好处就是简短了一点。

例如：

#include <iostream>
using namespace std;int main()
{pair<int, int> p(make_pair<int,int>(1,2));//make_pair即一个pair对象，将该对象拷贝给pcout << p.first << " " << p.second << endl;return 0;
}

 输出结果：

go on~ 

二、set的介绍和使用

2.1set介绍

1.set是按照一定次序存储元素的容器，C++中是按中序遍历的。

2.在set中，元素key与value是一一对应的，且是唯一的。set中的key不能在容器中修改(元素总是const)，但是可以插入和删除。因为修改元素，就破坏了树的结构。

3.在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。元素的相对顺序是严格确定的。

4.set容器通过key访问单个元素的速度通常比unordered_set(哈希实现)容器慢，但他们允许根据顺序对子集直接迭代。

5.set在底层是用红黑树实现的。

注意：

1.与map/multimap不同，map/multimap中存储的是真正的键值对<key,value>,set中只放value,但在底层实际存放的是由<value,value>构成的键值对。

2.set实际使用不需要构造键值对，只需传value参数即可。

3.set中的元素不可以重复,所以在插入相同的元素时，set会进行去重

4.使用set的迭代器遍历元素，得到的是有序序列，因为set底层是以中序的方式遍历

5.set中的元素默认按照小于来比较

6.set中查找某个元素，时间复杂度为：log N

7.红黑树依然是搜索二叉树，只不过其实现二叉搜索树的方式不同，优化了最初的二叉搜索树的缺点。 

set的第一个参数，存放元素的类型，第二个参数表示set元素默认按照小于来比较，第三个参数表示元素空间的管理方式，这个先不做了解，不影响我们的使用模拟实现。

2.2set使用

 2.2.1构造 

函数声明	功能介绍
explicit set (const key_compare&comp=key_compare(),const allocator_type& alloc = allocator_type());	构造空set
template <class InputIterator>set (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());	用[first,last)区间中的元素构造set
set (const set& x);	拷贝构造

例子： 

#include <iostream>
#include <set>
using namespace std;int main()
{int arr[] = { 2,34,6,6,56,8,321,9,4,88 };set<int> s(arr, arr + sizeof(arr)/sizeof(arr[0]));//迭代器区间构造for (auto e : s){cout << e << " ";}cout << endl;set<int> s1(s);//拷贝构造for (auto e : s1){cout << e << " ";}cout << endl;return 0;
}

输出结果： 

 

2.2.2容量

函数声明	功能介绍
bool empty() const;	检测set是否为空，空返回true，否则返回false
size_type size() const;	返回set中有效元素的个数
size_type max_size() const;	返回set能够存储的最大容量

例子： 

#include <iostream>
#include <set>
using namespace std;int main()
{int arr[] = { 2,34,6,6,56,8,321,9,4,88 };set<int> s(arr, arr + sizeof(arr) / sizeof(arr[0]));//迭代器区间构造for (auto e : s){cout << e << " ";}cout << endl;cout << boolalpha << s.empty() << endl;//bool值形式打印cout << s.size() << endl;cout << s.max_size() << endl;return 0;
}

输出结果： 

 

2.2.3修改

函数声明	功能介绍
pair<iterator,bool> insert(const value_type& x)	在set中插入元素x，实际插入的是<x,x>构成的键值对，如果插入成功，返回<该元素在set中的位置，true>,失败，说明x在set中已经存在，返回<x在set中的位置，false>
void erase(iterator position)	删除迭代器所指向position位置上的元素
size_type erase(const key_type& x)	删除set中值为x的元素，返回删除的元素的个数
void erase(iterator first,iterator last)	删除迭代器区间[first,last)中的元素
void swap(set& st)	交换两个set中的元素
void clear()	将set中的元素清空
iterator find(const key_type& x) const	返回set中值为x的元素的位置，未找到，返回end()
size_type count(const key_type& x) const	返回set中值为x的元素个数，因为set会去重，所以要么返回1，要么返回0

 其中key_type 代表第一个模板参数类型，即T

例子： 

#include <iostream>
#include <set>
using namespace std;int main()
{int arr[] = { 2,34,6,6,8,9,4};set<int> s(arr, arr + sizeof(arr) / sizeof(arr[0]));//迭代器区间构造set<int>::iterator it = s.begin();while(it != s.end()){cout << *it << " ";it++;}cout << endl;it= s.find(6);//返回元素的当前位置cout << *it << endl;cout << s.count(6) << endl;size_t num = s.erase(6);cout << num << endl;s.erase(s.begin());//删除迭代器当前位置元素it = s.begin();while (it != s.end()){cout << *it << " ";it++;}cout << endl;s.erase(s.begin(), s.end());//删除迭代器区间中的元素return 0;
}

输出结果： 

三、map的介绍和使用 

 3.1map介绍

 

1.map是关联式容器，存储由键值key和value组合的元素。key和value的组合元素跟set一样依然是按照key来进行比较排序。

2.在map中，key和value是一一对应的，即使类型不同。由于他们绑定在一起，并为他们取名为pair<key,value>，所以对于map而言Key和value元素存放在pair<const key, T>类模板当中。其typedef pair<const key, T> value_type;

3.map中通过键值访问单个元素的速度通常比unordered_map(哈希实现，遍历顺序是无序的)容器慢，但map遍历顺序是有序的。

4.map支持下标访问，通过key访问，即在[]中放入key,就可以找到key对应的value。

5.map由红黑树实现。

第一个参数表示key的类型，第二个参数表示value的类型。第三个参数表示map中的元素默认是按key来比较，且按小于来比。第四个参数表示空间配置器。

 3.2map使用

 3.2.1构造

函数声明	功能介绍
explicit map (const key_compare&comp=key_compare(),const allocator_type& alloc = allocator_type());	构造空map
template <class InputIterator>map (InputIterator first, InputIterator last,const key_compare& comp = key_compare(),const allocator_type& alloc = allocator_type());	用[first,last)区间中的元素构造map
map (const map& x);	拷贝构造
map& operator= (const map& x); map& operator= (initializer_list<value_type> il);	通过对象进行初始化。 通过初始化列表进行初始化，C++11的用法

例子： 

#include <iostream>
#include <map>
using namespace std;int main()
{map<string, string> mp = { {"apple","苹果"}, {"banana","香蕉"}, {"orange","橙子"} };//初始化列表进行初始化，每个元素都是pair类型for (auto& e : mp)//访问map元素，实则就是pair中的元素{cout << e.first << ":" << e.second << endl;}cout << endl;map<string, string> mmp(mp.begin(), mp.end());//迭代器区间构造map<string, string>::iterator it = mmp.begin();while (it != mmp.end()){cout << it->first << ":" << it->second << endl;it++;}cout << endl;map<string, string> pm(mmp);//拷贝构造for (auto& e : pm){cout << e.first << ":" << e.second << endl;}return 0;
}

 输出结果：

3.2.2容量

函数声明	功能简介
bool empty() const;	检测map中元素是否为空，是,返回true，否，返回false
size_type size() const;	返回map中有效元素的个数
mapped_type& operator[] (const key_type& k);	返回key对应的value。(支持插入，修改。若key不存在，则插入value，并返回。若存在，修改value,并返回)
mapped_type& at (const key_type& k);const mapped_type& at (const key_type& k) const;	返回key对应的value。(支持修改，不支持插入。若key不存在，抛异常。若存在，修改value，并返回)

 其中，mapped_type类型是第二个模板参数的类型，即T。

例子： 

#include <iostream>
#include <map>
using namespace std;int main()
{map<string, int> mp = { {"one",1},{"two",2},{"three",3},{"four",4} };cout << boolalpha << mp.empty() << endl;cout << mp.size() << endl;cout << "mp[one]:" << mp["one"] << endl;//返回对应的valuecout << "mp[two]:" << mp["two"] << endl;cout << "mp[three]:" << mp["three"] << endl;cout << "mp[four]:" << mp["four"] << endl << endl;mp["one"] = 5;//修改valuemp["two"] = 6;mp["three"] = 7;mp["four"] = 8;mp["nine"] = 9;//mp对象中没有<nine,9>。则表示新建key,插入9mp["ten"] = 10;cout << "mp[one]:" << mp["one"] << endl;//返回对应的valuecout << "mp[two]:" << mp["two"] << endl;cout << "mp[three]:" << mp["three"] << endl;cout << "mp[four]:" << mp["four"] << endl;cout << "mp[nine]:" << mp["nine"] << endl;cout << "mp[ten]:" << mp["ten"] << endl;return 0;
}

输出结果： 

 

3.2.3修改

函数声明	功能介绍
pair<iterator,bool> insert(const value_type& x)	在map中插入键值对x，注意x是一个键值对，即pair类型，返回值也是键值对：iterator代表新插入元素的位置，bool代表插入成功
void erase(iterator position) size_type erase(const key_type& x) void erase(iterator first,iterator last)	删除position位置上的元素 删除键值为x的元素 删除[first,last)区间中的元素
void swap(map<Key,T,Compare,Allocator>& mp)	交换两个map中的元素
void clear()	将map中的元素清空
iterator find(const key_type& x) const_iterator find(const key_type& x) const	在map中插入key为x的元素，找到返回该元素的位置的迭代器，否则返回end() 在map中插入key为x的元素，找到返回该元素的位置的const迭代器，否则返回end()
size_type count(const key_type& x)	返回key为x的键值在map中的个数，注意map汇总key是唯一的，因此该函数的返回值要么为0，要么为1，因此也可以用该函数来检测一个key是否在map中

对于operator[]重载实现，实则是按如下：

 

由于该长代码不好理解，将上述进行拆写，那么该重载的实现，可以按以下方式：

	mapped_type& operator[](const k& key){//插入成功，iterator指向的就是插入成功的位置，该位置类型为pair类型。插入失败，说明已经存在，iterator指向的就是已经存在的位置。pair<iterator, bool> p = this->insert(make_pair(k,mapped()));//p.first就是迭代器对象，指向<k,value>所在位置，p.first->second就是valuereturn p.first->second;}

接下来，就对修改的操作进行演示：

#include <iostream>
#include <map>
using namespace std;int main()
{map<string, string> mp;mp.insert(pair<string, string>("insert", "插入"));//将<"insert","插入">插入map中，用pair构造键值对//mp.insert(make_pair("insert","插入"));//通过make_pair构造键值对mp.insert(make_pair("fruit", "水果"));pair<map<string,string>::iterator, bool> p = mp.insert(make_pair("fruit", "水果"));//已经存在<"fruit","水果">,返回falsecout << boolalpha << p.second << endl;//通过operator[]向map中插入元素mp["apple"] = "苹果";//mp.at("peach") = "桃子";//"peach"不存在会抛异常，不会插入map<string, string> m;m.swap(mp);cout << boolalpha << mp.empty() << endl;m.erase("apple");map<string, string>::iterator it = m.find("apple");if (it != m.end()){cout << "苹果存在" << endl;}else{cout << "苹果不存在" << endl;}cout << m.count("peach") << endl;return 0;
}

 输出结果：

 总结一下map：

1.map中的元素是键值对，由pair管理。

2.map中的key是唯一的。

3.默认按照小于的方式对key进行比较

4.map中的元素是按中序的方式打印的，即有序的。

5.[]操作符，可插入，可修改。

四、multiset和multimap简单介绍使用

multiset和multimap跟set和map的使用一样。唯一功能不一样的是，multiset和multimap中的key不去重，正因为有了不去重的功能，所以对于他们就没必要提供operator[]，因为该接口是先判断是否已经存在key,是，则返回key对应的value,可以进行对value修改，而不是继续插入key，否，则是新插入key，这就达到了去重的概念。所以他们不提供该接口，而对于其他接口的用法和set、map是类似的。

multiset: 

#include <iostream>
#include <set>
using namespace std;int main()
{string arr[] = { "apple","apple","banana","apple","orange","grape","peach" };multiset<string> s(arr, arr + sizeof(arr)/sizeof(arr[0]));//不去重for (auto& e : s){cout << e << endl;}return 0;
}

输出结果： 

 

multimap:

#include <iostream>
#include <map>
using namespace std;int main()
{multimap<string, string> mlp = { {"apple","苹果"},{"apple","苹果"},{"orange","橙子"},{"peach","桃子"},{"grape","葡萄"},{"apple","苹果"},{"banana","香蕉"} };for (auto& e : mlp){cout << e.first << ":" << e.second << endl;}mlp.insert(make_pair("peach","桃子"));mlp.erase("apple");//删除所有applemultimap<string, string>::iterator it = mlp.find("apple");if (it != mlp.end()){cout << "apple is also exist" << endl;}else{cout << "apple is not exist" << endl;}return 0;
}

 输出结果：

对于他们的底层实现会在之后的章节进一步实现，最后封装map和set 

end~