6

私はDの標準ライブラリでSetの実装を探していましたが、次のものしか見つかりませんでした。

  • BinaryHeap
  • RedBlackTree

使い方がわかれば、どちらも問題なく動作します。私はRedBlackTreeから始めました（私はすでにそれらがどのように機能するかを知っているので）、そしてこれは私が思いついたものです：

auto rbt = redBlackTree!string();
foreach(s; setOfStrings) {
    rbt.insert(s);
}

foreach(s; rbt) {
    if (s[0 .. 3] == "sth") {
        rbt.removeKey(s);
    }
}

最初のforeachで条件を実行できたはずですが、これは、セットに要素を追加したり、セットから要素を削除したりする必要があることを示す単なる例です。これは機能しますが、コンパイルエラーが発生します。

エラー：template std.container.RedBlackTree！（string）.RedBlackTree.removeKey（U）if（isImplicitlyConvertible！（U、Elem））がどの関数テンプレート宣言とも一致しません

エラー：template std.container.RedBlackTree！（string）.RedBlackTree.removeKey（U）if（isImplicitlyConvertible！（U、Elem））は、引数の型からテンプレート関数を推測できません！（）（string

赤黒木（重複のないもの）は必要ありません。速度はそれほど重要ではありません。私はこのようなことをすることができます：

string[] arr;
foreach(s; setOfStrings) {
    // check for duplicate code here...

    arr ~= s;
}
for(int i = 0; i < arr.length; i++) {
    if (s[0 .. 3] == "sth") {
        arr = arr[0 .. i] ~ arr[i + 1 .. $];
        i++;
    }
}

単純なセットの標準ライブラリに何かありますか？

4

4 に答える 4

7

RedBlackTreePhobosのセット実装です。あなたが遭遇している問題removeKeyは、それが可変個引数であるという事実です。削除するには、キーの配列または複数のキー（removeKey(arr)またはremoveKey(key1, key2, key3)）が必要です。stringは不変の文字の配列であるため、の代わりにインスタンス化removeKeyを試みますが、これは機能しません。これは、ツリーが文字ではなく文字列を保持しているためです。intやその他の非配列型を扱っている場合は、この種の問題は発生しません。charstringRedBlackTree

あなたがする必要があるのは、それに文字列の配列を与えるか、それを直接インスタンス化することですすなわちremoveKey([s])またはremoveKey!string(s)。

ちなみに、std.containerは、使用目的ではなく、データ構造に基づいてコンテナタイプに名前を付ける方法を採用しています。ですから、赤黒木は必要ないと言うとき、それは正しくありません。セットが必要です。あなたはそれがどのように実装されているかを気にしません。セットを実装する2つの一般的な方法には、赤黒木またはハッシュテーブルのいずれかを使用することが含まれます。だから、RedBlackTreeあなたにセットを持っている1つの方法を与えます。使用方法ではなく、データ構造にちなんで名付けられているだけなのでSet、std.containerでコンテナ名を探している場合は、見つかりません。

編集：これに関するバグレポートが存在し、修正が提出されました。したがって、dmdの将来のリリースでは、直接インスタンス化したり、配列内でinを渡したりすることなく、 stringtoを渡すことができるようになるはずです。removeKeystring

于 2011-12-11T02:30:31.523 に答える
4

私が知っていることではありません。

最善の策は、キー（bool[key] yourTable;）でハッシュテーブルを使用し、値を無視することです。

于 2011-12-11T01:54:58.713 に答える
1

私は少なくとも1つ知っています：http ：//www.dsource.org/projects/dcollections

于 2011-12-11T02:02:57.930 に答える
1

Mehrdadの使用の提案を改善し、を使用することでbool[key]スペースの浪費を回避できますbyte[0][key]。 byte[0]サイズがゼロの静的配列であるため、スペースを使用しない型です。使用法：

byte[0][string] mySet;

// Insert an element.
mySet["foo"] = (byte[0]).init;

// Lookup
assert("foo" in mySet);

// Remove
mySet.remove("foo");
于 2011-12-11T17:37:44.970 に答える