STL 應用之set

之前在解決一道算法題的時候，應用到set，特意對這個stl的容器類做了一些了解。在我的印象中，set就是一個元素不重復的集合，而事實上也正是這樣的。無論從MSDN還是任何其它地方，都會告訴我們set的元素不可以重復。反之，只要元素不重復，就可以順利的放入到set中。看起來這實在是再清楚不過了，但是仔細想一想的話，就會發現，話說只要不重復的元素就可以被放入到一個set中，但是什麼樣的元素是不重復的元素呢？或者說，什麼樣的元素是互不相同的呢？對於內置數據類型，也就是傳說中的primary data type，像int 、 double、unsigned，甚至string，這些元素的“相同”非常容易理解，那麼對於自定義類型呢？什麼樣的數據是相同的呢？什麼樣的數據又是不同的呢？
在以前學習STL的時候，曾經學到過，如果要將自定義的類型放入到set中的話，就需要重載“<”符號，原因是set是一個有序的集合，集合會按照“<”比較的大小，默認按照從小到大的順序排列。假設我現在設計如下類型：
class MyType
{
public:
  int a, b, c;
}
這是，為了讓MyType類型可以順利的放進set中，我必須重載“<”，這時問題來了，要如何重載呢？這個類型有三個數據成員，我能不能要求按照a的大小排列，如果a相等的話就隨便按照b或者c的大小排列呢？如果近實現按照a的大小排列的話，重載函數如下：
bool operator<(const MyType& myType) const
{
   return a<myType.a;
}
看起來簡單明了,但是事實真的是這樣嗎?如果我聲明一個set,並在其中放入MyType(1,2,3)、MyType(1,2,4)我能成功嗎？實驗了一下，結果如下：
  

測試時用的代碼是這樣的：
#include<iostream>
#include<set>
using namespace std;
class MyType
{
public:
  int a, b, c;
  MyType(int a, int b, int c):a(a), b(b), c(c){}
  bool operator<(const MyType& myType) const
  {
    return a<myType.a;
  }
};
int main()
{
  set<MyType> se;
  MyType type1(1,2,3);
  MyType type2(1,2,4);
  se.insert(type1);
  se.insert(type2);
  cout<<"The set size:"<<se.size()<<endl;
  cout<<"Elements in the set as follows:"<<endl;
  for(set<MyType>::iterator it = se.begin(); it != se.end(); it++)
  {
    cout<<"("<<it->a<<", "<<it->b<<", "<<it->c<<") ";
  }
  cout<<endl;
  return 0;
}
結果很明顯，當我已經把MyType（1,2,3）放到set中之後，就不能把MyType（1,2,4）放進去了。但是為什麼呢？這兩個對象看起來確實不一樣啊！STL在比較是否相同的時候不是要比較每一個數據成員的嗎？從上述的例子中，看到的確實不是這樣的，STL不會自動的做任何比較，它僅對你說明過的動作干一些指定的活兒。在重載“<”的時候，當只指定眾多數據成員中的一部分的時候，如果這部分都相同的話，set就認為是同一個元素了。就如上述所示一樣，重載的時候僅作了a的比較，而沒有說明如果a相同的話，是否對剩下的元素進行比較。這樣一來，set認為MyType（1,2,3）和MyType(1,2,4)是一樣的。要讓set正確的進行大小的比較，針對自定義類型，就必須說明所有的數據成員的比較情況。如上述的例子的“<”重載，應該這樣寫：
bool operator<(const MyType& myType) const
{
  return a<myType.a?true:(b<myType.b?true:c<myType.c);
}
這樣一來，就完全說明了每一個數據成員的比較關系，set就可以正常工作了。還是MyType(1,2,3)、MyType(1,2,4)兩個元素，這回運行的結果如下：

  


 

運行代碼為：
#include<iostream>
#include<set>
using namespace std;
class MyType
{
public:
  int a, b, c;
  MyType(int a, int b, int c):a(a), b(b), c(c){}
  bool operator<(const MyType& myType) const
  {
    return a<myType.a?true:(b<myType.b?true:c<myType.c);
  }
};
int main()
{
  set<MyType> se;
  MyType type1(1,2,3);
  MyType type2(1,2,4);
  se.insert(type1);
  se.insert(type2);
  cout<<"The set size:"<<se.size()<<endl;
  cout<<"Elements in the set as follows:"<<endl;
  for(set<MyType>::iterator it = se.begin(); it != se.end(); it++)
  {
    cout<<"("<<it->a<<", "<<it->b<<", "<<it->c<<") ";
  }
  cout<<endl;
  return 0;
}

 

摘自  Martin's Tips