1.关联式容器

如果你接触过STL中的部分容器,比如:vector、list、deque、forward_list(C++11)等,那你应该知道这些容器统称为序列式容器,因为其底层为线性序列的数据结构,里面存储的是元素本身。那什么是关联式容器?它与序列式容器有什么区别?

关联式容器也是用来存储数据的,与序列式容器不同的是,其里面存储的是<key, value>结构的键值对,在数据检索时比序列式容器效率更高。比如:set、map、unordered_set、unordered_map等。

贴士:
C++STL当中的stack、queue和priority_queue属于容器适配器,它们默认使用的基础容器分别是deque、deque和vector。

树形结构与哈希结构

根据应用场景的不同,C++STL总共实现了两种不同结构的关联式容器:树型结构和哈希结构。

关联式容器容器结构底层实现
set、map、multiset、multimap树型结构平衡搜索树(红黑树)
unordered_set、unordered_map、unordered_multiset、unordered_multimap哈希结构哈希表

其中,树型结构容器中的元素是一个有序的序列,而哈希结构容器中的元素是一个无序的序列。

2.键值对

用来表示具有一一对应关系的一种结构,该结构中一般只包含两个成员变量key和value,key代表键值,value表示与key对应的信息。

比如:现在要建立一个英汉互译的字典,那该字典中必然有英文单词与其对应的中文含义,而且,英文单词与其中文含义是一一对应的关系,即通过该应该单词,在词典中就可以找到与 其对应的中文含义。

SGI-STL中关于键值对的定义:

template <class T1, class T2>
struct pair
{
typedef T1 first_type;
typedef T2 second_type;
T1 first;
T2 second;
pair(): first(T1()), second(T2())
{}
pair(const T1& a, const T2& b): first(a), second(b)
{}
};

3. set

3.1set的介绍

set文档介绍
在这里插入图片描述

了解

  1. set是按照一定次序存储元素的容器
  2. 在set中,元素的value也标识它(value就是key,类型为T),并且每个value必须是唯一的。set中的元素
    不能在容器中修改(元素总是const),但是可以从容器中插入或删除它们。
  3. 在内部,set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。
  4. set容器通过key访问单个元素的速度通常比unordered_set容器慢,但它们允许根据顺序对子集进行直
    接迭代。
  5. set在底层是用二叉搜索树(红黑树)实现的。
3.2 set的定义方式
set<int> s1; //构造int类型的空容器

set<int> s2(s1); //拷贝构造int类型s1容器的复制品

string str("abcdef");
set<char> s3(str.begin(), str.end()); //构造string对象某段区间的复制品

set < int, greater<int>> s4; //构造int类型的空容器,比较方式指定为大于
3.3 set的使用

set当中常用的成员函数如下:

成员函数功能
insert插入指定元素
erase删除指定元素
find查找指定元素
size获取容器中元素的个数
empty判断容器是否为空
clear清空容器
swap交换两个容器中的数据
count获取容器中指定元素值的元素个数

set迭代器:

函数声明功能介绍
iterator begin()返回set中起始位置元素的迭代器
iterator end()返回set中最后一个元素后面的迭代器
const_iterator cbegin() const返回set中起始位置元素的const迭代器
const_iterator cend() const返回set中最后一个元素后面的const迭代器
reverse_iterator rbegin()返回set第一个元素的反向迭代器,即end
reverse_iterator rend()返回set最后一个元素下一个位置的反向迭代器,即
rbeginconst_reverse_iterator crbegin() const返回set第一个元素的反向const迭代器,即cend
const_reverse_iterator crend() const返回set最后一个元素下一个位置的反向const迭代器,即crbegin

set使用范例:

#include<iostream>
#include<set>
void test_set1()
{
	set<int> s;
     //插入元素(去重,不冗余)
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(5);
//迭代器遍历
	set<int>::iterator it = s.begin();
	//set迭代器是中序遍历,set原理是二叉搜索树
	while (it != s.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	
	//删除
	//法一:
	//C++11的auto,比较方便,本质这里应该是迭代器,因为find返回的就是迭代器
	auto f = s.find(4);
	if (f != s.end())
		s.erase(f);

	//法二:也可以直接删除,有的话删除,没有的话也不报错
	s.erase(5);
	s.erase(44);
//算法中的find
	//注意:vector,list没有find-->用的是算法的find
	auto fi = find(s.begin(), s.end(), 1);
	if (fi != s.end())
		s.erase(fi);
	//比较:算法的find是暴力查找,O(n);set的find是平衡二叉树实现,O(log n)

//范围for遍历输出
	for (auto& e : s)
	{
		cout << e << " ";
	}
	cout << endl;

//计算容器中值为2的元素个数
	cout << s.count(2) << endl; //1
	//容器大小
	cout << s.size() << endl; //2
	//清空容器
	s.clear();
	//容器判空
	cout << s.empty() << endl; //1
	//交换两个容器的数据
	set<int> tmp{ 11, 22, 33, 44 };
	s.swap(tmp);
	//遍历容器方式三(反向迭代器)
	set<int>::reverse_iterator rit = s.rbegin();
	while (rit != s.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl; 
}

main()
{
test_set1();
return 0}

注意

  1. 与map/multimap不同,map/multimap中存储的是真正的键值对<key, value>,set中只放value,但 在底层实际存放的是由<value, value>构成的键值对。
  2. set中插入元素时,只需要插入value即可,不需要构造键值对。
  3. set中的元素不可以重复(因此可以使用set进行去重)。
  4. 使用set的迭代器遍历set中的元素,可以得到有序序列
  5. set中的元素默认按照小于来比较
  6. set中查找某个元素,时间复杂度为:log2 n
  7. set中的元素不允许修改
  8. set中的底层使用二叉搜索树(红黑树)来实现

4. multiset

multiset容器与set容器的底层实现一样,都是平衡搜索树(红黑树),其次,multiset容器和set容器所提供的成员函数的接口都是基本一致的,multiset容器和set容器的唯一区别就是,multiset允许键值冗余,即multiset容器当中存储的元素是可以重复的

使用范例:

void test_multiset()
{
	multiset<int> s;
	s.insert(1);
	s.insert(2);
	s.insert(1);
	s.insert(4);
	s.insert(3);
	s.insert(2);
	s.insert(2);
	s.insert(5);

	multiset<int>::iterator it = s.begin();
	//set迭代器是中序遍历,set原理是二叉搜索树
	while (it != s.end())
	{
		cout << *it << " ";
		it++; 
	}
	cout << endl;

	auto m = s.find(2);
	//muitiset查找2查找的是中序的第一个
	while (m != s.end()&&*m==2)
	{
		cout << *m << ' ';
		m++;
	}
	cout << endl;
	//count可以直接计算数据的个数
	cout << s.count(1) << endl;
	cout << s.count(2) << endl;
	cout << s.count(3) << endl;
}

由于multiset容器允许键值冗余,因此两个容器中成员函数find和count的意义也有所不同:

成员函数find

  • set对象 返回值为val的元素的迭代器
  • multiset对象 返回底层搜索树中序的第一个值为val的元素的迭代器

成员函数count

  • set对象 值为val的元素存在则返回1,不存在则返回0(find成员函数可代替)
  • multiset对象 返回值为val的元素个数(find成员函数不可代替)

注意

  1. multiset中再底层中存储的是<value, value>的键值对
  2. mtltiset的插入接口中只需要插入即可
  3. 与set的区别是,multiset中的元素可以重复,set是中value是唯一的
  4. 使用迭代器对multiset中的元素进行遍历,可以得到有序的序列
  5. multiset中的元素不能修改
  6. 在multiset中找某个元素,时间复杂度为O(log2 n)
  1. multiset的作用:可以对元素进行排序

5. map

5.1 map的介绍

map的文档简介
在这里插入图片描述

了解

  1. map是关联容器,它按照特定的次序(按照key来比较)存储由键值key和值value组合而成的元素。
  2. 在map中,键值key通常用于排序和惟一地标识元素,而值value中存储与此键值key关联的内容。键值key和值value的类型可能不同,并且在map的内部,key与value通过成员类型value_type绑定在一起,为其取别名称为pair:typedef pair value_type;
  3. 在内部,map中的元素总是按照键值key进行比较排序的。
  4. map中通过键值访问单个元素的速度通常比unordered_map容器慢,但map允许根据顺序对元素进行直接迭代(即对map中的元素进行迭代时,可以得到一个有序的序列)。
  5. map支持下标访问符,即在[]中放入key,就可以找到与key对应的value。
  6. map通常被实现为二叉搜索树(更准确的说:平衡二叉搜索树(红黑树))。
5.2 map的定义方式
map<int, double> m1; //构造一个key为int类型,value为double类型的空容器

map<int, double> m2(m1); //拷贝构造key为int类型,value为double类型的m1容器的复制品


map<int, double> m3(m2.begin(), m2.end()); //使用迭代器拷贝构造m2容器某段区间的复制品


map<int, double, greater<int>> m4; //构造一个key为int类型,value为double类型的空容器,key比较方式指定为大
5.3 map的使用
5.3.1 map的插入

map的插入函数的函数原型如下:

pair<iterator,bool> insert (const value_type& val);

insert函数的返回值

insert函数的返回值也是一个pair对象,该pair对象中第一个成员的类型是map的迭代器类型,第二个成员的类型的一个bool类型,具体含义如下:

  • 若待插入元素的键值key在map当中不存在,则insert函数插入成功,并返回插入后元素的迭代器和true。
  • 若待插入元素的键值key在map当中已经存在,则insert函数插入失败,并返回map当中键值为key的元素的迭代器和false。

insert函数的参数
insert函数的参数显示是value_type类型的,实际上value_type就是pair类型的别名:
typedef pair<const Key, T> value_type;

因此,我们向map容器插入元素时,需要用key和value构造一个pair对象,然后再将pair对象作为参数传入insert函数。

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	map<int, string> m;
	//方式一:调用pair的构造函数,构造一个匿名对象插入
	m.insert(pair<int, string>(2, "two"));
	m.insert(pair<int, string>(1, "one"));
	m.insert(pair<int, string>(3, "three"));
	for (auto e : m)
	{
		cout << "<" << e.first << "," << e.second << ">" << " ";
	}
	cout << endl; //<1,one> <2,two> <3,three>
	return 0;
}

但是这种方式会使得我们的代码变得很长,pair是map中的key,value键值对,需要写参数,这样很麻烦,为了方便我们一般使用make_pair。
make_pair是函数模板。可以自行推演参数类型
在这里插入图片描述
我们只需向make_pair函数传入key和value,该函数模板会根据传入参数类型进行自动隐式推导,最终构造并返回一个对应的pair对象

#include <iostream>
#include <string>
#include <map>
using namespace std;

int main()
{
	//方式二:调用函数模板make_pair,构造对象插入
	map<string, string> m;

	m.insert(pair<string, string>("sort", "排序"));
	m.insert(make_pair("insert", "插入"));
	m.insert(make_pair("left", "左边"));
	m.insert(make_pair("right", "右边"));
	map<string, string>::iterator it = m.begin();
	while (it != m.end())
	{
		//cout << *it << " ";//error:*it不可能返回两个值,map是key,value键值对
		
		//法一:
		//cout << (*it).first << ":" << (*it).second << endl;//first代表key,second代表value
		
		// 法二:
		//当迭代器节点指针管理的数据是结构体的时候,可以用箭头,pair实际就算是是结构体,成员包括key,value ,即first和second
		cout << it->first << ":" << it->second << endl;

		it++;
	}
	return 0;
}

map中其他插入法

map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict["string"] = "字符串";//先插入("string","缺省值"),再修改value值
	dict["left"];//插入,然后给缺省值""
	dict["left"]="左边";//map中已经有“left”,相当于查找,然后修改value值
5.3.2 map的查找

map的查找函数的函数原型如下:

iterator find (const key_type& k);

map的查找函数是根据所给key值在map当中进行查找,若找到了,则返回对应元素的迭代器,若未找到,则返回容器中最后一个元素下一个位置的正向迭代器。

使用范例:用map统计字符串次数

void test_map2()
{
	//用map统计字符串次数
	string str[] = { "sort","hello","sort","set","map","set","list" };
	map<string, int> countMap;

	//法1
	for (auto& e :str)
	{
		auto ret = countMap.find(e);
		if (ret== countMap.end())
		{
			countMap.insert(make_pair(e, 1));
		}
		else
		{
			ret->second++;
		}
	}
//上面查找的缺点:进行了二次查找,find一次,insert找到合适位置插入又一次

	//法2(少了一次查找)--但不好理解,可读性不强
	for (auto& e : str)
	{
		//标准写法:pair<map<string, int>::iterator, bool> ret = countMap.insert(make_pair(e, 1));
		auto ret = countMap.insert(make_pair(e, 1));
		if (ret.second == false)//插入失败,表明map中已经有相同的字符串,返回指向map中原有相同字符串的迭代器(即返回map当中键值为key的元素的迭代器),这里即指ret.first
		{
			ret.first->second++;//对应的次数++
		}
	}

	//法3 map的[]运算符重载
	//统计次数巧用:map::operator[](它的返回值是对应节点value值的引用)
	for (auto& e : str) 
	{
		//[]:给一个key,返回一个value,
		countMap[e]++;//给一个key,返回一个value,然后对value++,即统计次数
	}

	for (auto& kv : countMap)
	{
		cout << kv.first << ":" << kv.second << endl;
	}

}

我们先来具体讲解下上面用map统计字符串次数用到的法3:map的[ ]运算符重载

map的[ ]运算符重载函数的函数原型如下:

mapped_type& operator[] (const key_type& k);

[ ]运算符重载函数的参数就是一个key值,而这个函数的返回值如下:

(*((this->insert(make_pair(k, mapped_type()))).first)).second

实际上[ ]运算符重载实现的逻辑实际上就是以下三个步骤:

调用insert函数插入键值对。
拿出从insert函数获取到的迭代器。
返回该迭代器位置元素的值value。

mapped_type& operator[] (const key_type& k)
{
	//1、调用insert函数插入键值对
	pair<iterator, bool> ret = insert(make_pair(k, mapped_type()));
	//2、拿出从insert函数获取到的迭代器
	iterator it = ret.first;
	//3、返回该迭代器位置元素的值value
	return it->second;
}

总结一下:

如果k不在map中,则先插入键值对<k, V()>,然后返回该键值对中V对象的引用。
如果k已经在map中,则返回键值为k的元素对应的V对象的引用。

5.3.3 map的删除

map的删除函数的函数原型如下:

//删除函数1
size_type erase (const key_type& k);
//删除函数2
void erase(iterator position);

也就是说,我们既可以根据key值删除指定元素,也可以根据迭代器删除指定元素,若是根据key值进行删除,则返回实际删除的元素个数。

int main()
{
	map<int, string> m;
	m.insert(make_pair(1, "one"));
	m.insert(make_pair(2, "two"));
	m.insert(make_pair(3, "three"));
	//方式一:根据key值进行删除
	m.erase(3);
	//方式二:根据迭代器进行删除
	map<int, string>::iterator pos = m.find(2);
	if (pos != m.end())
	{
		m.erase(pos);
	}
	return 0;
}
5.3.4 map的其他成员函数

除了上述成员函数外,set当中还有如下几个常用的成员函数:

成员函数功能
size获取容器中元素的个数
empty判断容器是否为空
clear清空容器
swap交换两个容器中的数据
count获取容器中指定key值的元素个数
begin获取容器中第一个元素的正向迭代器
end获取容器中最后一个元素下一个位置的正向迭代器
rbegin获取容器中最后一个元素的反向迭代器
rend获取容器中第一个元素前一个位置的反向迭代器

【总结】

  1. map中的的元素是键值对
  2. map中的key是唯一的,并且不能修改
  3. 默认按照小于的方式对key进行比较
  4. map中的元素如果用迭代器去遍历,可以得到一个有序的序列
  5. map的底层为平衡搜索树(红黑树),查找效率比较高
  6. 支持[]操作符,operator[]中实际进行插入查找。

6. multimap

multimap容器与map容器的底层实现一样,也都是平衡搜索树(红黑树),其次,multimap容器和map容器所提供的成员函数的接口都是基本一致的,multimap容器和map容器的区别与multiset容器和set容器的区别一样,multimap允许键值冗余,即multimap容器当中存储的元素是可以重复的。

使用范例:

void test_multimap4()
{

	map<string, string> dict;
	dict.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("sort", "排序!!!"));//err:只要key有,就不会插入,不冗余

	//multimap其他用法和map基本相同,唯一不同,multimap不支持[],因为同一名字的key可能有多个value
	multimap<string, string> dict1;//允许数据冗余
	dict1.insert(make_pair("sort", "排序"));
	dict.insert(make_pair("sort", "排序!!!"));
	dict1.insert(make_pair("sort", "排序"));
}

由于multimap容器允许键值冗余,因此两个容器中成员函数find和count的意义也有所不同:

成员函数find

  • map对象 返回值为键值为key的元素的迭代器
  • multimap对象 返回底层搜索树中序的第一个键值为key的元素的迭代器
  • 成员函数count
  • map对象 键值为key的元素存在则返回1,不存在则返回0(find成员函数可代替)
  • multimap对象 返回键值为key的元素个数(find成员函数不可代替)

好了,(set、map、multiset、multimap)基本介绍及使用就讲到这里了,下面就来个题练练手吧~

leetcode ——692. 前K个高频单词

leetcode ——692. 前K个高频单词

在这里插入图片描述
代码:

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        //统计单词出现次数,此时得first已经是字典序了
        map<string,int> countMap;
        for(auto &e:words)
        {
            countMap[e]++;
        }
        //排序
        multimap<int,string,greater<int>> sortmap;//按照降序
        for(auto &e:countMap)
        {
            sortmap.insert(make_pair(e.second,e.first));
//sortmap中是降序的first,即单词出现次数,并且此时的sortmap中相同first(即出现次数相同)对应的second是按字典序排序的,因为countMap在插入到sortmap时它的second(单词)就是字典序了,相当于用sortmap排序是稳定的。
        }
        //输出
        vector<string> v;
        for(auto &e:sortmap)
        {
            v.push_back(e.second);
            if(--k==0)
            break;
        }
    return v;
    }
};
Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐