www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Inserting and removing elements from a sorted container

reply Dirk <dirk email.address> writes:
Hi!

I want to add an uint into a container, but avoid duplicate 
uints, similar to a set<> from C++ STL.

To find out if an uint is already present in the container, it 
would make sense if the container is sorted.

This is some pseudo-D-code that should make clear what i want to 
do:

auto sortedlist = SList!uint(1, 2, 3, 5);
uint newValue = 4;
bool appendValue = true;
foreach( i; sortedlist[] ) {
     if( value == i ) {
         // value already in list
         appendValue = false;
         break;
     }
     if( i > newValue ) {
         // value not there. Insert value in front of i
         sortedlist.insertBefore(i, newValue);
         appendValue = false;
     }
}
if( appendValue )
     sortedlist.append( newValue );

Can someone help me?

Thank you,
Dirk
Nov 19
parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Sunday, November 19, 2017 13:41:51 Dirk via Digitalmars-d-learn wrote:
 Hi!

 I want to add an uint into a container, but avoid duplicate
 uints, similar to a set<> from C++ STL.

 To find out if an uint is already present in the container, it
 would make sense if the container is sorted.

 This is some pseudo-D-code that should make clear what i want to
 do:

 auto sortedlist = SList!uint(1, 2, 3, 5);
 uint newValue = 4;
 bool appendValue = true;
 foreach( i; sortedlist[] ) {
      if( value == i ) {
          // value already in list
          appendValue = false;
          break;
      }
      if( i > newValue ) {
          // value not there. Insert value in front of i
          sortedlist.insertBefore(i, newValue);
          appendValue = false;
      }
 }
 if( appendValue )
      sortedlist.append( newValue );

 Can someone help me?

 Thank you,
 Dirk
I'd suggest that you use std.container.rbtree..RedBlackTree. A red-black tree exactly the sort of data structure that is typically used in a sorted set. - Jonathan M Davis
Nov 19
parent reply Dirk <dirk email.address> writes:
On Sunday, 19 November 2017 at 16:05:53 UTC, Jonathan M Davis 
wrote:
 I'd suggest that you use std.container.rbtree..RedBlackTree. A 
 red-black tree exactly the sort of data structure that is 
 typically used in a sorted set.

 - Jonathan M Davis
Thank you, i will look into it. I have a question related to ranges: An input range has an interface like this: struct inputRange { void popFront(); property bool empty(); property int front(); } So if i use a foreach loop to iterate over all elements of a range, i would expect the range to shrink for every iteration: auto list = SList!uint(1,2,3); auto range = list[].save(); foreach( i; range ) { writeln(range); } Expected output: [1,2,3] [2,3] [3] But i get: [1,2,3] [1,2,3] [1,2,3] Why don't i see the expected output? Thank you, Dirk
Nov 19
parent reply Jonathan M Davis <newsgroup.d jmdavisprog.com> writes:
On Sunday, November 19, 2017 16:48:00 Dirk via Digitalmars-d-learn wrote:
 On Sunday, 19 November 2017 at 16:05:53 UTC, Jonathan M Davis

 wrote:
 I'd suggest that you use std.container.rbtree..RedBlackTree. A
 red-black tree exactly the sort of data structure that is
 typically used in a sorted set.

 - Jonathan M Davis
Thank you, i will look into it. I have a question related to ranges: An input range has an interface like this: struct inputRange { void popFront(); property bool empty(); property int front(); } So if i use a foreach loop to iterate over all elements of a range, i would expect the range to shrink for every iteration: auto list = SList!uint(1,2,3); auto range = list[].save(); foreach( i; range ) { writeln(range); } Expected output: [1,2,3] [2,3] [3] But i get: [1,2,3] [1,2,3] [1,2,3] Why don't i see the expected output?
foreach(e; range) { ... } gets lowered to something like for(auto __range = range; !__range.empty; __range.popFront()) { auto e = __range.front; ... } So, the range gets copied when it's used with foreach. foreach then consumes the copy. If a range is a value type such that copying the range is equivalent to calling save on a forward range, then using the range with foreach implicitly saves it, and so you iterate over a separate copy, and if you then iterate over the original, then it continues to iterate from wherever it was. However, if the range is a reference type, then copying the range just copies its reference rather than implicitly saving it, and when you try to iterate over the original, it won't work, because it's empty. And if the range is a pseudo-reference type such that copying the range does not simply copy a reference, and copying the range is not the same as calling save, then if you try to iterate over the original after copying the range with foreach will result in really weird behavior. So, in the general case, you should never use a range again after having copied it. It will work in some cases, but in others, it will fail miserably - potentially in very weird ways. So, if you want to iterate over a range with foreach and then do something with the range afterwards, call save when you pass it to foreach. e.g. foreach(e; range.save) { ... } though if you're just grabbing the range from a container, you can just use the container in foreach. e.g. foreach(e; container) { ... } The compiler implicitly calls [] on the container to get its range. So, it would be equivalent to foreach(e; container[]) { ... } Also, I would point out that your use of save in your example doesn't really make sense:
 auto list = SList!uint(1,2,3);
 auto range = list[].save();
list[] will give you a fresh range every time you call it. You only need to be calling save if you already have a range and want an indepedent copy to iterate over. e.g. auto list = SList!uint(1, 2, 3); auto range = list[]; range.popFront(); foreach(e; range.save) writeln(e); // prints 2 and then 3 writeln(range.save); // prints [2. 3] On a side note, you should be calling save without parens. In most cases, with parens will work, but the range API specifically treats save like a property (much as that doesn't really make sense, since save doesn't fit the typical definition of what a property is), so it's technically possible for someone to implement a range where save is a variable (which would be really weird, but as long as copying it then resulted in range.save giving you a range that was the same as the original range, it would work). I wouldn't expect you to have problems calling save with parens in practice, but it's best to use range primitives in the way that isInputRange, isForwardRange, etc. test for them (the code that they test should be in the docs). For other range primitives, it really does matter in practice (e.g. empty is typically a function for most ranges but for infinite ranges, it's an enum, so if you call it with parens, some ranges will fail to compile with your code). So, it's best to get in the habit of calling them the same way that the range API traits call them - which for forward ranges, means front, empty, length, popFront(), and save. - Jonathan M Davis
Nov 19
parent Dirk <dirk email.address> writes:
Thank you very much for your thorough answer!

/Dirk
Nov 19