C++
std :: setとstd :: multiset
サーチ…
前書き
setは、要素がソートされユニークなコンテナの一種です。 multisetは似ていますが、 multisetの場合、複数のエレメントが同じ値を持つことができます。
備考
これらの例では、C ++のさまざまなスタイルが使用されています。 C ++ 98コンパイラを使用している場合は注意してください。このコードの一部は使用できない場合があります。
セットに値を挿入する
セットには3つの異なる挿入方法を使用できます。
- まず、値の簡単な挿入。このメソッドは、呼び出し側が挿入が実際に発生したかどうかを確認できるようにするペアを返します。
- 次に、値が挿入される場所のヒントを指定して挿入します。そのような場合に挿入時間を最適化することが目的ですが、値の挿入先を知ることは一般的なケースではありません。 その場合は注意してください。ヒントを与える方法はコンパイラのバージョンによって異なります 。
- 最後に、開始ポインタと終了ポインタを指定して値の範囲を挿入することができます。開始のものは挿入に含まれ、終了のものは除外されます。
#include <iostream>
#include <set>
int main ()
{
std::set<int> sut;
std::set<int>::iterator it;
std::pair<std::set<int>::iterator,bool> ret;
// Basic insert
sut.insert(7);
sut.insert(5);
sut.insert(12);
ret = sut.insert(23);
if (ret.second==true)
std::cout << "# 23 has been inserted!" << std::endl;
ret = sut.insert(23); // since it's a set and 23 is already present in it, this insert should fail
if (ret.second==false)
std::cout << "# 23 already present in set!" << std::endl;
// Insert with hint for optimization
it = sut.end();
// This case is optimized for C++11 and above
// For earlier version, point to the element preceding your insertion
sut.insert(it, 30);
// inserting a range of values
std::set<int> sut2;
sut2.insert(20);
sut2.insert(30);
sut2.insert(45);
std::set<int>::iterator itStart = sut2.begin();
std::set<int>::iterator itEnd = sut2.end();
sut.insert (itStart, itEnd); // second iterator is excluded from insertion
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
std::cout << *it << std::endl;
}
return 0;
}
出力は次のようになります。
# 23 has been inserted!
# 23 already present in set!
Set under test contains:
5
7
12
20
23
30
45
マルチセットに値を挿入する
セットからのすべての挿入メソッドもマルチセットに適用されます。それにもかかわらず、initializer_listを提供する別の可能性があります。
auto il = { 7, 5, 12 };
std::multiset<int> msut;
msut.insert(il);
セットのデフォルトのソートの変更
setとmultisetはデフォルトの比較メソッドがありますが、場合によってはそれらをオーバーロードする必要があります。
文字列値をセットに格納しているとしましょうが、その文字列には数値のみが含まれていることがわかります。デフォルトでは、並べ替えは辞書順の文字列比較であるため、順序は数値の並べ替えと一致しません。 int値と同等のソートを適用するには、compareメソッドをオーバーロードするためのファンクタが必要です。
#include <iostream>
#include <set>
#include <stdlib.h>
struct custom_compare final
{
bool operator() (const std::string& left, const std::string& right) const
{
int nLeft = atoi(left.c_str());
int nRight = atoi(right.c_str());
return nLeft < nRight;
}
};
int main ()
{
std::set<std::string> sut({"1", "2", "5", "23", "6", "290"});
std::cout << "### Default sort on std::set<std::string> :" << std::endl;
for (auto &&data: sut)
std::cout << data << std::endl;
std::set<std::string, custom_compare> sut_custom({"1", "2", "5", "23", "6", "290"},
custom_compare{}); //< Compare object optional as its default constructible.
std::cout << std::endl << "### Custom sort on set :" << std::endl;
for (auto &&data : sut_custom)
std::cout << data << std::endl;
auto compare_via_lambda = [](auto &&lhs, auto &&rhs){ return lhs > rhs; };
using set_via_lambda = std::set<std::string, decltype(compare_via_lambda)>;
set_via_lambda sut_reverse_via_lambda({"1", "2", "5", "23", "6", "290"},
compare_via_lambda);
std::cout << std::endl << "### Lambda sort on set :" << std::endl;
for (auto &&data : sut_reverse_via_lambda)
std::cout << data << std::endl;
return 0;
}
出力は次のようになります。
### Default sort on std::set<std::string> :
1
2
23
290
5
6
### Custom sort on set :
1
2
5
6
23
290
### Lambda sort on set :
6
5
290
23
2
1
上記の例では、比較演算をstd::setに追加する3つの異なる方法を見つけることができ、それぞれがそれ自身のコンテキストで便利です。
デフォルトのソート
これは、キーの比較演算子（最初のテンプレート引数）を使用します。多くの場合、キーはstd::less<T>関数のための良いデフォルトを提供します。この関数が特殊化されていない限り、オブジェクトのoperator<を使用します。これは、他のコードもいくつかの順序を使用しようとする場合に特に便利です。これはコードベース全体の一貫性を可能にするためです。
このようにコードを書くと、キーが変更されたときにコードを更新するための労力が軽減されます。たとえば、2つのメンバーを含むクラスは3つのメンバーを含むクラスに変更されます。クラス内のoperator<を更新すると、すべてのオカレンスが更新されます。
ご想像のとおり、デフォルトのソートを使用するのが合理的なデフォルトです。
カスタムソート
比較演算子を使用してオブジェクトを介してカスタムソートを追加するのは、デフォルトの比較が準拠しない場合によく使用されます。上記の例では、文字列が整数を参照しているためです。それ以外の場合は、参照するオブジェクトに基づいて（スマートな）ポインタを比較する場合や、比較のために異なる制約が必要な場合に使用されることがあります（例： std::pairとfirstの値を比較）。
比較演算子を作成する場合、これは安定したソートでなければなりません。挿入後に比較演算子の結果が変更された場合、未定義の動作が発生します。良い習慣として、比較演算子は定数データ（constメンバー、const関数...）のみを使うべきです。
上記の例のように、メンバーを持たないクラスは比較演算子としてよく見かけるでしょう。これにより、デフォルトコンストラクタとコピーコンストラクタが生成されます。既定のコンストラクターでは、作成時にインスタンスを省略することができ、セットがcompare演算子のコピーをとるので、コピーコンストラクターが必要です。
ラムダソート
Lambdaは、関数オブジェクトを書くための短い方法です。これにより、比較演算子を少ない行に書くことができ、コード全体をより読みやすくします。
ラムダの使用の欠点は、各ラムダがコンパイル時に特定の型を取得することです。したがって、同じコンパイル単位（cppファイル）のコンパイルごとにdecltype(lambda)が複数のコンパイル単位）。このため、ヘッダーファイル内で使用された場合、比較オブジェクトとして関数オブジェクトを使用することをお勧めします。
この構造は、 std::setが関数のローカルスコープ内で代わりに使用されているときにしばしば遭遇しますが、関数の引数またはクラスのメンバーとして使用されるときは、関数オブジェクトが優先されます。
その他の並べ替えオプション
std::setのcompare演算子はテンプレート引数であるため、 呼び出し可能なオブジェクトはすべてcompare演算子として使用でき、上記の例は特定のケースのみです。これらの呼び出し可能オブジェクトには、次の制限があります。
- コピー可能なものでなければなりません
- それらは、キーの型の2つの引数で呼び出し可能でなければなりません。 （暗黙的な変換は許可されますが、パフォーマンスを低下させる可能性があるため推奨されません）
セットとマルチセットの値の検索
与えられた値をstd::setまたはstd::multiset検索するにはいくつかの方法があります：
キーの最初の出現のイテレータを取得するには、 find()関数を使用できます。キーが存在しない場合はend()返します。
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3); // contains 3, 10, 15, 22
auto itS = sut.find(10); // the value is found, so *itS == 10
itS = sut.find(555); // the value is not found, so itS == sut.end()
std::multiset<int> msut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(15);
sut.insert(3); // contains 3, 10, 15, 15, 22
auto itMS = msut.find(10);
別の方法が使用されるcount()多くの対応する値は、で発見されたかをカウントする機能、 set / multiset （の場合にset 、戻り値とすることができるだけ0または1）。上記と同じ値を使用すると、次のようになります。
int result = sut.count(10); // result == 1
result = sut.count(555); // result == 0
result = msut.count(10); // result == 1
result = msut.count(15); // result == 2
std::multiset場合、同じ値を持つ複数の要素が存在する可能性があります。この範囲を取得するには、 equal_range()関数を使用できます。 iteratorの下限（上限）と上限（上限）を持つstd::pairを返します。キーが存在しない場合、両方のイテレータは、（指定されたmultisetをソートするために使用されるcompareメソッドに基づいて）最も近い上位値を指します。
auto eqr = msut.equal_range(15);
auto st = eqr.first; // point to first element '15'
auto en = eqr.second; // point to element '22'
eqr = msut.equal_range(9); // both eqr.first and eqr.second point to element '10'
セットから値を削除する
最も明白な方法は、あなたのセット/マルチセットを空のものにリセットしたいのであれば、 clearを使うclearです：
std::set<int> sut;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.clear(); //size of sut is 0
次に、 erase方法を使用することができます。それは挿入と幾分同じようないくつかの可能性を提供します：
std::set<int> sut;
std::set<int>::iterator it;
sut.insert(10);
sut.insert(15);
sut.insert(22);
sut.insert(3);
sut.insert(30);
sut.insert(33);
sut.insert(45);
// Basic deletion
sut.erase(3);
// Using iterator
it = sut.find(22);
sut.erase(it);
// Deleting a range of values
it = sut.find(33);
sut.erase(it, sut.end());
std::cout << std::endl << "Set under test contains:" << std::endl;
for (it = sut.begin(); it != sut.end(); ++it)
{
std::cout << *it << std::endl;
}
出力は次のようになります。
Set under test contains:
10
15
30
これらのメソッドはすべてmultisetも適用されます。 multisetから要素を削除するように要求され、複数回存在する場合は、 すべての同等の値が削除されます。