www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - removing element from DList

reply "Jack Applegame" <japplegame gmail.com> writes:
How to get range for single just inserted element?

DList!int list;
...
list.insertBack(5);
auto r = ??? // get range for single last element
...
list.insertBack(something);
...
list.remove(r);
Nov 05 2012
next sibling parent reply "Michael" <pr m1xa.com> writes:
On Monday, 5 November 2012 at 16:41:16 UTC, Jack Applegame wrote:

 How to get range for single just inserted element?

 DList!int list;
 ...
 list.insertBack(5);
 auto r = ??? // get range for single last element
 ...
 list.insertBack(something);
 ...
 list.remove(r);


Something like


auto r = list[$ - 1];
Nov 05 2012
parent reply "Jack Applegame" <japplegame gmail.com> writes:
On Monday, 5 November 2012 at 18:06:44 UTC, Michael wrote:

 Something like

 auto r = list[$ - 1];


Error: no [] operator overload for type DList!(int)
Nov 05 2012
parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, November 05, 2012 19:35:57 Jack Applegame wrote:

 On Monday, 5 November 2012 at 18:06:44 UTC, Michael wrote:

 Something like
 
 auto r = list[$ - 1];


 
 Error: no [] operator overload for type DList!(int)


The range returned by list isn't random access, and it can't be random access, 
so that won't work. Regardless, that would have given you the last element, 
not a range over just the last element. It would have to be list[$ - 1 .. $] 
to give you a range over just the last element, but that requires a sliceable 
random-access range (which DList's range can't be). If all you want is the 
last element, then use list[].back, since DList's range is bidirectional.

- Jonathan M Davis
Nov 05 2012
parent reply "Jack Applegame" <japplegame gmail.com> writes:
On Monday, 5 November 2012 at 19:31:25 UTC, Jonathan M Davis 
wrote:

 If all you want is the
 last element, then use list[].back, since DList's range is 
 bidirectional.

 - Jonathan M Davis


No. I want after inserting element, remember its "position" (in 
C++ I used iterator) and remove it later even if other elements 
was inserted after it.
Nov 05 2012
parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, November 05, 2012 21:59:05 Jack Applegame wrote:

 On Monday, 5 November 2012 at 19:31:25 UTC, Jonathan M Davis
 
 wrote:

 If all you want is the
 last element, then use list[].back, since DList's range is
 bidirectional.
 
 - Jonathan M Davis


 
 No. I want after inserting element, remember its "position" (in
 C++ I used iterator) and remove it later even if other elements
 was inserted after it.


If you're using insertBack like you're original post lists, then you know that 
it's at the back. However, unfortunately, DList made the choice of returning 
the number of elements inserted rather than a range starting at the element 
inserted, so if you want a range to that element, you're either going to have 
to do

auto range = retro(take(retro(list[]), 1));

or

typeof(list[]) targetRange = list[];

for(auto range = list[]; list.empty; list.popFront())
 targetRange = range.save;

The first is obviously more efficient, but it won't give you the same type as 
list[] (whether that matters depends on what you're doing). The second will 
given you the correct type but is obviously suboptimal and only works because 
you know that you inserted it at the end. If you were inserting in the middle 
somewhere, you'd have to use find to find the new element (which could be 
problematic if the list contains duplicates), or you'd have to somehow know 
how deep into the list the element is and pop that many elements from list[].

Personally, I think that it was a serious mistake for insert* to not return a 
range like C++ returns an iterator, but at least for the moment, that's what 
it does. The basic design for std.container is solid, but a number of the 
details definitely need some work, particularly since this is the first major 
attempt to have containers using ranges exclusively without anything like an 
iterator, and it's one area where ranges aren't always better than iterators.

- Jonathan M Davis
Nov 05 2012
prev sibling next sibling parent reply "cal" <callumenator gmail.com> writes:
On Monday, 5 November 2012 at 16:41:16 UTC, Jack Applegame wrote:

 How to get range for single just inserted element?

 DList!int list;
 ...
 list.insertBack(5);
 auto r = ??? // get range for single last element
 ...
 list.insertBack(something);
 ...
 list.remove(r);


http://forum.dlang.org/thread/cfkllwgfushidyuwzuwp forum.dlang.org
Nov 05 2012
parent "Jack Applegame" <japplegame gmail.com> writes:
On Monday, 5 November 2012 at 18:52:24 UTC, cal wrote:

 http://forum.dlang.org/thread/cfkllwgfushidyuwzuwp forum.dlang.org


I read it. It's absolutely useless for my question.
Nov 05 2012
prev sibling next sibling parent Tobias Pankrath <lists pankrath.net> writes:
On 05.11.2012 17:41, Jack Applegame wrote:

 How to get range for single just inserted element?

 DList!int list;
 ...
 list.insertBack(5);
 auto r = ??? // get range for single last element
 ...
 list.insertBack(something);
 ...
 list.remove(r);


There is no way to do that in constant time with current dlist 
interface. (You could do something like 
list[].drop(walkLength(list)-1).takeOne), which is embarrassing.

I think DList should offer a native backwards range, so that you can do 
list.retro.takeOne.
Nov 05 2012
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, November 05, 2012 17:41:15 Jack Applegame wrote:

 How to get range for single just inserted element?
 
 DList!int list;
 ...
 list.insertBack(5);
 auto r = ??? // get range for single last element
 ...
 list.insertBack(something);
 ...
 list.remove(r);


If you want to remove an element, do

auto range = find(list[], elem);
list.remove(take(range, 1));

Unfortunately, it looks like insert* makes the choice of returning the number 
of elements inserted instead of a range starting at the newly inserted element 
(C++ std::list returns an iterators pointing to that element, which seems a 
lot more useful to me). So, you can't easily get at a range to the most 
recently inserted element.

However, since you know that it's the last element, if you want to remove it, 
it's easy. Just use

list.removeBack();

If you want a range to the last element for something other than removing it, 
then you'd probably have to do something like

auto range = retro(take(retro(list[]), 1));

though that won't be the original range type. If you need that, you'd probably 
have to pop elements off until there's only one left (probably by saving before 
every pop and then returning the saved range when the range is empty).

- Jonathan M Davis
Nov 05 2012