- 追加された行はこの色です。
- 削除された行はこの色です。
#blog2navi()
*C#: SortedList や SortedDictionary における特定値未満・以下・以上・超のキーを持つ要素の取得 [#k7eaad8b]
C#の @code{SortedList<TKey, TValue>}; ジェネリッククラスや @code{SortedDictionary<TKey, TValue>}; ジェネリッククラスには、C++の @code{std::map}; テンプレートクラスにあるメンバ関数 @code{lower_bound}; や @code{upper_bound}; に相当するメソッドがありません。~
ではどうするのかというと、 .NET Framework 3.5 & C# 3.0 以降では @code{IEnumerable<T>}; インタフェースに対する拡張メソッドである @code{FirstOrDefault}; および @code{LastOrDefault}; を使います。
#code(csharp){{
// using System.Linq; が必要です。
/// <summary>
/// 指定したキーの前後にある要素を取得する。
/// </summary>
/// <typeparam name="TKey">キーの型。</typeparam>
/// <typeparam name="TValue">値の型。</typeparam>
/// <param name="sortedList">キーでソートされたリスト。</param>
/// <param name="key">検索対象のキー。</param>
/// <param name="lessThan">key より小さいキーを持つ直近の要素。</param>
/// <param name="lessEqual">key 以下のキーを持つ直近の要素。</param>
/// <param name="greaterEqual">key 以上のキーを持つ直近の要素。</param>
/// <param name="greaterThan">key より大きいキーを持つ直近の要素。</param>
/// <param name="comparer">
/// 比較子。既定の比較子を用いるならば null 。
/// </param>
/// <remarks>
/// いずれの out 引数も、要素が見つからなければ
/// default(KeyValuePair{TKey, TValue}) が設定される。
/// </remarks>
void GetBoundKeys<TKey, TValue>(
IEnumerable<KeyValuePair<TKey, TValue>> sortedList,
TKey key,
out KeyValuePair<TKey, TValue> lessThan,
out KeyValuePair<TKey, TValue> lessEqual,
out KeyValuePair<TKey, TValue> greaterEqual,
out KeyValuePair<TKey, TValue> greaterThan,
IComparer<TKey> comparer = null)
{
// comparer が null なら既定の比較子を用いる
var comp = comparer ?? Comparer<TKey>.Default;
lessThan =
sortedList.LastOrDefault(
kv => comp.Compare(kv.Key, key) < 0);
lessEqual =
sortedList.LastOrDefault(
kv => comp.Compare(kv.Key, key) <= 0);
greaterEqual =
sortedList.FirstOrDefault(
kv => comp.Compare(kv.Key, key) >= 0);
greaterThan =
sortedList.FirstOrDefault(
kv => comp.Compare(kv.Key, key) > 0);
}
}}
拡張メソッド @code{FirstOrDefault}; は、条件に合致する(=引数のデリゲートが @code{true}; を返す)''最初''の要素を返します。~
拡張メソッド @code{LastOrDefault}; は、条件に合致する(=引数のデリゲートが @code{true}; を返す)''最後''の要素を返します。~
いずれのメソッドも見つからなかった場合は要素型の既定値(上述のコードならば @code{default(KeyValuePair<TKey, TValue>)};)を返します。
要素が存在するとわかっている場合には拡張メソッド @code{First}; および @code{Last}; も使えます。~
こちらはリストが空である場合や要素が見つからなかった場合に例外をスローします。
なお、どのメソッドにもデリゲートを引数に取らないオーバロードがあり、そちらは単純にリスト内で一番最初および一番最後の要素を返します。
:追記|
当然ながらこれらのメソッドは対象のリストがソート済みであることを考慮してはくれません。~
二分探索法などを駆使したい場合は自前でコーディングする必要があるでしょう。
RIGHT:Category: [[[プログラミング>ぼやきごと/カテゴリ/プログラミング]]][[[C#>ぼやきごと/カテゴリ/C#]]] - 2013-03-16 18:10:21
----
RIGHT:&blog2trackback();
#comment(above)
#blog2navi()