Le 01/01/2014 22:54, Cooler a écrit :
Example in C++:
set<int> uniqueInts;
assert(uniqueInts.count(99) == 0);
uniqueInts.insert(99);
assert(uniqueInts.count(99) == 1);
uniqueInts.erase(99);
assert(uniqueInts.count(99) == 0);
Which it will be analogue solution in D?
I need a collection that can hold number of items, and can tell me
weather is an item in the collection or not. I found that RedBlackTree
can help me. But RedBlackTree uses O(log(n)) time for insert/remove
operations. On the other hand we have built-in associative arrays with
hashed keys. But associative arrays requires pairs of (key, value),
which is quite wasting in my case.
May be it will be convenient to allow void[key] built-in collections?
Any suggestion?
Hello,
I don't know if it fits with your needs, but I just pushed a library
for handling sets I wrote months ago.
It supports basic operations like adding, removing, testing the
presence of an object in the set, intersection, union, powerset,
difference, symmetric difference.
Sets can be untyped (it accepts elements of any type) or typed (more
efficient, accepts only elements of a given type like int).
If I'm not mistaken, complexity of insertion, presence checking and
removal is O(1).
You can get it here:
https://gitorious.org/set/set/
Feel free to ask question, make suggestions... if you have any.
Example of code:
import std.stdio;
import std.conv;
import set;
void main() {
auto S = new Set!();
S.add("hello");
S.add(42);
writeln(S);
writeln("has 42? ", S.contains(42));
writeln("has \"42\"? ", S.contains("42"));
writeln("has \"hello\"? ", S.contains("hello"));
S.remove("hello");
writeln(S);
writeln("has \"hello\"? ", S.contains("hello"));
writeln("address of 42 : ", S.addressOf(42));
auto E = new Set!int([1,2,3,4]); // it is possible to declare
an empty set
auto F = new Set!int([3,4,5,6]); // of int like this: auto G =
new Set!int;
writeln("union: ", E.Union(F));
writeln("inter: ", E.Inter(F));
writeln("symmetric difference: ", E.SymDiff(F));
writeln("minus: ", E.Minus(F));
writeln("Powerset: ", E.Powerset);
S.UnionInPlace(E);
writeln("Union in place: ", S);
// lets iterate over elements:
foreach (element ; S) {
write(element);
// beware, because S is an untyped set (Set!() or
Set!Object),
// type of element is Element.
// If you want the real value, cast to
Element!the_type_of_your_element
// and access to the e property of the class.
auto el = cast(Element!int)(element);
write(" (", el.e, ") ");
// el.e is an int
// Note that this works only because the only remaining
values in S
// are integer values. If another type were present in the
set, we
// would experience a segmentation fault.
}
writeln();
}
Expected output:
{hello, 42}
has 42? true
has "42"? false
has "hello"? true
{42}
has "hello"? false
address of 42 : 7F9323979F60
union: {4, 1, 5, 2, 6, 3}
inter: {4, 3}
symmetric difference: {1, 5, 2, 6}
minus: {1, 2}
Powerset: {{}, {4}, {1, 3}, {4, 1, 3}, {1}, {4, 1}, {2, 3}, {4, 2,
3}, {2}, {4, 2}, {1, 2, 3}, {4, 1, 2, 3}, {1, 2}, {4, 1, 2}, {3}, {4, 3}}
Union in place: {4, 1, 42, 2, 3}
4 (4) 1 (1) 42 (42) 2 (2) 3 (3)
Should Phobos have something similar built in?
Happy new year to everyone,
Raphaël.
