本文主要是介绍C++ | STL 单集合容器set和多集合容器multiset,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
一.单集合容器set和多集合容器multiset
二.set常用的构造方式
三.set的插入,删除以及查找操作
四.set的访问函数
五.比较 set 和multiset的不同
六.使用set和multiset时的注意事项
一.单集合容器set和多集合容器multiset
set指的是单集合容器,所谓的单集合容器指的是容器里面的数据不能重复,所需要的头文件为#include<set>,其底层为红黑树。
multiset指的是多集合容器,所谓的多集合容器指的是容器里面的数据可以重复,所需要的头文件为#include<set>,其底层为红黑树。
二.set常用的构造方式
#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{std::set<int> myset; //默认的构造 int arr[] = { 13, 2, 343, 2, 53, 6 };int len = sizeof(arr) / sizeof(arr[0]);std::set<int> myset1(arr, arr + len);Show(myset);Show(myset1);return 0;
}
在构造set容器myset时,调用的是set类中默认的构造函数,(所有的容器中都有默认的构造函数),且构造的同时没有做任何事情。
在构造set容器myset1时,我们传入的参数是一个迭代器区间,即将arr数组的开始和末尾的后一个位置传入,也就是将arr中的数据插入到myset1中。并且我们发现,虽然在向myset1中插入元素时,有重复的元素2,但最终的打印的结果却只有一个2,这是因为单集合容器set里面的数据不能重复。而且打印的结果是从小到大打印的,这是因为单集合容器set的底层为红黑树,默认的排序方式是从小到大的。
三.set的插入,删除以及查找操作
#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{std::set<int> myset; //默认的构造 std::set<int> myset1;int arr[] = { 11,22,33,44 };int len = sizeof(arr) / sizeof(arr[0]);myset1.insert(arr, arr + len);Show(myset1);for (int i = 0; i < 5; i++){myset.insert(i + 1);//按位置插入 set只给出了数据 没有给出位置。}myset.insert(myset.begin(), 10);//位置无效 Show(myset);myset.erase(10);std::set<int>::iterator it = myset.begin();myset.erase(it);Show(myset);return 0;
}
我们知道,set容器的底层是红黑树,而红黑树是在二叉排序树的基础上实现的,这也就意味着在向set容器中插入元素时不需要传入位置,因为红黑树会自动根据插入节点的值的大小来调整该节点的位置,使得最后该二叉树还是一个红黑树,因此也就不存在头插,尾插以及按位置插等方法,例如上述代码中,哪怕你在insert函数中给定了要插入的位置,系统也会将该位置忽略,所以我们在调用insert时只需要给定要插入的值就可以。或者我们也可以给定一个迭代器区间,将这个区间内的所有值都插入。
insert的重载还有很多,在这里就不一一列举。
因为set的底层为红黑树,因此也不存在头删,尾删,因为每个节点的位置随时都可能发生变动。
erase的重载还有很多,在这里就不一一列举。
关于在set容器中查找一个值为val的元素是否存在,在std域下有一个泛型算法find可以实现,这个find函数的形参是要查找的范围即一个迭代器区间,以及要查找的值val,但这个find的时间复杂度为O(n),因为这个泛型算法采用的是顺序遍历。另外,在set类中也会提供一个find函数,这个find函数的形参为要查找的值val,而他的时间复杂度为O(log2 n),因为set底层是红黑树,而红黑树中的数据已经经过了排列而变得有序了,那么就可以使用二分法来查找。
因此set容器的优点就是“快速查找”。
#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{int arr[] = { 13, 2, 343, 2, 53, 6 };int len = sizeof(arr) / sizeof(arr[0]);std::set<int> myset(arr, arr + len);Show(myset);//find 时间复杂度 O(n) 泛型算法库std::set<int>::iterator fit1 = std::find(myset.begin(),myset.end(), 53);if (fit1 != myset.end()){std::cout << *fit1 << std::endl;}//find 时间复杂度O(log2 n) set类中提供 优点std::set<int>::iterator fit2 = myset.find(53);if (fit2 != myset.end()){std::cout << *fit2 << std::endl;}return 0;
}
四.set的访问函数
#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{int arr[] = { 1,9,8,10,7,3,6,2,5,4 };int len = sizeof(arr) / sizeof(arr[0]);std::set<int> myset(arr, arr + len);Show(myset);return 0;
}
我们发现我们在访问某一set容器时,最终的结果是从小到大排序的,因为这是系统默认的,我们也可以通过添加参数,来决定底层的二叉树对数据的排序方法。例如:
#include<iostream>
#include<set>
#include<algorithm>template<typename Container>
void Show(Container con)
{typename Container::iterator it = con.begin();while (it != con.end()){std::cout << *it << " ";it++;}std::cout << std::endl;
}int main()
{int arr[] = { 1,9,8,10,7,3,6,2,5,4 };int len = sizeof(arr) / sizeof(arr[0]);std::set<int,std::less<int>> myset(arr, arr + len);std::set<int, std::greater<int>> myset1(arr, arr + len);Show(myset);Show(myset1);return 0;
}
五.比较 set 和multiset的不同
所谓的multiset其实就是多集合容器,其底层也是一棵红黑树,之前我们讲过,单集合容器set中不允许有重复的数据存在,而多集合容器multiset恰恰与其相反,因为它允许重复的元素存在。多集合容器multiaet所需要的头文件也为#include<set>。下面,我们来举一个例子,来看一下二者的区别。
#include<iostream>
#include<set>
#include<iterator>
#include<algorithm>int main()
{const int size = 16;int a[size] = { 17,11,29,89,73,53,61,37,41,29,3,47,31,59,5,2 };std::multiset<int> intMultiset(a, a + size); //用a来初始化INTMS容器实例std::ostream_iterator<int> output(std::cout, " ");//整型输出迭代子output,可通过cout输出用空格分隔的整数std::cout << "这里原来有" << intMultiset.count(17)<< "个数值17" << std::endl; intMultiset.insert(17); //插入一个重复的数17std::cout << "输入后这里有" << intMultiset.count(17) << "个数值17" << std::endl;std::multiset<int>::const_iterator result;result = intMultiset.find(18);//找到则返回所在位置,设找到返回与调end()返回的同样值if (result == intMultiset.end()){std::cout << "没找到值18" << std::endl;}else{std::cout << "找到值18" << std::endl;}std::cout << "intMultiset容器中有" << std::endl;copy(intMultiset.begin(), intMultiset.end(), output);//输出容器中全部元素std::cout << std::endl;
}
我们看到一开始多集合容器multiset中只有一个17,但在我们又插入了一个17后,多集合容器multiset中17的个数就变为2个了,所以多集合容器multiset中允许数据重复。因为多集合容器multiset的用法几乎与set相同,所以我们不在这里一一阐述,至于上述代码中出现的泛型算法copy和输出流迭代器在我以前的博客 迭代器 那一篇有讲到过,感兴趣的读者可以自行去学习。
六.使用set和multiset时的注意事项
我们知道set的底层是红黑树,每次我们插入一个新的数据后,红黑树都要按中序遍历的形式从小到大(默认是从小到大)的对数据进行排序,一般我们我们插入的数据的类型都是内置类型,例如 int char double ......,但是如果我们要插入的数据的类型是自定义类型时,红黑树就不知道该怎么对这些自定义类型的数据排序了。所以当我们向set中插入自定义类型的数据时,那么该自定义类型的类中就要提供比较运算符的重载函数,便于set进行排序。multiset的注意事项与set相同。
这篇关于C++ | STL 单集合容器set和多集合容器multiset的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!