【C++】set的使用

?个人主页： Forcible Bug Maker
?专栏： STL || C++

目录

?前言?关于set?容量函数==empty====size== ?Modifiers==insert====erase====clear== ?Operations==find====count====lower_bound和upper_bound====equal_range== ?关于multiset?结语

?前言

本篇博客主要内容：STL库中set的介绍以及其用法的讲解。

set和map的底层结构是红黑树，而红黑树又是一种特殊的二叉搜索树（红黑树可以保持树的平衡）。而我们今天来学习什么是set，以及如何使用set这个容器。如果对二叉搜索树不了解，可以参考这篇：【数据结构进阶】二叉搜索树

?关于set

set是按照一定次序存储元素的容器在set中，元素的value也标识它(value就是key，类型为T)，并且每个value必须是唯一的。set中的元素不能在容器中修改(元素总是const)，但是可以从容器中插入或删除它们。在内部，set中的元素总是按照其内部比较对象(类型比较)所指示的特定严格弱排序准则进行排序。set容器通过key访问单个元素的速度通常比unordered_set容器慢，但它们允许根据顺序对子集进行直接迭代。set在底层是用二叉搜索树(红黑树)实现的。

?容量函数

empty

判断set对象是否为空。

#include<iostream>#include<set>using namespace std;int main(){set<int> se;cout << se.empty() << endl;se.insert(1);cout << se.empty() << endl;return 0;}

size

返回set对象中的元素个数。

#include <iostream>#include <set>int main (){  std::set<int> myints;  std::cout << "0. size: " << myints.size() << '\n';  for (int i=0; i<10; ++i) myints.insert(i);  std::cout << "1. size: " << myints.size() << '\n';  myints.insert (100);  std::cout << "2. size: " << myints.size() << '\n';  myints.erase(5);  std::cout << "3. size: " << myints.size() << '\n';  return 0;}

?Modifiers

insert

支持三种重载：
single element (1)
单个元素插入

pair<iterator,bool> insert (const value_type& val);

with hint (2)
暗示插入

iterator insert (iterator position, const value_type& val);

range (3)
迭代器区间插入

template <class InputIterator>  void insert (InputIterator first, InputIterator last);

// set::insert (C++98)#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;}

erase

(1)
通过迭代器指向直接删除

void erase (iterator position);

(2)
通过值的查找删除，同时返回删除元素的个数

size_type erase (const value_type& val);

(3)
迭代器区间删除

void erase (iterator first, iterator last);

#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;}

clear

将set对象中所有的元素清空。
size变为0。

#include <iostream>#include <set>int main (){  std::set<int> myset;  myset.insert (100);  myset.insert (200);  myset.insert (300);  std::cout << "myset contains:";  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)    std::cout << ' ' << *it;  std::cout << '\n';  myset.clear();  myset.insert (1101);  myset.insert (2202);  std::cout << "myset contains:";  for (std::set<int>::iterator it=myset.begin(); it!=myset.end(); ++it)    std::cout << ' ' << *it;  std::cout << '\n';  return 0;}

?Operations

find

查找set对象中的某个元素，返回指向此元素的迭代器；如不存在，返回迭代器set::end。

#include <iostream>#include <set>int main (){  std::set<int> myset;  std::set<int>::iterator it;  // set some initial values:  for (int i=1; i<=5; i++) myset.insert(i*10);    // set: 10 20 30 40 50  it=myset.find(20);  myset.erase (it);  myset.erase (myset.find(40));  std::cout << "myset contains:";  for (it=myset.begin(); it!=myset.end(); ++it)    std::cout << ' ' << *it;  std::cout << '\n';  return 0;}

count

查找并返回set对象中和val值相等的值的个数。

#include <iostream>#include <set>int main (){  std::set<int> myset;  // set some initial values:  for (int i=1; i<5; ++i) myset.insert(i*3);    // set: 3 6 9 12  for (int i=0; i<10; ++i)  {    std::cout << i;    if (myset.count(i)!=0)      std::cout << " is an element of myset.\n";    else      std::cout << " is not an element of myset.\n";  }  return 0;}

在set中，此函数显得比较没用，因为set中每个元素最多只有一个。但是在mutiset中就大不相同了，mutiset允许数据冗余。

lower_bound和upper_bound

iterator lower_bound (const value_type& val) const;

返回set对象中 大于等于（>=）val 的第一个元素的迭代器·。

iterator upper_bound (const value_type& val) const;

返回set对象中 大于（>）val 的第一个元素的迭代器。

// set::lower_bound/upper_bound#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;}

equal_range

pair<iterator,iterator> equal_range (const value_type& val) const;

返回一个pair，其中是与val值相等的set对象的迭代器区间。

// set::equal_elements#include <iostream>#include <set>int main (){  std::set<int> myset;  for (int i=1; i<=5; i++) myset.insert(i*10);   // myset: 10 20 30 40 50  std::pair<std::set<int>::const_iterator,std::set<int>::const_iterator> ret;  ret = myset.equal_range(30);  std::cout << "the lower bound points to: " << *ret.first << '\n';  std::cout << "the upper bound points to: " << *ret.second << '\n';  return 0;}

?关于multiset

multiset是按照特定顺序存储元素的容器，其中元素是可以重复的。在multiset中，元素的value也会识别它(因为multiset中本身存储的就是<value, value>组成的键值对，因此value本身就是key，key就是value，类型为T). multiset元素的值不能在容器中进行修改(因为元素总是const的)，但可以从容器中插入或删除。在内部，multiset中的元素总是按照其内部比较规则(类型比较)所指示的特定严格弱排序准则进行排序。multiset容器通过key访问单个元素的速度通常比unordered_multiset容器慢，但当使用迭代器遍历时会得到一个有序序列。multiset底层结构为二叉搜索树(红黑树)。

总的来说，multiset与set的区别是，multiset中的元素可以重复，set中value是唯一的。同时，成员函数count()和equal_range()在mutiset中也更有其意义。
这里就不再赘述关于multiset的使用了。

?结语

本篇博客我们介绍了STL库中set和multiset，以及set成员函数接口的使用。multiset支持数据冗余，而set中的值（value）是唯一的。感谢大家支持♥