Say I have a DList. I am looking for a vanilla way to insert/remove elements in place while traversing that list.

import std.container : DList;

struct myType{
   int id;
   // [...] other stuff
}

auto list = DList!myType();

// [...] populate list with elements

To remove the element with id=3 I can do:

list.linearRemove(list[].find!(a => a.id==3).take(1));

but according to this post linearRemove might be less efficient than remove and remove can't be used. Also in the example above, finding the needle is easy but my case would involve more complicated scenarios that I am relunctant to bury into find's predicate.

I would like to do something like traversing a DList, operating on the current element, and potentially removing that element or inserting a new one before/after it - an easy operation if you code a DList yourself. Maybe I missed something?

// Traverse and operate on current element
foreach(element; list)
{
    // [...] do something long and complicated with m, throw a random number rand

    if(rand < 0.5)
        list.removeInPlace(); // remove 'element'
    else
        list.insertInPlace(myType(...)); // insert a new element "here" (before/after 'element')
}

Any way to achieve this simply with D? E.g. is there a way to extract the 'reading head' of a list being traversed and to use that head as a range into the remove, insertAfter, insertBefore functions?

ok there is the issue of not knowing how to traverse the list after removing the current element (=> the one that came after of course). But how about even just keeping a pointer (range) to 'element' that can be used after the list has been traversed in full to use in remove / insertAfter?

I think I can achieve this with associative arrays (below) but it seems overkill to use an associative effectively as a DList?

struct myType{
    int id;
    int prev, next; // id of prev and next
    // [...] other stuff

    this(int id_, int prev_, int next_)
    {
        //[...]
    }
}

myType[int] list; // key = id

int[] to_remove;
myType[] to_add;

foreach(elem; list)
{
    // [...] do something long and complicated with elem, throw a random number rand

    if(rand < 0.5)
        to_remove ~= elem.id; // flag for removal
    else
        to_add ~= myType(some_new_id, elem.id, elem.next); // add new elem after current
}

foreach(elem; to_add)
    list[elem.id] = elem;

foreach(id; to_remove)
{
    // reconnect: prev's next to next, and next's prev to prev
    list[list[id].prev].next = list[id].next;
    list[list[id].next].prev = list[id].prev;
    list.remove(id);
}

On Sunday, 19 March 2023 at 13:15:58 UTC, Armando wrote:

This is one way to do that:

import std;

struct MyType
{
    int id;
    // [...] other stuff
}

void main()
{
    auto list = DList!MyType();

    // Fill the list.
    foreach (i; 0 .. 10)
        list.insertBack(MyType(i));

    // Traverse the list, conditionally remove one element.
    for (auto range = list[]; !range.empty;)
        if (range.front.id == 3)
            list.popFirstOf(range);
        else
            range.popFront();

    // Traverse the list, conditionally insert one element.
    for (auto range = list[]; !range.empty;)
    {
        if (range.front.id == 6)
            list.insertBefore(range, MyType(66));
        range.popFront();
    }

    // Print modified list.
    foreach (e; list)
        writeln(e);

}

Output:

MyType(0)
MyType(1)
MyType(2)
MyType(4)
MyType(5)
MyType(66)
MyType(6)
MyType(7)
MyType(8)
MyType(9)

https://run.dlang.io/is/kk80FD

-- Bastiaan.

Wonderful, that works like a treat, thank you so much! For those who wonder, inserting after works too:

  for (auto range = list[]; !range.empty;)
    {
        if (range.back.id == 8)
            list.insertAfter(range, MyType(88));
        range.popBack();
    }

which will give

MyType(0)
MyType(1)
MyType(2)
MyType(4)
MyType(5)
MyType(66)
MyType(6)
MyType(7)
MyType(8)
MyType(88)
MyType(9)

On Monday, 27 March 2023 at 15:05:16 UTC, Armando wrote:

Very cool! Thanks for asking and sharing! :)