集合コンテナ | Fluid Dynamics Lab. Kyoto Univ.

std::set

std::setは, 順序集合です. 順序集合の要素を保存することが可能です．利用するには, 比較演算オペレータ<が定義されていなければなりません.

例: グローバル関数を準備

#include <set>
...
class MYF
{
public:
  int val,opt;
  MYF(int i,int j){val=i;opt=j;}
};

bool operator<(const MYF& lhs,const MYF& rhs){return lhs.val < rhs.val;};
...
int main(){
  std::set<MYF> myset;
  myset.emplace(5,1);
  myset.emplace(2,3);
  myset.emplace(-3,5);
  myset.emplace(2,7);
  for(auto& e:myset) std::cout << e.val << "." << e.opt << std::endl;
};

この場合だと, 出力は

-3.5
2.3
5.1

になり, ここの2, 7はねぐられます. なぜならば, ここで定義した比較演算<では, MYF.val だけで大小を決めているので, ここの2,3と同じものであると判断されたからです.

例: 比較クラスを準備

#include <set>
...
class MYF
{
public:
  int val,opt;
  MYF(int i,int j){val=i;opt=j;}
};
class whichLess
{                                                                          
public:                                                                    
    constexpr bool operator()(const MYF& lhs, const MYF& rhs) const
    {return lhs.key > rhs.key;};                                           
};
int main(){
   std::set<MYF,whichLess> myset;
   ...

この比較クラスは, keyが大きい方を「小さい」と定義しちゃってるので, keyが大きい順に集合が並べられます.

例: 比較関数を準備

#include <set>
...
class MYF
{
public:
  int val,opt;
  MYF(int i,int j){val=i;opt=j;}
};
class myTestClass(){
public:
   static bool comComPa(const MYF& lhs,const MYF& rhs)
   {
      return lhs.key < rhs.key;
   };
   std::set<MYF,bool(*)(const MYF&,const MYF&)> myset {comComPa};
   ...

ううむ．このサンプルが，どういう理屈で動作するのか理解できない・・・てゆうか, 最後の{comComPa}が何なのか，だれかここにきて説明しろ

集合系のコンテナ要素はwrite-protectedですよ

集合系のコンテナの最大の特徴は，(key,value)ペアではなく, (key) の集合であるということです．集合に要素を追加した後で, key を変更することはできません！

for(auto& e:myset) e.value+=1;
set.cpp:90:11: error: cannot assign to variable 'e' with const-qualified type 'const MYF &'

このeはMYFオブジェクトですので，比較に使っているkey以外にvalueもあるのですが，集合に追加した要素はwrite-protectかかっているので，書き換えることはできません.

要素がwrite-protectedなのであって, 集合自身はwrite-protectではありません. 要素の追加削除は可能です．要素の値を変更することができないだけです．

std::unordered_set

std::unordered_setは, 順序を持たない集合です. なんのためにあるのかというと, std::setは, 要素の追加挿入をするたびに，要素のソートを行うので，要素が増えると問題になるんですね．で，要素の並び順に興味を持たないユーザーには，ただ遅いだけになるわけです．std::unordered_setは，ソートを省略したので, 追加挿入が少し早い.

あくまでソートしないだけなので，同一の要素を多数保存することはできません. 整数や不動小数点数など，等号が定義されているもののstd::unordered_setは簡単です：

例: いや普通に簡単だろう

#include <unordered_set>
...
class myTestClass(){
public:
   std::unordered_set<int> myset;
   ...

デフォで等号が定義されていない，あんたのクラスには，少しばかり定義するものがあります：

例: ハッシュクラス・等値クラスを準備

#include <set>
...
class MYF
{
public:
  int val,opt;
  MYF(int i,int j){val=i;opt=j;}
};
class myHash
{
public:
    constexpr size_t operator()(const MYF& key) const {return key.key;};
};
class myEqual
{
public:
    constexpr size_t operator()(const MYF& lhs,const MYF& rhs) const {return lhs.key == rhs.key;};  
};      
int main(){
   std::set<MYF,myHash,myEqual> myset;

一応何かで整理する必要があるので, Hash値を計算するクラスが必要です．で，値が等しいとは何か？を定義する必要があります．

std::multiset

順序はあるのだが, 同一の値を多数保持できるstd::multiset もあります．基本的には std::set と同じですが

bool operator <(const myClass& lhs, const myClass& rhs)
{
    return lhs.key < rhs.key;
};
class Multi_Test
{
public:
    std::multiset<myClass> d0;
    Multi_Test()
    {
        d0.emplace(3,0.3);
        d0.emplace(1,0.3);
        d0.emplace(-5,0.2);
        d0.emplace(1,0.1);
        print();
    }
    void print()
    {
        int i=0;
        for(auto& e:d0) std::cout << "d0[" << i++ << "] KEY[" << e.key << "]= " << e.value << std::endl;
    }
};

このような感じでは，

d0[0] KEY[-5]= 0.2
d0[1] KEY[1]= 0.3
d0[2] KEY[1]= 0.1  ⇦重複したキーも，何処かに保存される
d0[3] KEY[3]= 0.3

ところが異なります．