C++中Set和Map基本使用_set

一、基本概念

        首先来认识一个概念，在Set和Map中用来比较的值称为关键字，在使用中通常称为键，而另外的Map中还有存储数据的值，称为值，和键一起组成了键值对（key_value）。这样定义的原因在于两个容器底层都使用了KV结构搜索二叉树的变种----红黑树。

        1.set（集）

        set中只存储键，可抽象的看似于数组，能储存任何类型的原始值和引用，不过储存的键具有唯一性，总的来说有以下特性：

        1.set是一个类数组对象

        2.set储存的值是不重复的

        3.set所有的元素都会被自动排序（搜索二叉树的特性）

        4.不能通过迭代器来改变set的值

        5.底层以红黑树作为容器

        2.map（字典） 

        map类似于set，不过map中储存键值对，键必须唯一，值可以修改，能通过键自动排序，总的来说有以下特性：

        1.map以键值对，即key_value形式储存数据

        2.不允许键重复

        3.所有元素通过键进行自动排序

        4.键不可修改，值可以修改

        5.底层以红黑树作为容器

二、基本使用

        1.set的使用

         （1）初始化

int main()
{
	set<int> test({2,1,3,3,1,5,4});
    	for (auto i : test)
	{
		cout << i << " ";
	}
	cout << endl;
	cout <<"size:" << test.size() << endl;
	return 0;
}

        运行结果：

                               

        可以看到，set的插入类似于vector，并对重复数据进行了去重，还将数据进行了排序。

        （2）插入-insert

int main()
{
	set<int> test;
	test.insert(1);
	test.insert(1);
 
	test.insert(3);
	test.insert(3);
 
	test.insert(2);
 
	
 
	for (auto i : test)
	{
		cout << i << " ";
	}
	cout << endl;
	cout <<"size:" << test.size() << endl;
	return 0;
}

        运行结果： 

                                 

        可以看到，插入的效果和初始化类似。

        （3）查找-find

//时间复杂度：O(logN)----底层是搜索树
set<int>::iterator pos = s.find(3);
//时间复杂度：O(N)----需要遍历一遍（不建议使用）
set<int>::iterator pos = find(s.begin(), s.end(), 3);
if (pos != s.end())
{
	cout << "找到了" << endl;
}

        对于查找，有两种方式，一种是利用搜索树的特性去查找，一种是利用迭代器将搜索树看作类似于数组那样的结构，再遍历查找。对于这两种方法，显然第一种的效率更高。

        （4）删除-erase

test.erase(3);//（1）值删除
test.erase(pos);//（2）迭代器删除
cout << "删除后数据：";
for (auto i : test)
{
	cout << i << " ";
}
cout << endl;
cout <<"size:" << test.size() << endl;

         运行结果：

                            

        对于删除，也有两种操作方式，一种是直接用想删除的值删除，一种配合find传迭代器去删除，不过要注意的是，当find未找到删除值时，会返回空迭代器，用空迭代器删除会导致报错。 

        （5）清空-clear

test.clear();//清掉所有数据
 
cout << "清空后数据：";
for (auto i : test)
{
	cout << i << " ";
}
cout << endl;
cout <<"size:" << test.size() << endl;

        运行结果：

                                    

        一键清空功能，好用效率高。 

        2.map的使用

        map有别于set，对键值对形式的数据，使用了pair容器进行储存。pair中的first对应于map的key（键），second对应于map的value（值）。

        （1）初始化

map<int, string> test({ {3,"结束"},{1,"开始"},{2,"运行"},{1,"xxxxxx"} });
cout << "原数据："<<endl;
for (auto i : test)
{
	cout << i.first<<":" <<i.second<< endl;
}
cout << "size:" << test.size() << endl;

        运行结果：

                              

可以看到，map初始化不看value，map在初始化时大致和set初始化时相同，所以当即使key相同，value不同时，也无法储存数据。 

        （2）operator[]

        对于为什么先介绍map的[],主要因为这个重载包含插入和查找后修改（和find区分）两个功能，操作简单，因此先介绍该方法。

        *插入：

test[-1] = "预备";//[]是一种重载，因此符合key的类型即可，所以是可以使用-1的
cout << "插入后的数据：" << endl;
for (auto i : test)
{
	cout << i.first << ":" << i.second << endl;
}
cout << "size:" << test.size() << endl;

        运行结果：

                          

 

        *查找：

cout << test[3] << endl;//即通过key打印value
test[3] = "未完待续";//即通过key修改value
cout << "插入后的数据：" << endl;
for (auto i : test)
{
	cout << i.first << ":" << i.second << endl;
}
cout << "size:" << test.size() << endl;

        运行结果：

             

        可以看到，[]的功能大致为：如果key存在便返回value，如果key不存在则新构建一个pair插入。

        （3）插入-insert

map<int, string> test;
test.insert(pair<int, string>(1, "开始"));//模板类型pair：构造了一个匿名对象插入到map
test.insert(make_pair(2, "运行"));//模板函数make_pair
test.insert({ 3, "结束" });
 

         intert有三种插入方式，需要注意的是，map元素的插入都是传入pair容器进行插入。

        （4）查找-find

//时间复杂度：O(logN)----底层是搜索树
map<int,string>::iterator pos = test.find(3);
//时间复杂度：O(N)----需要遍历一遍（不建议使用）
map<int,string>::iterator pos= find(test.begin(), test.end(), 3);
if (pos != test.end())
{
	cout << "找到了" << endl;
}

         如果是为了找到后修改value值，建议使用[]。        

        （5）删除

test.erase(3);//（1）值删除
test.erase(pos);//（2）迭代器删除
cout << "删除后数据："<<endl;
for (auto i : test)
{
	cout << i.first << ":" << i.second << endl;
}
cout << "size:" << test.size() << endl;

       （6）清空

test.clear();//清掉所有数据
 
cout<<"清空后数据"<<endl;
for (auto i : test)
{
	cout << i.first << ":" << i.second << endl;
}
cout << "size:" << test.size() << endl;
return 0;

三、使用场景介绍

        Set：

                1.数组去重

                2.快速查找S

                3.排序（n*logn）

                4.......

        Map：

                1.字典操作，通过键映射值，类似宏定义，但比宏更加多样化   

                2.复杂链表的复制，将旧节点和复制出新节点组成键值关系，当旧节点有另外的指向指向3节点时，新节点可以通过map拿到新的3节点，然后建立指向。

                3.........

        其实对于map来说，set的使用场景map也都可以实现。

四、总结

        看了这么多的操作，其实本质上对于Set和Map来说，其优越点主要是在插入、删除和查找这些操作上，而这些特性是基于在红黑树（搜索二叉树的一种）上实现的，至于其他的特性则是在红黑树上的扩展。