STL set

STL 對這個序列可以進行查找，插入刪除序列中的任意一個元素，而完成這些操作的時間同這個序列中元素個數的對數成比例關係，並且當游標指向一個已刪除的元素時，刪除操作無效。而一個經過更正的和更加實際的定義應該是：一個集合(set)是一個容器，它其中所包含的元素的值是唯一的。這在收集一個數據的具體值的時候是有用的。集合中的元素按一定的順序排列，並被作為集合中的實例。一個集合通過一個鍊表來組織，在插入操作和刪除操作上比向量(vector)快，但查找或添加末尾的元素時會有些慢。具體實現採用了紅黑樹的平衡二叉樹的數據結構。

基本介紹

• 中文名：STL set
• 用途：可以進行查找
• 相關：所包含的元素的值是唯一的
• 性質：數據結構

集和多集

#include <set>

一個集合（set）是一個容器，它其中所包含的元素的值是唯一的。

集和多集的區別是：set支持唯一鍵值，set中的值都是特定的，而且只出現一次；而multiset中可以出現副本鍵，同一值可以出現多次。

構造

explicit set(const Compare&=compare());

如：set<int,less<int> > set1;

less<int>是一個標準類，用於形成升序排列函式對象。降序排列是用greater<int>。

Template<class InputIterator> set(InputIterator, InputIterator,\ const Compare&=compare());

如：set<int ,less<int> >set2(vector1.begin(),vector1.end());

通過指定某一預先定義的區間來初始化set對象的構造函式。

set（const set<Key,Compare&>）;

如：set<int ,less<int> >set3(set2);

複製構造函式。

方法

begin() 返回指向第一個元素的疊代器

clear() 清除所有元素

count() 返回某個值元素的個數

empty() 如果集合為空，返回true(真）

end() 返回指向最後一個元素之後的疊代器，不是最後一個元素

equal_range() 返回集合中與給定值相等的上下限的兩個疊代器

erase() 刪除集合中的元素

find() 返回一個指向被查找到元素的疊代器，如果沒找到則返回end()

get_allocator() 返回集合的分配器

insert() 在集合中插入元素

lower_bound() 返回指向大於（或等於）某值的第一個元素的疊代器

key_comp() 返回一個用於元素間值比較的函式

max_size() 返回集合能容納的元素的最大限值

rbegin() 返回指向集合中最後一個元素的反向疊代器

rend() 返回指向集合中第一個元素的反向疊代器

size() 集合中元素的數目

swap() 交換兩個集合變數

upper_bound() 返回大於某個值元素的疊代器

value_comp() 返回一個用於比較元素間的值的函式

集合操作

std::set_intersection() :這個函式是求兩個集合的交集。

std::set_union() :求兩個集合的並集

std::set_difference（）：差集

std::set_symmetric_difference（）：得到的結果是 第一個疊代器相對於第二個的差集 並上

第二個相對於第一個的差集

struct compare{

bool operator ()(string s1,string s2){

return s1>s2;

}///自定義一個仿函式

};

std::set<string,compare> s

string str[10];

string *end = set_intersection(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//求交集，返回值指向str最後一個元素的尾端

end = std::set_union(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//並集

end = std::set_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//s2相對於s1的差集

end = std::set_difference(s2.begin(),s2.end(),s.begin(),s.end(),str,compare());//s1相對於s2的差集

end = std::set_symmetric_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//上面兩個差集的並集

例子

1//////////////////////////////////////////////////////////////////

#include <iostream>

#include <set>

using namespace std;

int main(void)

{

set<int> set1;

for(int i=0; i<10; ++i)

set1.insert(i);

for(set<int>::iterator p=set1.begin();p!=set1.end();++p)

cout<<*p<<"";

if(set1.insert(3).second)//把3插入到set1中

//插入成功則set1.insert(3).second返回1，否則返回0

//此例中，集中已經有3這個元素了，所以插入將失敗

cout<<"set insert success";

else

cout<<"set insert failed";

int a[] = {4, 1, 1, 1, 1, 1, 0, 5, 1, 0};

multiset<int> A;

A.insert(set1.begin(),set1.end());

A.insert(a,a+10);

cout<<endl;

for(multiset<int>::iterator p=A.begin();p!=A.end();++p)

cout<<*p<<" ";

cin.get();

return 0;

}

2////////////////////////////////////////

#include <iostream>

#include <set>

#include <string>

#include <algorithm>

using namespace std;

struct compare

{

bool operator ()(string s1,string s2)

{

return s1>s2;

}///自定義一個仿函式

};

int main()

{

typedef std::set<string,compare> _SET;

_SET s;

s.insert(string("sfdsfd"));

s.insert(string("apple"));

s.insert(string("english"));

s.insert(string("dstd"));

cout<<"s1:"<<endl;

std::set<string,compare>::iterator it = s.begin();

while(it!=s.end())

cout<<*it++<<" ";

cout<<endl<<"s2:"<<endl;

_SET s2;

s2.insert(string("abc"));

s2.insert(string("apple"));

s2.insert(string("english"));

it = s2.begin();

while(it!=s2.end())

cout<<*it++<<" ";

cout<<endl<<endl;

string str[10];

string *end = set_intersection(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//求交集，返回值指向str最後一個元素的尾端

cout<<"result of set_intersection s1,s2:"<<endl;

string *first = str;

while(first<end)

cout <<*first++<<" ";

cout<<endl<<endl<<"result of set_union of s1,s2"<<endl;

end = std::set_union(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//並集 first = str;

while(first<end)

cout <<*first++<<" ";

cout<<endl<<endl<<"result of set_difference of s2 relative to s1"<<endl;

first = str;

end = std::set_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//s2相對於s1的差集 while(first<end)

cout <<*first++<<" ";

cout<<endl<<endl<<"result of set_difference of s1 relative to s2"<<endl;

first = str;

end = std::set_difference(s2.begin(),s2.end(),s.begin(),s.end(),str,compare());//s1相對於s2的差集

while(first<end)

cout <<*first++<<" ";

cout<<endl<<endl;

first = str;

end = std::set_symmetric_difference(s.begin(),s.end(),s2.begin(),s2.end(),str,compare());//上面兩個差集的並集 while(first<end)

cout <<*first++<<" ";

cout<<endl;

}