C++中set⽤法详解
1.关于set
C++ STL 之所以得到⼴泛的赞誉，也被很多⼈使⽤，不只是提供了像vector, string, list等⽅便的容器，更重要的是STL封装了许多复杂的数据结构算法和⼤量常⽤数据结构操作。vector封装数组，list封装了链表，map和set封装了⼆叉树等，在封装这些数据结构的时候，STL按照程序员的使⽤习惯，以成员函数⽅式提供的常⽤操作，如：插⼊、排序、删除、查等。让⽤户在STL使⽤过程中，并不会感到陌⽣。
关于set，必须说明的是set关联式容器。set作为⼀个容器也是⽤来存储同⼀数据类型的数据类型，并且能从⼀个数据集合中取出数据，在set中每个元素的值都唯⼀，⽽且系统能根据元素的值⾃动进⾏排序。应该注意的是set中数元素的值不能直接被改变。C++ STL中标准关联容器set, multiset, map, multimap内部采⽤的就是⼀种⾮常⾼效的平衡检索⼆叉树：红⿊树，也成为RB树(Red-Black Tree)。RB树的统计性能要好于⼀般平衡⼆叉树，所以被STL选择作为了关联容器的内部结构。
关于set有下⾯⼏个问题：
（1）为何map和set的插⼊删除效率⽐⽤其他序列容器⾼？
⼤部分⼈说，很简单，因为对于关联容器来说，不需要做内存拷贝和内存移动。说对了，确实如此。set容器内所有元素都是以节点的⽅式来存储，其节点结构和链表差不多，指向⽗节点和⼦节点。结构图可能如下：
  A
  / \
  B C
　/ \ / \
D E F G
因此插⼊的时候只需要稍做变换，把节点的指针指向新的节点就可以了。删除的时候类似，稍做变换后把指向删除节点的指针指向其他节点也OK 了。这⾥的⼀切操作就是指针换来换去，和内存移动没有关系。
（2）为何每次insert之后，以前保存的iterator不会失效？
iterator这⾥就相当于指向节点的指针，内存没有变，指向内存的指针怎么会失效呢(当然被删除的那个元素本⾝已经失效了)。相对于vector来说，每⼀次删除和插⼊，指针都有可能失效，调⽤push_back在尾部插⼊也是如此。因为为了保证内部数据的连续存放，iterator指向的那块内存在删除和插⼊过程中可能已经被其他内存覆盖或者内存已经被释放了。即使时push_back的时候，容器内部空间可能不够，需要⼀块新的更⼤的内存，只有把以前的内存释放，申请新的更⼤的内存，复制已有的数据元素到新的内存，最后把需要插⼊的元素放到最后，那么以前的内存指针⾃然就不可⽤了。特别时在和find等算法在⼀起使⽤的时候，牢记这个原则：不要使⽤过期的iterator。
（3）当数据元素增多时，set的插⼊和搜索速度变化如何？
如果你知道log2的关系你应该就彻底了解这个答案。在set中查是使⽤⼆分查，也就是说，如果有16个元素，最多需要⽐较4次就能到结果，有32个元素，最多⽐较5次。那么有10000个呢？最多⽐较的次数为log10000，最多为14次，如果是20000个元素呢？最多不过15次。看见了吧，当数据量增⼤⼀倍的时候，搜索次数只不过多了1次，多了1/14的搜索时间⽽已。你明⽩这个道理后，就可以安⼼往⾥⾯放⼊元素了。
2.set中常⽤的⽅法
begin()        ，返回set容器的第⼀个元素
end()      ，返回set容器的最后⼀个元素
clear()          ，删除set容器中的所有的元素
empty()    ，判断set容器是否为空
max_size()  ，返回set容器可能包含的元素最⼤个数
size()      ，返回当前set容器中的元素个数
rbegin    ，返回的值和end()相同
rend()    ，返回的值和rbegin()相同
写⼀个程序练⼀练这⼏个简单操作吧：
4using namespace std;
5
6int main()
7 {
8set<int> s;
9    s.insert(1);
10    s.insert(2);
11    s.insert(3);
12    s.insert(1);
13    cout<<"set 的 size 值为："<<s.size()<<endl;
14    cout<<"set 的 maxsize的值为："<<s.max_size()<<endl;
15    cout<<"set 中的第⼀个元素是："<<*s.begin()<<endl;
16    cout<<"set 中的最后⼀个元素是:"<<*s.end()<<endl;
17    s.clear();
pty())
19    {
20        cout<<"set 为空"<<endl;
21    }
22    cout<<"set 的 size 值为："<<s.size()<<endl;
23    cout<<"set 的 maxsize的值为："<<s.max_size()<<endl;
24return0;
25 }
运⾏结果：
⼩结：插⼊3之后虽然插⼊了⼀个1，但是我们发现set中最后⼀个值仍然是3哈，这就是set 。还要注意begin() 和 end()函数是不检查set是否为空的，使⽤前最好使⽤empty()检验⼀下set是否为空.
count() ⽤来查set中某个某个键值出现的次数。这个函数在set并不是很实⽤，因为⼀个键值在set只可能出现0或1次，这样就变成了判断某⼀键值是否在set出现过了。
⽰例代码：
4using namespace std;
5
6int main()
7 {
8set<int> s;
9    s.insert(1);
10    s.insert(2);
11    s.insert(3);
12    s.insert(1);
13    cout<<"set 中 1 出现的次数是："<&unt(1)<<endl;
14    cout<<"set 中 4 出现的次数是："<&unt(4)<<endl;
15return0;
16 }
运⾏结果：
equal_range() ，返回⼀对定位器，分别表⽰第⼀个⼤于或等于给定关键值的元素和第⼀个⼤于给定关键值的元素，这个返回值是⼀个pair类型，如果这⼀对定位器中哪个返回失败，就会等于end()的值。具体这个有什么⽤途我还没遇到过~~~
⽰例代码：
1 #include <iostream>
2 #include <set>
3
4using namespace std;
5
6int main()
7 {
8set<int> s;
9set<int>::iterator iter;
10for(int i = 1 ; i <= 5; ++i)
11    {
12        s.insert(i);
13    }
14for(iter = s.begin() ; iter != s.end() ; ++iter)
15    {
16        cout<<*iter<<"";
17    }
18    cout<<endl;
19    pair<set<int>::const_iterator,set<int>::const_iterator> pr;
20    pr = s.equal_range(3);
21    cout<<"第⼀个⼤于等于 3 的数是："<<*pr.first<<endl;
22    cout<<"第⼀个⼤于 3的数是： "<<*pr.second<<endl;
23return0;
24 }
运⾏结果：
erase(iterator)  ，删除定位器iterator指向的值
erase(first,second)，删除定位器first和second之间的值
erase(key_value)，删除键值key_value的值
看看程序吧：
1 #include <iostream>
2 #include <set>
3
4using namespace std;
5
6int main()
7 {
8set<int> s;
9set<int>::const_iterator iter;
10set<int>::iterator first;
11set<int>::iterator second;
12for(int i = 1 ; i <= 10 ; ++i)
13    {
14        s.insert(i);
15    }
16//第⼀种删除
17    s.erase(s.begin());
18//第⼆种删除
19    first = s.begin();
20    second = s.begin();
21    second++;
22    second++;
23    s.erase(first,second);
24//第三种删除
25    s.erase(8);
26    cout<<"删除后 set 中元素是：";
27for(iter = s.begin() ; iter != s.end() ; ++iter)
28    {
29        cout<<*iter<<"";
30    }
31    cout<<endl;
32return0;
33 }
运⾏结果：
⼩结：set中的删除操作是不进⾏任何的错误检查的，⽐如定位器的是否合法等等，所以⽤的时候⾃⼰⼀定要注意。
find()  ，返回给定值值得定位器，如果没到则返回end()。
⽰例代码：
1 #include <iostream>
2 #include <set>
3
4using namespace std;
5
6int main()
7 {
8int a[] = {1,2,3};
9set<int> s(a,a+3);
10set<int>::iterator iter;
11if((iter = s.find(2)) != s.end())
12    {
13        cout<<*iter<<endl;
14    }
15return0;
16 }
insert(key_value); 将key_value插⼊到set中，返回值是pair<set<int>::iterator,bool>，bool标志着插⼊
是否成功，⽽iterator代表插⼊的位置，若key_value已经在set中，则iterator表⽰的key_value在set中的位置。
inset(first,second)；将定位器first到second之间的元素插⼊到set中，返回值是void.
⽰例代码：
1 #include <iostream>
2 #include <set>
3
4using namespace std;
5
6int main()
7 {
8int a[] = {1,2,3};
9set<int> s;
10set<int>::iterator iter;
11    s.insert(a,a+3);
12for(iter = s.begin() ; iter != s.end() ; ++iter)
13    {
14        cout<<*iter<<"";
15    }
16    cout<<endl;
17    pair<set<int>::iterator,bool> pr;
18    pr = s.insert(5);
19if(pr.second)
20    {
21        cout<<*pr.first<<endl;
22    }
23return0;namespace是干嘛的
24 }
运⾏结果：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。