C   STL/ (7) set
  • 預備知識

    • 二叉樹
      樹的任意一個結點都最多隻有兩個結點。
    • 二叉搜尋樹
      樹的任意一個結點的值都比該結點的左子樹中的任意一個結點的值大;同時比該結點右子樹中的任意結點的值小。
    • 平衡二叉樹(紅黑樹RB-tree是平衡二叉樹的一種)
      針對二叉搜尋樹搜尋效能不穩定這個問題。我們跟進一步發明了平衡二叉樹。平衡二叉樹能保證左右子樹的高度差小於等於1。這樣在查詢特點值時不會出現查詢左右兩子樹的開銷相差太大的情況。
  • set/multiset基本概念

    • 什麼是set/multiset?
      set和multiset是關聯型容器。

      • set/multiset的特點
        • set容器中的元素會按元素值的大小進行排序,所以set容器對查詢很支援。
        • set中不允許有重複的元素;而multiset允許
    • set/multiset功能
      下圖所示:
      set
    • set/multiset實現原理
      • set是基於紅黑樹(紅黑樹是一種二叉樹)實現的關聯型容器
  • set/multiset的API

    • 初始化

      set <int> s1;
      multiset<int> s2;
      s1.insert(1);
      set<int> s3(s1);
      set<int> s4=s3;
    • 賦值

          //=運算子過載
      //swap()
    • 元素訪問

      //只能通過iterator訪問元素,且不能改變
      set <int> s1;
      s1.insert(1);
      s1.insert(9);
      s1.insert(5);
      s1.insert(4);
      s1.insert(7);
      s1.insert(8);
      set<int>:: iterator i=s1.begin();
      while(i!=s1.end()){
      cout<<*i<<" ";
      i  ;
      }
      cout<<endl;
      
    • set/multiset大小

      //size()
      //empty()
    • set/multiset插入和刪除

      //insert(ele)
      //erase(iter_start,iter_end)
      //erase(iter_pos)
      //erase(ele)
      //clear()
    • set/multiset查詢

      //find(ele)
      //lower_bound(keyele);
      //upper_bound(keyele);
      //equal_range(keyele);

  • 我們知道set預設的排序方式是從小到大。那麼我們是不是可以通過某種方法讓set實現從大到小的排序呢?
    要實現這個功能就要先理解函式物件的概念。

    • 什麼是函式物件?
      函式物件是一個物件,其使用和函式的形式相同,故稱為函式物件。

      • 定義
      class Mycompare{
      public:
      bool operator() (int val1,int val2){
      return val1>val2;
      }
      };
      Mycompare M_com;
      M_com(3,5); //該物件呼叫過載運算子(),其形式和函式的用法相同。
    • 函式物件的使用
      C STL中已經封裝了很多的函式物件在標頭檔案functional中。下面我們來看一個從大到小給set容器排序的例子。

      
      #include <iostream>
      #include <set>
      #include <functional>
      #include <algorithm>
      using namespace std;
      void printset(set<int,greater<int>> & s);
      int main(){
      set <int,greater<int>> s1;
      s1.insert(1);
      s1.insert(9);
      s1.insert(5);
      s1.insert(4);
      s1.insert(7);
      s1.insert(8);
      printset(s1);
      return 0;
      }
      void printset(set<int,greater<int>> & s){
      set<int>::iterator i = s.begin();
      while (i != s.end()){
      cout << *i << " ";
      i  ;
      }
      cout << endl;
      }
    • 自定義函式物件使用

      
      #include <iostream>
      #include <set>
      #include <functional>
      #include <algorithm>
      using namespace std;
      class Mycompare{
      public:
      bool operator() (int val1, int val2){
      return val1 > val2;
      }
      };
      void printset(set<int,Mycompare> & s);
      int main(){
      //set <int,greater<int>> s1;
      set <int,Mycompare> s1;
      s1.insert(1);
      s1.insert(9);
      s1.insert(5);
      s1.insert(4);
      s1.insert(7);
      s1.insert(8);
      printset(s1);
      return 0;
      }
      void printset(set<int,Mycompare> & s){
      set<int>::iterator i = s.begin();
      while (i != s.end()){
      cout << *i << " ";
      i  ;
      }
      cout << endl;
      }

      我們可能發現了,使用functional自帶的函式物件格式是greater;而自定義的函式物件則是Mycompare沒有<>。我們可以使用template來實現和functional庫檔案中一樣的函式物件格式。修改後的程式如下:

      
      #include <iostream>
      #include <set>
      #include <functional>
      #include <algorithm>
      using namespace std;
      template <class T>
      class Mycompare{
      public:
      bool operator() (T val1, T val2){
      return val1 > val2;
      }
      };
      void printset(set<int,Mycompare<int>> & s);
      int main(){
      //set <int,greater<int>> s1;
      set <int,Mycompare<int>> s1;
      s1.insert(1);
      s1.insert(9);
      s1.insert(5);
      s1.insert(4);
      s1.insert(7);
      s1.insert(8);
      printset(s1);
      return 0;
      }
      void printset(set<int,Mycompare<int>> & s){
      set<int>::iterator i = s.begin();
      while (i != s.end()){
      cout << *i << " ";
      i  ;
      }
      cout << endl;
      }
      

  • set容器也可以存放物件

    //新建一個類
    class Teacher{
    public:
    int id;
    int age;
    Teacher(int id, int age) :id(id), age(age){}
    };
    //寫一個類的排序方法
    class Compare_teacher{
    public:
    bool operator()(Teacher t1, Teacher t2){
    return t1.id < t2.id;
    }
    };
    //main函式部分
    Teacher t1(1, 2), t2(3, 4), t3(5, 6);
    set<Teacher,Compare_teacher>  s_t;    //如果是set<Teacher> s_t;會是什麼情況?
    s_t.insert(t1);
    s_t.insert(t2);
    s_t.insert(t3);
    set<Teacher, Compare_teacher>::iterator i = s_t.begin();
    while (i != s_t.end()){
    cout << "id is : " << i->id << " age is : " << i->age << endl;
    i  ;
    }
    

  • set 容器的最重要的方法find()

    set<Teacher, Compare_teacher>::iterator pos = s_t.find(t2);//find查詢物件
    cout << "id is:"<<pos->id<<"age is:"<<pos->age << endl;
    set<Teacher, Compare_teacher>::iterator pos2 = s_t.find(Teacher(30,4));//find查詢匿名物件
    if (pos2 != s_t.end()){
    cout << "id is:" << pos2->id << "age is:" << pos2->age << endl;
    }
    else{
    cout << "can not find!!" << endl;
    }
  • upper_bound &lower_bound &equal_range的使用
    我們知道set容器的主要功能之一就是查詢,那麼有關查詢的方法就很重要了。
    想要了解上述三種方法的使用,我們先要了解對組的概念。

    • 什麼是對組?
      我們在使用某些變數的時候,往往希望變數能夠接收兩個變數的值;比如:函式傳遞返回值。如果使用結構體或者類去實現又很繁瑣。這個時候就需要對組這個工具了。

      • 如何定義一個對組?
        三種初始化的方法。對組用方法.first來訪問第一個元素;用.second方法來訪問第二個元素。
      pair<int, string> my_pair(10, "abc");
      cout << "my_pair first is :" << my_pair.first << " my_pair second is :" << my_pair.second.c_str() << endl;
      pair<int, string> my_pair2 = make_pair(20, "ABC");
      cout << "my_pair2 first is :" << my_pair2.first << " my_pair2 second is :" << my_pair2.second.c_str() << endl;
      auto my_pair3 = my_pair;
      cout << "my_pair3 first is :" << my_pair3.first << " my_pair3 second is:" << my_pair3.second.c_str() << endl;
    • set的查詢方法

      
      #include <iostream>
      #include <set>
      #include <algorithm>
      using namespace std;
      int main(){
      set <int> s1;
      s1.insert(10);
      s1.insert(34);
      s1.insert(2);
      s1.insert(30);
      s1.insert(5);
      set<int>::iterator i = s1.lower_bound(5);  //>=5
      cout << *i << endl;  //output 5
      set<int>::iterator j = s1.upper_bound(5);    //>5
      cout << *j << endl;   //output 10
      set<int>::iterator p, q;
      p = s1.equal_range(5).first;    //相當於 lower_bound
      q = s1.equal_range(5).second;   //相當於 upper_bound
      cout << *p << " " << *q << endl;
      return 0;
      }