C++中的STL基础复习——unordered_set和set

STL——unordered_set

1. unordered_set基于哈希表&＃xff0c;是无序的&＃xff0c;是一个无序的容器。
2. 头文件

#include


3. 定义以及常用的操作
   定义&＃xff1a;

unordered_set<int> set;


4. 迭代器操作&＃xff1a;
   begin返回unordered_set第一个元素的迭代器
   end返回unordered_set最后一个元素下一个位置的迭代器

5. 常见操作&＃xff1a;
   bool empty() const检测unordered_set是否为空
   insert向容器中插入键值对
   erase删除容器中的键值对
   iterator find(const key_type& k)返回k在哈希桶中的位置
   size_t count(const key_type& k)返回哈希桶中关键码为k的键值对的个数
   size_t size() const获取unordered_set的有效元素个数

比如这里的m其实就是我定义的一个unordered_set&＃xff0c;它里边的内容如下&＃xff1a;

vector<string> wordDict(2);
wordDict[0] &＃61; "apple";
wordDict[1] &＃61; "pen";
unordered_set<string> m(wordDict.begin(), wordDict.end());//定义容器m里装着字典里的内容


键为0时值为apple&＃xff1b;键为1时值为pen。

6. 一些常用操作的例子&＃xff1a;

//定义unordered_set
unordered_set<int> set;
//向容器里插入值
for (int i&＃61;0; i<list.size(); i&＃43;&＃43;)
{set.insert(list[i]);
}
//遍历着输出无序容器里的值
for (unordered_set<int>::iterator i &＃61; set.begin(); i !&＃61; set.end(); i&＃43;&＃43;)
{cout << *i << endl;
}
//找出容器里第39个位置的值
cout << " find 39: " << *set.find(39) << endl;
//统计容器里值为5的个数
cout << "count 14:" << set.count(5) << endl;


STL——set

1. set是STL中的标准关联容器
   set实现了红黑树的平衡二叉检索树的数据结构&＃xff0c;插入元素时&＃xff0c;它会自动调整二叉树的排列&＃xff0c;把元素放到适当的位置&＃xff0c;以保证每个子树根节点键值大于左子树所有节点的键值&＃xff0c;小于右子树所有节点的键值&＃xff1b;另外&＃xff0c;还得保证根节点左子树的高度与右子树高度相等。
   作为一个容器也是用来存储同一数据类型的数据类型&＃xff0c;并且能从一个数据集合中取出数据&＃xff0c;在set中每个元素的值都唯一&＃xff0c;而且系统能根据元素的值自动进行排序。应该注意的是set中数元素的值不能直接被改变。
   跟unordered_set也太像了。
2. 头文件

#include


3. 定义以及常用的操作
   定义&＃xff1a;

set<int> s;


4. 常用操作&＃xff1a;

begin() 　　 ,返回set容器的第一个元素

end() 　　　　 ,返回set容器的最后一个元素

clear() 　　 ,删除set容器中的所有的元素

empty() 　　　,判断set容器是否为空

max_size() 　 ,返回set容器可能包含的元素最大个数

size() 　　　　 ,返回当前set容器中的元素个数

count() 用来查找set中某个某个键值出现的次数。这个函数在set并不是很实用&＃xff0c;因为一个键值在set只可能出现0或1次&＃xff0c;这样就变成了 判断某一键值是否在set出现过了。

关于这个STL&＃xff08;Standard Template Library&＃xff09;标准模板库

1. 这个库里边封装了许多复杂的数据结构算法和大量常用的数据结构操作。vector封装数组&＃xff0c;list封装了链表&＃xff0c;map和set封装了二叉树等&＃xff0c;在封装这些数据结构的时候&＃xff0c;STL按照程序员的使用习惯&＃xff0c;以成员函数方式提供的常用操作&＃xff0c;如&＃xff1a;插入、排序、删除、查找等。让用户在STL使用过程中&＃xff0c;并不会感到陌生。

2. 其实也就是存了很多常用不常用的已经造好的轮子。

3. 从逻辑层次来看&＃xff0c;在STL中体现了泛型化程序设计的思想&＃xff08;generic programming&＃xff09;&＃xff0c;引入了诸多新的名词&＃xff0c;比如像需求&＃xff08;requirements&＃xff09;&＃xff0c;概念&＃xff08;concept&＃xff09;&＃xff0c;模型&＃xff08;model&＃xff09;&＃xff0c;容器&＃xff08;container&＃xff09;&＃xff0c;算法&＃xff08;algorithmn&＃xff09;&＃xff0c;迭代子&＃xff08;iterator&＃xff09;等。与OOP&＃xff08;object-oriented programming&＃xff09;中的多态&＃xff08;polymorphism&＃xff09;一样&＃xff0c;泛型也是一种软件的复用技术。

4. 如果&＃xff0c;有的时候&＃xff0c;你需要在程序中用到堆、栈、队列、链表等一些基本的算法&＃xff0c;而你又实在不想自己去实现数据结构教科书中那些繁琐的算法&＃xff0c;那么你就可以考虑使用STL。

5. 红黑树的底层实现就是set和map。

了解下红黑树&＃xff1a;
红黑树在二叉查找树的基础上还必须满足以下着色规则&＃xff1a;
每个节点不是红色就是黑色
根节点为黑色
如果节点为红&＃xff0c;其子节点必须为黑&＃xff08;一条路径上不能出现连续的两个红色节点&＃xff09;
任一节点至NULL&＃xff08;树尾端&＃xff09;的任何路径&＃xff0c;所含之黑节点数必须相同

6. 很常用的有vector&＃xff0c;string&＃xff0c;stack&＃xff0c;queue&＃xff0c;set&＃xff0c;unordered_set&＃xff0c;map等。