Простая реализация набора в D?

Question

Я рылся в стандартной библиотеке D в поисках реализации Set, и нашел только эти:

• * 1004 двоичная куча *
• RedBlackTree

Они оба будут работать нормально, если бы я только мог понять, как их использовать. Я начал с RedBlackTree (потому что я уже знаком с тем, как они работают), и вот что я придумал:

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

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

Я знаю, что мог выполнить условие в первом foreach, но это всего лишь пример, показывающий, что мне нужно добавлять и удалять элементы из набора. Это будет работать, но я получаю ошибки компиляции:

Ошибка: шаблон std.container.RedBlackTree! (Строка) .RedBlackTree.removeKey (U) если (isImplicitlyConvertible! (U, Elem)) не соответствует ни одному объявлению шаблона функции

Ошибка: шаблон std.container.RedBlackTree! (Строка) .RedBlackTree.removeKey (U) if (isImplicitlyConvertible! (U, Elem)) не может вывести функцию шаблона из типов аргументов! () (Строка

Мне не нужно красно-черное дерево (ничего без дубликатов), и скорость не так уж важна. Я мог бы сделать что-то вроде этого:

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++;
    }
}

Есть ли в стандартной библиотеке что-нибудь для простого набора?

Answer 1

RedBlackTree - реализация Фобоса.Проблема, с которой вы сталкиваетесь с removeKey, заключается в том, что она разнообразна.Для удаления потребуется либо массив ключей, либо несколько ключей (например, removeKey(arr) или removeKey(key1, key2, key3)).string - это массив неизменяемых символов, поэтому он пытается создать экземпляр removeKey с char вместо string, что не работает, потому что ваше дерево содержит строки, а не символы.У вас не возникло бы такого рода проблем, если бы вы имели дело с RedBlackTree целыми числами или любым другим типом, не являющимся массивом.

Что вам нужно сделать, это либо дать ему массив строк, либо создать экземплярэто напрямую, то есть removeKey([s]) или removeKey!string(s).

Кстати, std.container пошел по пути именования своих типов контейнеров, основываясь на их структуре данных, а не на том, для чего они используются.Итак, когда вы говорите, что вам не нужно красно-черное дерево, это не совсем верно.Вы хотите набор.Тебе просто все равно, как это реализовано.Два типичных способа реализации наборов включают использование красно-черного дерева или хеш-таблицы.Итак, RedBlackTree дает вам один способ получить сет.Просто он назван в честь своей структуры данных, а не как вы можете его использовать, поэтому, если вы ищете имя контейнера Set в std.container, вы не найдете его.

EDIT : отчет об ошибке существует для этого, и исправление было отправлено.Таким образом, в будущем выпуске dmd должна быть возможность передать string в removeKey без необходимости его непосредственного создания или передачи string внутрь массива.

Answer 2

Не то, что я знаю.

Лучше всего просто использовать хеш-таблицу по ключам (bool[key] yourTable;) и игнорировать значения.

Answer 3

Улучшив предложение Мехрдада об использовании 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");

Answer 4

Я знаю, по крайней мере, один: http://www.dsource.org/projects/dcollections