std::list と std::set の悩ましい関係2011年04月06日 14時52分22秒

C++ に Standard Template Library 通称 STL が登場して C++ も格段に使いやすくなった。普段使っている分には、再開発の労力を削減でき、気分良く使っているが時折微妙な落とし穴がある。

std::list と std::set は似通ったインターフェースを持っている。単一性の保持する std::set と、双方向リストの std::list。

元々、std::list で掛かれていたコードを変更していた。何が来ても単純に insert() をしていたコードだったが、厳格に単一性を求める必要が出て来て、std::set に変えてみた。ところが、find() の後に値の変更が出来ない。std::set の find は iterator find ( const key_type& x ) const; となっているので、変更不可なのだ。

つまり、std::set は一度挿入したら、二度と変更できない。もし、値を変更したいのなら erase() の後に insert() し直す必要がある。最初と最後の場合を考えると、あまり単純には場所指定の insert も出来ない。

鍵の変更が行なわれると std::set の順列が保てないので理解出来る実装ではあるが、自ら比較演算子を実装し、順序に影響の無い値を変更しているのに何とも煩わしい。仕方が無いので、結局 std::map になってしまった。しかも、鍵と値を別々に分けて、鍵部分を二重に保持。

std::list の値は変更可だが、std::set の値は変更不可なのだ。