一、什么是 set？

set 容器，又稱集合容器，即該容器的底層是以紅黑樹變體實現(xiàn)的，是典型的關(guān)聯(lián)式容器。這意味著，set 容器中的元素可以分散存儲在內(nèi)存空間里，而不是必須存儲在一整塊連續(xù)的內(nèi)存空間中。跟任意其它類型容器一樣，它能夠存放各種類型的對象。

二、容器特性

1.存儲結(jié)構(gòu)

set是由多個節(jié)點(二叉樹中的紅黑樹變體)組成的。

2.集合

set 容器不能在指定位置插入，意味著不支持at(pos)和[]操作。在set中查找元素，效率是非常高的

multiset與set的區(qū)別：set中的元素值唯一，每個元素只能出現(xiàn)一次；而multiset中同一元素可以出現(xiàn)多次。

3.雙向迭代器

不支持隨機訪問迭代器，只能從容器中第一個元素或最后一個元素開始遍歷容器，直到找到該位置。

三、基本函數(shù)實現(xiàn)

1，構(gòu)造函數(shù)

• set();創(chuàng)建一個空set
• set(const set&);復(fù)制構(gòu)造函數(shù)
• set(begin,end);復(fù)制[begin,end)區(qū)間內(nèi)的元素，到另一個set中

2.set插入

• iterator insert(const T& x); 插入元素

3.set刪除

• iterator erase(iterator it);刪除集合中迭代器指向元素
• iterator erase(iterator first,iterator last);刪除集合中[first,last)中元素
• size_type erase(const key_type& elem); 刪除指定的元素
• void clear();清空集合中所有元素

4.查找函數(shù)

• iterator set.find(elem); //查找elem元素，返回指向elem元素的迭代器。

• size_type set.count(elem); //返回容器中值為elem的元素個數(shù)。對set來說，要么是0，要么是1。對multiset來說，值可能大于1。

• iterator set.lower_bound(elem); //返回第一個>=elem元素的迭代器。

• iterator set.upper_bound(elem); // 返回第一個>elem元素的迭代器。

• reverse_iterator rbegin();反向迭代器，指向最后一個元素

• pair set.equal_range(elem); //返回一對迭代器，這兩個迭代器分別用于指向set中大于指定元素的第一個元素，以及等于或大于指定元素的第一個元素。

  equal_range返回值pair是什么？

  • pair.second是pair里面的第二個值，是T2類型。
  • pair.first是pair里面的第一個值，是T1類型。
  • pair存放的兩個值的類型，可以不一樣，如T1為int，T2為float。T1,T2也可以是自定義類型。
  • pair譯為對組，實際上就是一個結(jié)構(gòu)體類型，有兩個成員。

5.判斷函數(shù)

• bool empty() const;判斷容器中是否有元素，若無元素，則返回 true；反之，返回 false。

6.大小函數(shù)

• int size() const;返回集合中元素的個數(shù)
• int max_size() const;返回最大可允許的set元素數(shù)量值

7.其他函數(shù)

• void swap(set&);交換兩個同類型集合的數(shù)據(jù)

四、基本用法

#include
#include
using namespace std;
int main()
{
  set<int> s;
  for (int i = 0; i < 10; i++)
  {
    s.insert(rand()%20);
  }
  for (set<int>::iterator it = s.begin(); it != s.end(); it++)
  {
    cout << *it << " ";
  }
  cout <<"\\nset size():"<< s.size() << endl;
  //輸出：0 1 2 4 7 9 14 18  為什么只輸出8個元素呢？
  //因為set只能存在唯一的元素，重復(fù)的會被丟掉
  //思考：為什么set里面的元素是有序的呢？
  //因為set是關(guān)聯(lián)式容器，會默認按照升序進行排列




  //如果找到，返回指向的迭代器，沒有找到返回end()迭代器，所以再輸出之前
  //需要判斷是否找到
  set<int>::iterator it1 = s.find(6);
  if (it1 != s.end())
  {
    cout << *it1 << endl;
  }
  //如果set中有等于4的元素，則返回指向4的迭代器，如果沒有返回第一個
  //大于4的元素的迭代器，沒有找到返回end()迭代器
  it1 = s.lower_bound(4);
  if (it1 != s.end())
  {
    cout << *it1 << endl;
  }
  //如果set中有大于4的元素，返回第一個大于4的元素的迭代器，沒有找
  //到返回end()迭代器
  it1 = s.upper_bound(4);
  if (it1 != s.end())
  {
    cout << *it1 << endl;
  }
  cout <<"------------------我是 C語言Plus 華麗分割線"<