set容器(无重复元素集合)///multiset容器(可重复元素集合)
首先介绍set容器
原文链接:http://www.cnblogs.com/wonderKK/archive/2012/04/10/2441379.html
set是STL中一种标准关联容器(vector,list,string,deque都是序列容器,而set,multiset,map,multimap是标准关联容器),它底层使用平衡的搜索树——红黑树实现,插入删除操作时仅仅需要指针操作节点即可完成,不涉及到内存移动和拷贝,所以效率比较高。set,顾名思义是“集合”的意思,在set中元素都是唯一的,而且默认情况下会对元素自动进行升序排列,支持集合的交(set_intersection),差(set_difference) 并(set_union),对称差(set_symmetric_difference) 等一些集合上的操作,如果需要集合中的元素允许重复那么可以使用multiset
#include<set>
#include<iterator>
#include<iostream>
using namespace std;
int main()
{
set<int>eg1;
//插入
eg1.insert(1);
eg1.insert(100);
eg1.insert(5);
eg1.insert(1);//元素1因为已经存在所以set中不会再次插入1
eg1.insert(10);
eg1.insert(9);
//遍历set,可以发现元素是有序的
set<int>::iterator set_iter=eg1.begin();
cout<<"Set named eg1:"<<endl;
for(;set_iter!=eg1.end();set_iter++) cout<<*set_iter<<" ";
cout<<endl;
//使用size()函数可以获得当前元素个数
cout<<"Now there are "<<eg1.size()<<" elements in the set eg1"<<endl;
if(eg1.find(200)==eg1.end())//find()函数可以查找元素是否存在
cout<<"200 isn't in the set eg1"<<endl;
set<int>eg2;
for(int i=6;i<15;i++)
eg2.insert(i);
cout<<"Set named eg2:"<<endl;
for(set_iter=eg2.begin();set_iter!=eg2.end();set_iter++)
cout<<*set_iter<<" ";
cout<<endl;
//获得两个set的并
set<int>eg3;
cout<<"Union:";
set_union(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin()));//注意第五个参数的形式
copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout," "));
cout<<endl;
//获得两个set的交,注意进行集合操作之前接收结果的set要调用clear()函数清空一下
eg3.clear();
set_intersection(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin()));
cout<<"Intersection:";
copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout," "));
cout<<endl;
//获得两个set的差
eg3.clear();
set_difference(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin()));
cout<<"Difference:";
copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout," "));
cout<<endl;
//获得两个set的对称差,也就是假设两个集合分别为A和B那么对称差为AUB-A∩B
eg3.clear();
set_symmetric_difference(eg1.begin(),eg1.end(),eg2.begin(),eg2.end(),insert_iterator<set<int> >(eg3,eg3.begin()));
copy(eg3.begin(),eg3.end(),ostream_iterator<int>(cout," "));
cout<<endl;
return 0;
}
set会对元素进行排序,那么问题也就出现了排序的规则是怎样的呢?上面的示例代码我们发现对int型的元素可以自动判断大小顺序,但是对char*就不会自动用strcmp进行判断了,更别说是用户自定义的类型了,事实上set的标准形式是set<Key, Compare, Alloc>,
参数 | 描述 | 默认值 |
---|---|---|
Key | 集合的关键字和值的类型 | |
Compare | 关键字比较函数,它的参数类型key参数指定的类型,如果第一个参数小于第二个参数则返回true,否则返回false | less<Key> |
Alloc | set的分配器,用于内部内存管理 | alloc |
下面给出一个关键字类型为char*的示例代码
#include<iostream>
#include<iterator>
#include<set>
using namespace std;
struct ltstr
{
bool operator() (const char* s1, const char* s2) const
{
return strcmp(s1, s2) < 0;
}
};
int main()
{
const int N = 6;
const char* a[N] = {"isomer", "ephemeral", "prosaic",
"nugatory", "artichoke", "serif"};
const char* b[N] = {"flat", "this", "artichoke",
"frigate", "prosaic", "isomer"};
set<const char*,ltstr> A(a, a + N);
set<const char*,ltstr> B(b, b + N);
set<const char*,ltstr> C;
cout << "Set A: ";
//copy(A.begin(), A.end(), ostream_iterator<const char*>(cout, " "));
set<const char*,ltstr>::iterator itr;
for(itr=A.begin();itr!=A.end();itr++) cout<<*itr<<" ";
cout << endl;
cout << "Set B: ";
copy(B.begin(), B.end(), ostream_iterator<const char*>(cout, " "));
cout << endl;
cout << "Union: ";
set_union(A.begin(), A.end(), B.begin(), B.end(),
ostream_iterator<const char*>(cout, " "),
ltstr());
cout << endl;
cout << "Intersection: ";
set_intersection(A.begin(), A.end(), B.begin(),B.end(),ostream_iterator<const char*>(cout," "),ltstr());
cout<<endl;
set_difference(A.begin(), A.end(), B.begin(), B.end(),inserter(C, C.begin()),ltstr());
cout << "Set C (difference of A and B): ";
copy(C.begin(), C.end(), ostream_iterator<const char*>(cout, " "));
cout <<endl;
return 0;
}
其中的ltstr也可以这样定义
class ltstr
{
public:
bool operator() (const char* s1,const char*s2)const
{
return strcmp(s1,s2)<0;
}
};
更加通用的应用方式那就是数据类型也是由用户自定义的类来替代,比较的函数自定义,甚至可以加上二级比较,比如首先按照总分数排序,对于分数相同的按照id排序,下面是示例代码
#include<set>
#include<iostream>
using namespace std;
struct
{
int id;
int score;
string name;
};
struct compare
{
bool operator()(const Entity& e1,const Entity& e2)const {
if(e1.score<e2.score) return true;
else
if(e1.score==e2.score)
if(e1.id<e2.id) return true;
return false;
}
};
int main()
{
set<Entity,compare>s_test;
Entity a,b,c;
a.id=123;a.score=90;a.name="bill";
b.id=121;b.score=85;b.name="mary";
c.id=130;c.score=85;c.name="jerry";
s_test.insert(a);s_test.insert(b);s_test.insert(c);
set<Entity,compare>::iterator itr;
cout<<"Score List(ordered by score):\n";
for(itr=s_test.begin();itr!=s_test.end();itr++)
cout<<itr->id<<"---"<<itr->name<<"---"<<itr->score<<endl;
return 0;
}
下面是介绍set和multiset的区别的:
原文地址:https://blog.****.net/longshengguoji/article/details/8546286
集合
Set、multiset都是集合类,差别在与set中不允许有重复元素,multiset中允许有重复元素。
sets和multiset内部以平衡二叉树实现
1. 常用函数
1) 构造函数和析构函数
set c:创建空集合,不包含任何元素
set c(op):以op为排序准则,产生一个空的set
set c1(c2):复制c2中的元素到c1中
set c(const value_type *first, const value_type* last):复制[first, last)之间元素构成新集合
set c(const value_type *first, const value_type* last,op):以op为排序准则,复制[first, last)之间元素构成新集合。
c.~set()销毁所有元素,释放内存
multiset mc:创建空集合,不包含任何元素
multiset mc(op):以op为排序准则,产生一个空的set
multiset c1(c2):复制c2中的元素到c1中
multiset c(const value_type *first, const value_type* last):复制[first, last)之间元素构成新集合
multiset c(const value_type *first, const value_type* last,op):以op为排序准则,复制[first, last)之间元素构成新集合。
c.~set()销毁所有元素,释放内存
- // constructing sets
- #include <iostream>
- #include <set>
- bool fncomp (int lhs, int rhs) {return lhs<rhs;}
- struct classcomp {
- bool operator() (const int& lhs, const int& rhs) const
- {return lhs<rhs;}
- };
- int main ()
- {
- std::set<int> first; // empty set of ints
- int myints[]= {10,20,30,40,50};
- std::set<int> second (myints,myints+5); // range
- std::set<int> third (second); // a copy of second
- std::set<int> fourth (second.begin(), second.end()); // iterator ctor.
- std::set<int,classcomp> fifth; // class as Compare
- bool(*fn_pt)(int,int) = fncomp;
- std::set<int,bool(*)(int,int)> sixth (fn_pt); // function pointer as Compare
- return 0;
- }
2) 大小、判断空函数
int size() const:返回容器元素个数
bool empty() const:判断容器是否为空,若返回true,表明容器已空
3) 增加、删除函数
pair<iterator,bool> insert( x):插入元素x
iterator insert(iterator it,x):在迭代器it处插入元素x
void insert(const value_type *first,const value_type *last):插入[first, last)之间元素
iterator erase(iterator it):删除迭代器指针it处元素
iterator erase(iterator first,iterator last):删除[first, last)之间元素
size_type erase(const Key& key):删除元素值等于key的元素
- #include <iostream>
- #include <set>
- int main ()
- {
- std::set<int> myset;
- std::set<int>::iterator it;
- std::pair<std::set<int>::iterator,bool> ret;
- // set some initial values:
- for (int i=1; i<=5; ++i) myset.insert(i*10); // set: 10 20 30 40 50
- ret = myset.insert(20); // no new element inserted
- if (ret.second==false) it=ret.first; // "it" now points to element 20
- myset.insert (it,25); // max efficiency inserting
- myset.insert (it,24); // max efficiency inserting
- myset.insert (it,26); // no max efficiency inserting
- int myints[]= {5,10,15}; // 10 already in set, not inserted
- myset.insert (myints,myints+3);
- std::cout << "myset contains:";
- for (it=myset.begin(); it!=myset.end(); ++it)
- std::cout << ' ' << *it;
- std::cout << '\n';
- return 0;
- }
- #include <iostream>
- #include <set>
- int main ()
- {
- std::set<int> myset;
- std::set<int>::iterator it;
- // insert some values:
- for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90
- it = myset.begin();
- ++it; // "it" points now to 20
- myset.erase (it);
- myset.erase (40);
- it = myset.find (60);
- myset.erase (it, myset.end());
- std::cout << "myset contains:";
- for (it=myset.begin(); it!=myset.end(); ++it)
- std::cout << ' ' << *it;
- std::cout << '\n';
- return 0;
- }
4) 遍历函数
iterator begin():返回首元素的迭代器指针
iterator end():返回尾元素的迭代器指针
reverse_iterator rbegin():返回尾元素的逆向迭代器指针
reverse_iterator rend():返回首元素前一个位置的迭代器指针
- #include <iostream>
- #include <set>
- int main ()
- {
- int myints[] = {75,23,65,42,13};
- std::set<int> myset (myints,myints+5);
- std::cout << "myset contains:";
- for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
- std::cout << ' ' << *it;
- std::cout << '\n';
- return 0;
- }
5) 操作函数
const_iterator lower_bound(const Key& key):返回容器中大于等于key的迭代器指针
const_iterator upper_bound(const Key& key):返回容器中大于key的迭代器指针
int count(const Key& key) const:返回容器中元素等于key的元素的个数
pair<const_iterator,const_iterator> equal_range(const Key& key) const:返回容器中元素值等于key的迭代指针[first, last)
const_iterator find(const Key& key) const:查找功能,返回元素值等于key的迭代器指针
void swap(set& s):交换集合元素
void swap(multiset& s):交换多集合元素
- #include <iostream>
- #include <set>
- int main ()
- {
- std::set<int> myset;
- std::set<int>::iterator itlow,itup;
- for (int i=1; i<10; i++) myset.insert(i*10); // 10 20 30 40 50 60 70 80 90
- itlow=myset.lower_bound (30); // ^
- itup=myset.upper_bound (60); // ^
- myset.erase(itlow,itup); // 10 20 70 80 90
- std::cout << "myset contains:";
- for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)
- std::cout << ' ' << *it;
- std::cout << '\n';
- return 0;
- }
- #include "stdafx.h"
- #include <iostream>
- #include <set>
- using namespace std;
- int main ()
- {
- set<int> myset;
- for (int i=1; i<=5; i++) myset.insert(i*10); // myset: 10 20 30 40 50
- pair<set<int>::const_iterator,set<int>::const_iterator> ret;
- ret = myset.equal_range(30);
- cout << "the lower bound points to: " << *ret.first << '\n';
- cout << "the upper bound points to: " << *ret.second << '\n';
- return 0;
- }
- #include "stdafx.h"
- #include <iostream>
- #include <set>
- using namespace std;
- int main ()
- {
- int myints[]={12,75,10,32,20,25};
- set<int> first (myints,myints+3); // 10,12,75
- set<int> second (myints+3,myints+6); // 20,25,32
- first.swap(second);
- cout << "first contains:";
- for (set<int>::iterator it=first.begin(); it!=first.end(); ++it)
- cout << ' ' << *it;
- cout << '\n';
- cout << "second contains:";
- for (set<int>::iterator it=second.begin(); it!=second.end(); ++it)
- cout << ' ' << *it;
- cout << '\n';
- return 0;
- }