I currently have my own implementations of gc free containers, but it would be nice to switch to a more "widely" used library.

But I would need the containers to be move aware, so that you can have DynamicArray!(Unique!Foo) for example.

Thoughts?

Parameter ContainerName in

void testEMSIContainer(alias Container, string ContainerName)()
{
    Allocator allocator;
    auto c = Container!(int, typeof(&allocator))(&allocator);
    StopWatch sw = StopWatch(AutoStart.yes);
    foreach (i; 0 .. NUMBER_OF_ITEMS)
        c.insert(i);
    sw.stop();
    writeln("Inserts for ", ContainerName, " finished in ",
        sw.peek().to!("msecs", float), " milliseconds.");
}

and testPhobosContainer can be removed and its usage can be replaced by Container.stringof

as

void testEMSIContainer(alias Container)()
{
    Allocator allocator;
    auto c = Container!(int, typeof(&allocator))(&allocator);
    StopWatch sw = StopWatch(AutoStart.yes);
    foreach (i; 0 .. NUMBER_OF_ITEMS)
        c.insert(i);
    sw.stop();
    writeln("Inserts for ", Container.stringof, " finished in ",
        sw.peek().to!("msecs", float), " milliseconds.");
}

TTree.Node.height() returns ulong, but inside of TTree.Node.calcHeight() a variable is declared as type size_t, causing compile errors on 32-bit systems.

See dlang-community/DCD#310

There is way to have allocators works with all compilers, we did it for logger here: burner/logger#22 to support multiple D front-ends.

• create a DUB package with std.experimental.allocatorexcept renamed to std.historical.allocator (this avoid samey import conflicts with newer compilers)
• instead of private import std.experimental.allocator.mallocator : Mallocator;, use

static if (front-end >= 2.069)
    import std.experimental.allocator;
else
    import std.historical.allocator;

I've checked and this isn't a problem for now but will be once a new DMD is out with allocators.
Such a package could be useful for other projects and would allow to compile allocators only once.

This would help make it a drop in replacement for GC arrays.

It should just return false.

0.4.2 does not build with the current ldc, master does @Hackerpilot could you release 0.4.3?

See recent comments on dlang-community/DCD#219 and dlang-community/DCD#310

Function like HashMap.keys is trying to cast from const(K) to K. When K contains reference, this won't work.

My idea is to return const(K)[] instead in that case.

something like this ?

   void opSliceAssign(T[] values, size_t i, size_t j) @nogc
    {
            assert(values.length==j-i);
            foreach(k,value;values)
                    arr[i+k]=value;
    }

And delegate can add to support . i think it same as isDynamicArra, but shoudl be null, when don't use.

Using allocator branch of Andrei's Phobos fork:
https://github.com/andralex/phobos.git

and DMD v 2.068

just copying over the std.experimental code and using stock Phobos otherwise I have a problem compiling (arch linux 64):

Compiling using dmd...
phobos/std/experimental/allocator/building_blocks/allocator_list.d(307,20): Error: no property 'expand' for type 'shared(Mallocator)'
phobos/std/experimental/allocator/building_blocks/allocator_list.d(529,28): Error: template instance std.experimental.allocator.building_blocks.allocator_list.AllocatorList!(Factory, Mallocator) error instantiating
src/app.d(14,19): instantiated from here: AllocatorList!((a) => Region!Mallocator(1024 * 16), Mallocator)
FAIL .dub/build/application-debug-linux.posix-x86_64-dmd_2068-847B9437DBA5F4B7C25C9B215DF0D8E9/ containers executable
Error executing command build:
dmd failed with exit code 1.

any suggestions?

How hard would it be to make these containers concurrent? A few locks here and there would do. A user defined lock could be used so only locking is needed, which also could be statically compiled in if the user defined lock is specified. (So no locking method specified = single threaded, else multi-threaded)

See unit test in pull request #66.

unittest
{
    static class Foo
    {
        string name;
    }

    hash_t stringToHash(string str) @safe pure nothrow @nogc
    {
        hash_t hash = 5381;
        return hash;
    }

    hash_t FooToHash(in Foo e) pure @safe nothrow @nogc
    {
        return stringToHash(e.name);
    }

    HashSet!(const(Foo), Mallocator, FooToHash) hs;
    const(Foo) f = new const Foo;
    hs.insert(f);
    assert(f in hs);
    auto r = hs.range();
}

not sure why this does not work. I test Rebindable separately and it work.

struct HStorage
{
	import containers.dynamicarray: DynamicArray;

	DynamicArray!int storage;
}

@nogc
unittest
{
	auto hs = HStorage();	
}

fails with

Error: @nogc function 'hstorage.__unittestL11_10' cannot call non-@nogc destructor 'hstorage.HStorage.~this'

https://dlang.org/changelog/2.078.0.html#fix16997
https://forum.dlang.org/post/[email protected]

The online documentation under http://economicmodeling.github.io/containers/index.html
is not up to date. At lest CyclicBuffer is missing.

When the TreeMap has only one entry (left), remove will trigger an assertion failure on ttree.d, line 48.

Code to reproduce:

import std.stdio;
import containers.treemap;

void main()
{
    TreeMap!(string, string) tm;

    // add two entries
    tm["test1"] = "hello";
    tm["test2"] = "world";

    // iterate: show two
    foreach(key, value; tm)
        writeln(key, " -> ", value);

    // remove one
    tm.remove("test1");

    // iterate: show one
    writeln("\niterating:");
    foreach(key, value; tm)
        writeln(key, " -> ", value);

    // remove the last one
    tm.remove("test2"); // this will crash with assertion failed, ttree.d (48)
}

This example:

void main()
{
 static struct Foo {}
 import containers.hashset : HashSet;
 HashSet!Foo set; 
}

Fails to compile with:

......\Users\x\AppData\Roaming\dub\packages\emsi_containers-0.5.3\emsi_containers\src\containers\hashset.d(503): Error: cast(BucketNode*)current is not an lvalue
......\Users\x\AppData\Roaming\dub\packages\emsi_containers-0.5.3\emsi_containers\src\containers\hashset.d(337): Error: cast(Bucket[])oldBuckets is not an lvalue
..\source\app.d(76): Error: template instance containers.hashset.HashSet!(Foo, Mallocator, generateHash, false) error instantiating

moveEmplaceAll is used in CyclicBuffer, which was introduced in 2.069, so now this cannot be built with LDC 0.17.0.

Now, It not support 。
so when I use the RC struct, it will error.
I think it should and can support.

From dlang-community/D-Scanner#458 (comment)

Btw don't mind the test failure on dmd-nightly for now - it's a known regression in EMSI containers.
Anyway, I think we should also bring emsi_containers to the org, so we can more easily manage such issues.

@Hackerpilot what's your opinion on this?

while working on remove for DynamicArray I ran into a problem.

class Cls {
    int* a;

    this(int* a) {
        this.a = a;
    }

    ~this() {
        ++(*a;)
    }
}

unittest {
    int a = 0;
    {
        DynamicArray!(Cls) arr;
        arr.insert(new Cls(&a));
    }
    assert(a == 1); // this fails
}

the dtor of the on cls is not called. Is this by design? I would say the typeof(T).destory in DynamicArray.dtor suggests otherwise.

Have to use writeln(hashset[]).

is this design on purpose?

for TreeMap (and others if applic) add .keys

so foreach(itemKey;container.keys)

Not a big deal since you can iterate by key/value pair.

I have UnrolledList and I want to traverse this list in reverse order, but when I try to run this code:
foreach_reverse (Widget widget; widgetOrdering)
I get an error:

invalid foreach aggregate this.widgetOrdering, define opApply(), range primitives, or use .tupleof

Also container doesn't have method insertFront.

unittest
{
    HashMap!(string, int) map;
    map.insert("foo", 0);
    map.insert("bar", 0);

    foreach(const(string) key, ref int value; map) {
        value = 1;
    }

    foreach(const(string) key, ref int value; map) {
        assert(value == 1);
    }
}

reason: https://github.com/economicmodeling/containers/issues/53

Follow the same interface as built-in AAs: return the value for a key or a default value if the key is not present.

One line fix: alias opDollar = length;

"inout" type are considered as immutable in that template.

containers/src/containers/ttree.d(193): Error: redundant attribute 'const'

I thought that attribute inference would let HashMap be @nogc when using Mallocator?

Error: @nogc function 'dplug.gui.font.Font.getGlyphCoverage' cannot call non-@nogc function 'containers.hashmap.HashMap!(GlyphKey, Image!(Color!(ubyte, "l")), Mallocator, generateHash, true).HashMap.opBinaryRight!"in".opBinaryRight'

Should return a range of tuples with named members

unittest
{
    UnrolledList!int list;
    list.insert(0);
    list.insert(0);
    list.insert(0);
    list.insert(0);
    list.insert(0);

    foreach(ref it; list.range) {
        it = 1;
    }

    foreach(it; list.range) {
        assert(it == 1);
    }
}

I think UnrolledList!int.Range.front needs to return ref int . But ref is sort of f*** up so I can't simple cast to ref int. @Hackerpilot ideas?

p.s. This only affects value types.
p.s.s HashMap is also affected

For example, HashMap doesn't have .byKey, .byValue, HashSet doesn't have opApply, etc.

Are those deliberately left out, or are there plans to implement them in the future? If it's the latter case, are you accepting pull requests? I really want to contribute to this project.

In HashSet.Bucket.insert. Not all BucketNodes are checked for duplication before insert.

i.e. the loop should look like this:

for (BucketNode* current = root; current !is null; current = current.next)
    if (current.get(n) !is null)
        return false;
for (BucketNode* current = root; current !is null; current = current.next)
    if (current.l < current.items.length)
    {
        current.insert(n);
        return true;
    }

HashMap!(string,string) hm;

foreach(ref string key, ref string value) {
    key = "WAT";  // this assignment should not be possible
}

also foreach (opApply) does not work for const(HashMap)

and opApply does not work with safe code

unittest
{
    HashMap!(string, int) map;
    map.insert("foo", 0);
    map.insert("bar", 0);

    foreach(key; map.keys()) {
        map[key] = 1;
    }

    foreach(const(string) key, ref int value; map) {
        assert(value == 1);
    }
}

reason: https://github.com/economicmodeling/containers/issues/53

Returning a container from a function is currently not allowed because of

this(this) @disable;

Is there a reason for this?

I'm trying to put a class into a HashSet but it keeps telling me something are not nothrow even though the code I created is nothrow. Maybe it's to late right now or I'm just stupid. Anyway, I could need some help.

import containers.hashset;

import std.experimental.allocator.mallocator : Mallocator;

private hash_t stringToHash(string str) @safe pure nothrow @nogc {
    hash_t hash = 5381;
    return hash;
}

hash_t FooToHash(Foo e) pure @safe nothrow @nogc {
    return stringToHash(e.name);
}

class Foo {
    string name;
}

void main() {
    HashSet!(Foo, Mallocator, FooToHash) hs;
}