www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - std.collection - changing the collection while iterating

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
While I work on making std.allocator better, here's some food for 
thought regarding std.collection.

Consider a traditional container with reference semantics, Java-style. 
Regarding changing the collection (e.g. adding/removing elements) while 
iterating, we have the following possibilities:

1. Leave it undefined, like the STL does. Probably this is too extreme.

2. Throw an exception if a remove is attempted while ranges exist. This 
works but it's conservative - e.g. it throws even if those ranges are 
never to be used again etc.

3. Allow the removal but throw from the ranges if there's any attempt to 
use a range following a remove.

4. Make it work such that ranges continue to be valid post removal. 
Perhaps this is on the inefficient side.


Andrei
Jun 21 2015
next sibling parent reply "H. S. Teoh via Digitalmars-d" <digitalmars-d puremagic.com> writes:
On Sun, Jun 21, 2015 at 04:02:43PM -0700, Andrei Alexandrescu via Digitalmars-d
wrote:
 While I work on making std.allocator better, here's some food for
 thought regarding std.collection.
 
 Consider a traditional container with reference semantics, Java-style.
 Regarding changing the collection (e.g. adding/removing elements)
 while iterating, we have the following possibilities:
Modifying a container while iterating over it generally will always have counterintuitive behaviour, even if well-defined (in general, it's ill-defined because it depends on implementation details), unless you restrict it to a very narrow set of permissible modifications. Consider, for instance, a simple linked-list of 5 elements: A -> B -> C -> D -> E Suppose you're iterating over this list, and have a reference (or range, or whatever, it's not important what) to, say, C: A -> B -> C -> D -> E ^ currentPtr Let's say we decide to delete C. Since this is a linked list, deleting C will modify the .next pointer from B to point to D instead. A -> B -> D -> E C ^ currentPtr Depending on the implementation, C.next may be reset to null, which causes the iteration over the list to terminate prematurely, since currentPtr.next is null, and it has no way to find where the logically-next element D is. Therefore, the iteration sequence will be A, B, C, instead of the intuitively-expected A, B, C, D, E. To solve this problem, we may cache the successor of C in currentPtr, so that we know to go to D next. However, this also breaks down if we delete *both* C and D while currentPtr is at C. It will result in the iteration sequence A, B, C, D instead of the expected A, B, C, E. Linked-lists are relatively simple, so there may be a way to get "consistent" (i.e., intuitive) behaviour from modifying it in the middle of an iteration, but this breaks down when dealing with more complex containers, say an unordered AA. Iterating over an AA, in theory, should give you the elements in some implementation-defined order. However, if the AA is modified while in the middle of iteration, all sorts of strange things may happen: deleting or inserting an element may cause an AA rehash, which completely changes the sequence of iteration. The current iteration may, as a result, miss some elements or repeat elements that have already been processed earlier. Some newly-added elements may be visited by the current iteration but others not, because they hashed to an earlier address than the current bucket. If you have multiple ranges iterating over the container at different rates, the story becomes a whole lot more complex, and counterintuitive behaviour is almost guaranteed.
 1. Leave it undefined, like the STL does. Probably this is too
 extreme.
It may be extreme, but it also seems sanest, since it avoids treading in the dangerous territory of strange and counterintuitive behaviours when a container is modified in the middle of an iteration.
 2. Throw an exception if a remove is attempted while ranges exist.
 This works but it's conservative - e.g. it throws even if those ranges
 are never to be used again etc.
This is too straitjacketed.
 3. Allow the removal but throw from the ranges if there's any attempt
 to use a range following a remove.
This is also too extreme. If I'm iterating over a linked-list on the 50th element, there is no reason why deleting the first element of the list should cause an exception when I later want to visit the 51st element.
 4. Make it work such that ranges continue to be valid post removal.
 Perhaps this is on the inefficient side.
[...] As I pointed out above, this is not only inefficient, but also hard (if not impossible) to define in any way that behaves consistently in every scenario. Basically, if you allow arbitrary modification of a container while iterating over it, you will always run into some corner case that behaves counterintuitively, no matter what you do. Thankfully, if we restrict the scope of container modifications to the current element being iterated over, then there is a way to do things consistently (I believe the container library written by a forum member does this). However, this requires explicit container support, and may or may not work if you have multiple ranges iterating over the container simultaneously. It will probably introduce inefficiencies. Arbitrary container modification and iteration simply don't mix. T -- They pretend to pay us, and we pretend to work. -- Russian saying
Jun 21 2015
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/21/15 4:55 PM, H. S. Teoh via Digitalmars-d wrote:
1. Leave it undefined, like the STL does. Probably this is too
extreme.
It may be extreme, but it also seems sanest, since it avoids treading in the dangerous territory of strange and counterintuitive behaviours when a container is modified in the middle of an iteration.
One important pursuit about std.collection is they're safe. -- Andrei
Jun 21 2015
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Sunday, 21 June 2015 at 23:58:38 UTC, H. S. Teoh wrote:
 On Sun, Jun 21, 2015 at 04:02:43PM -0700, Andrei Alexandrescu 
 via Digitalmars-d wrote:
 3. Allow the removal but throw from the ranges if there's any 
 attempt to use a range following a remove.
This is also too extreme. If I'm iterating over a linked-list on the 50th element, there is no reason why deleting the first element of the list should cause an exception when I later want to visit the 51st element.
Which is why I would suggest that we consider the issue from the perspective of iterator/range invalidation. If the operation that you did on the container does not alter the number of elements in the range or which elements it refers to, then that range should still be considered valid and work exactly as it would have had the container operation not taken place. But if it _does_ alter the range, then the range should be considered invalidated, and it should be a logic error to continue to iterate over that range at that point. That's basically how it's dealt with in C++. It's just that what happens when you iterate using an invalidated iterator is undefined behavior, and we could choose to throw an Error in that case if we wanted to be more user-friendly. That would generally result in a slight performance hit, but it would probably be minimal enough to be worth the extra gain in bug-catching. But programmers need to understand how the containers they're using work and what sort of operations make sense when you're iterating over them. I don't see how we could reasonably say otherwise. But I agree that considering all ranges for a container invalid just because you removed an element from that container regardless of whether that would affect those ranges is definitely too extreme.
 Arbitrary container modification and iteration simply don't mix.
Agreed. - Jonathan M Davis
Jun 21 2015
prev sibling next sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu 
wrote:
 While I work on making std.allocator better, here's some food 
 for thought regarding std.collection.

 Consider a traditional container with reference semantics, 
 Java-style. Regarding changing the collection (e.g. 
 adding/removing elements) while iterating, we have the 
 following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too 
 extreme.
Personally, I have no problem with this whatsoever, but if that's considered too extreme, then I'd go with
 3. Allow the removal but throw from the ranges if there's any 
 attempt to use a range following a remove.
but I'd make it throw an Error, not an Exception, since it'll seriously harm nogc code otherwise, and I don't see how it can be considered anything but a logic error if you're continuing to iterate over a container with a range or iterator after calling erase/remove on the container, and it would invalidate the range or iterator. I can see making it so that the range continues to work if it wasn't invalidated by the removal (e.g. the removal was at some point before or after the range in the container), but if it was inside the range, then it should be considered a logic error IMHO. To do otherwise would violate how ranges work, because they currently guarantee that they only change in length with calls to popFront or popBack. And in general, range-based algorithms assume that even the values of elements don't change while they're being iterated over, so having the range change what elements it has without a call to popFront or popBack is just begging for trouble. The other thing to consider is reallocation (e.g. a vector type which is appended to can end up being reallocated and invalidate its iterators). And I think that that should be treated the same way. Either we should just consider it undefined behavior or throw an Error. There are some rare cases where it makes sense to remove elements from a container or add them while iterating over them, but in general, I don't see how that could be considered anything but a bad idea. Certainly, you have to understand exactly how the container in question works and whether what you're doing works with that type of container (e.g. adding or removing elements from the beginning of a linked list while iterating over the end of it would be no problem, but doing that with a vector would be a disaster). The one place where it can get a bit annoying to not be able to remove while iterating is when you're iterating over an entire container and removing elements as you go along, but it just doesn't make sense to expect a range to continue to work when an element has been removed from it, since it fundamentally violates how ranges work if how many elements they have changes without a call to popFront or popBack. However, in order to combat the case where you're iterating over a container and removing elements from it as you go, we should probably go the C++ route and have a remove function which returns a range starting at the element after the last element in the range that was passed to the remove function. Then, you can have code like for(auto range = container[]; !range.empty;) { //... if(pred(range.front)) range = container.remove(takeOne(range)); else range.popFront(); } Similarly, we could have a remove function which takes a predicate, which would be more idiomatic in many cases, but it doesn't work in the general case, since that assumes that you're not doing anything else while iterating and that the predicate doesn't change while iterating. Regardless, overall, I don't mind the C++ route with regards to iterator invalidation, but if we're not going to go that route, I think that we should go with throwing Errors when operating on invalidated ranges. The resulting code is then essentially the same, but it catches when you screw up your container logic. - Jonathan M Davis
Jun 21 2015
prev sibling next sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/21/15 7:02 PM, Andrei Alexandrescu wrote:
 While I work on making std.allocator better, here's some food for
 thought regarding std.collection.

 Consider a traditional container with reference semantics, Java-style.
 Regarding changing the collection (e.g. adding/removing elements) while
 iterating, we have the following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too extreme.
I don't think it's undefined, it depends on the container: http://www.cplusplus.com/reference/set/set/erase/ "Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and references keep their validity." I do the same for dcollections. Note that I support a mechanism whereby the user can choose to remove *while* iterating (I call it purging) via the container itself. One of the main reasons I wrote dcollections in the first place is because I had a requirement to remove while iterating. The use case was a map of processes I was keeping track of, looking for ones that were done so they could be removed. In effect, I would do a foreach on the container, and add keys of the elements I'd like to remove to an array. Then afterward, I would use the key array to remove all those elements (these were Tango containers). I didn't like that second step, nor the inefficiency of building another array that I was going to discard. With dcollections, this becomes as simple as: foreach(key, value, ref dopurge; container) { dopurge = checkIfDone(key, value); } One nice thing, you get effectively O(1) removal from non-node containers like arrays, and you can remove while iterating containers that may normally be impossible to remove from while iterating. -Steve
Jun 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/21/15 7:31 PM, Steven Schveighoffer wrote:
 On 6/21/15 7:02 PM, Andrei Alexandrescu wrote:
 While I work on making std.allocator better, here's some food for
 thought regarding std.collection.

 Consider a traditional container with reference semantics, Java-style.
 Regarding changing the collection (e.g. adding/removing elements) while
 iterating, we have the following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too extreme.
I don't think it's undefined, it depends on the container: http://www.cplusplus.com/reference/set/set/erase/ "Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and references keep their validity."
"Invalidated" = undefined. The point is to make it a hard error when trying to use an invalidated range. -- Andrei
Jun 21 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/21/15 10:55 PM, Andrei Alexandrescu wrote:
 On 6/21/15 7:31 PM, Steven Schveighoffer wrote:
 On 6/21/15 7:02 PM, Andrei Alexandrescu wrote:
 While I work on making std.allocator better, here's some food for
 thought regarding std.collection.

 Consider a traditional container with reference semantics, Java-style.
 Regarding changing the collection (e.g. adding/removing elements) while
 iterating, we have the following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too extreme.
I don't think it's undefined, it depends on the container: http://www.cplusplus.com/reference/set/set/erase/ "Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and references keep their validity."
"Invalidated" = undefined. The point is to make it a hard error when trying to use an invalidated range. -- Andrei
No, that's not why I quoted it. An iterator remains valid as long as its target hasn't been removed. For instance: std::set<int> s; s.insert(1); s.insert(2); s.insert(3); auto beg = s.begin(); auto end = s.end(); s.erase(s.find(2)); // beg and end are still valid because they weren't removed while(beg != end) { std::cout << *beg << " "; beg++; } outputs 1 3 So I don't think removing elements should invalidate ranges that do not refer to removed elements. Should such ranges that get invalidated throw an error? Would be very nice but potentially costly. Perhaps in some debug mode? It may be a case of using the right allocator. I can't imagine using certain containers, e.g. linked lists, without the ability to remove while maintaining pointers to certain elements. -Steve
Jun 21 2015
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 6/21/15 10:03 PM, Steven Schveighoffer wrote:
 On 6/21/15 10:55 PM, Andrei Alexandrescu wrote:
 On 6/21/15 7:31 PM, Steven Schveighoffer wrote:
 On 6/21/15 7:02 PM, Andrei Alexandrescu wrote:
 While I work on making std.allocator better, here's some food for
 thought regarding std.collection.

 Consider a traditional container with reference semantics, Java-style.
 Regarding changing the collection (e.g. adding/removing elements) while
 iterating, we have the following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too extreme.
I don't think it's undefined, it depends on the container: http://www.cplusplus.com/reference/set/set/erase/ "Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and references keep their validity."
"Invalidated" = undefined. The point is to make it a hard error when trying to use an invalidated range. -- Andrei
No, that's not why I quoted it. An iterator remains valid as long as its target hasn't been removed.
The matter is very well understood. My point here is that leaving it to the user to make sure which ranges are still valid vs. not is not appropriate for D's container. -- Andrei
Jun 21 2015
next sibling parent "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Monday, 22 June 2015 at 06:29:20 UTC, Andrei Alexandrescu 
wrote:
 The matter is very well understood. My point here is that 
 leaving it to the user to make sure which ranges are still 
 valid vs. not is not appropriate for D's container. -- Andrei
Have you considered checking it at compile time? This is obviously the RCArray problem in disguise, and the same possible solutions apply here, too.
Jun 22 2015
prev sibling next sibling parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/22/15 2:29 AM, Andrei Alexandrescu wrote:
 On 6/21/15 10:03 PM, Steven Schveighoffer wrote:
 An iterator remains valid as long as its target hasn't been removed.
The matter is very well understood. My point here is that leaving it to the user to make sure which ranges are still valid vs. not is not appropriate for D's container. -- Andrei
Then std.collection will be second fiddle to C++ and dcollections I'm afraid when it comes to usability. I won't be using such containers, and will continue to stick with a design that lacks training wheels. -Steve
Jun 22 2015
prev sibling parent "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Monday, 22 June 2015 at 06:29:20 UTC, Andrei Alexandrescu 
wrote:
 The matter is very well understood. My point here is that 
 leaving it to the user to make sure which ranges are still 
 valid vs. not is not appropriate for D's container. -- Andrei
If we mean that we don't want undefined behavior, and we want to do something like throw Errors when a programmer screws up and uses an invalidated range, then fine - especially if it's restricted to version(assert) like we've recently been doing with our checks for calling popFront or front on empty ranges in Phobos - then logic errors with containers can be caught more easily. But if you mean that the programmer shouldn't have to know what types of operations are going to invalidate a range for a specific container type, I don't see how that makes any sense at all. How can anyone expect to use a container without understanding it well enough to know what's going to happen when they start adding elements to it or removing elements from it while iterating over it? IIRC, Java tries to be nicer than C++ and throws an exception when you screw that up rather than treating it as undefined behavior, but even they don't try and make it work for you. You need to understand the container types that you're using if you expect your code to be correct or efficient. And remember that we're already dealing with undefined behavior with all ranges with stuff like what happens when you call front or popFront (or pretty much anything other than empty) on an empty range. So, it's not like we're not going to have undefined behavior involved here. You're just looking to avoid it in an additional case where folks have used a range incorrectly. I'd suggest that we do with containers what we've taken to doing with ranges in Phobos in the last year or so and add checks in version(assert) blocks which throw Errors when you screw up (which in the case of ranges in general would be throwing in functions like front or popFront when the range is empty, and in the case of ranges for containers would mean throwing an Error when you try and do something with them after they've been invalidated). But I don't think that it's at all unreasonable to consider code that tries to iterate over an invalidated range to be a logic error that the programmer needs to fix. Programmers should know when what they're doing to a container is going to invalidate its existing ranges. - Jonathan M Davis
Jun 22 2015
prev sibling next sibling parent reply "Joseph Cassman" <jc7919 outlook.com> writes:
On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu 
wrote:
 While I work on making std.allocator better, here's some food 
 for thought regarding std.collection.

 Consider a traditional container with reference semantics, 
 Java-style. Regarding changing the collection (e.g. 
 adding/removing elements) while iterating, we have the 
 following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too 
 extreme.

 2. Throw an exception if a remove is attempted while ranges 
 exist. This works but it's conservative - e.g. it throws even 
 if those ranges are never to be used again etc.

 3. Allow the removal but throw from the ranges if there's any 
 attempt to use a range following a remove.

 4. Make it work such that ranges continue to be valid post 
 removal. Perhaps this is on the inefficient side.


 Andrei
I was trying to understand how it could work with array slices. For example, I was thinking of code similar to the following from TDPL p. 103: import std.conv, std.stdio; int main(string[] args) { args = args[1 .. $]; while (args.length >= 2) { if (to!int(args[0]) != to!int(args[$ - 1])) { writeln("not palindrome"); return 1; } args = args[1 .. $ - 1]; } writeln("palindrome"); return 0; } Is the slice above considered a range? If so then it seems that (4) is already used a lot in existing D code. If it is not, then will slices of the possible future library implementation of arrays be considered ranges? I cannot see all difficulties arising from allowing (4), but I imagine code complexity will increase as a result. Perhaps the compiler can special case arrays to avoid possible issues making (4) allowable for all containers? Joseph
Jun 21 2015
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 6/22/15 2:27 AM, Joseph Cassman wrote:
 On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu wrote:
 While I work on making std.allocator better, here's some food for
 thought regarding std.collection.

 Consider a traditional container with reference semantics, Java-style.
 Regarding changing the collection (e.g. adding/removing elements)
 while iterating, we have the following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too extreme.

 2. Throw an exception if a remove is attempted while ranges exist.
 This works but it's conservative - e.g. it throws even if those ranges
 are never to be used again etc.

 3. Allow the removal but throw from the ranges if there's any attempt
 to use a range following a remove.

 4. Make it work such that ranges continue to be valid post removal.
 Perhaps this is on the inefficient side.


 Andrei
I was trying to understand how it could work with array slices. For example, I was thinking of code similar to the following from TDPL p. 103: import std.conv, std.stdio; int main(string[] args) { args = args[1 .. $]; while (args.length >= 2) { if (to!int(args[0]) != to!int(args[$ - 1])) { writeln("not palindrome"); return 1; } args = args[1 .. $ - 1]; } writeln("palindrome"); return 0; } Is the slice above considered a range? If so then it seems that (4) is already used a lot in existing D code. If it is not, then will slices of the possible future library implementation of arrays be considered ranges? I cannot see all difficulties arising from allowing (4), but I imagine code complexity will increase as a result. Perhaps the compiler can special case arrays to avoid possible issues making (4) allowable for all containers?
No, what Andrei is referring to is modification of the referenced structure (not just the elements). In other words, imagine removing 5 elements from the array while you are doing this iteration, and pushing all the other elements up. Modification of the range itself is not ever going to be illegal! A range is for iterating, and if you need to iterate it, you must modify it. Note also that although the above sample code uses a string which is technically a range, it's not used with range primitives (front back, popFront, popBack), and really it should be used that way to support UTF. -Steve
Jun 22 2015
parent "Joseph Cassman" <jc7919 outlook.com> writes:
On Monday, 22 June 2015 at 13:42:41 UTC, Steven Schveighoffer 
wrote:
 On 6/22/15 2:27 AM, Joseph Cassman wrote:
 On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu 
 wrote:
[...]
 I was trying to understand how it could work with array 
 slices. For
 example, I was thinking of code similar to the following from 
 TDPL p. 103:

 import std.conv, std.stdio;
 int main(string[] args) {
    args = args[1 .. $];
    while (args.length >= 2) {
      if (to!int(args[0]) != to!int(args[$ - 1])) {
        writeln("not palindrome");
        return 1;
      }
      args = args[1 .. $ - 1];
    }
    writeln("palindrome");
    return 0;
 }

 Is the slice above considered a range? If so then it seems 
 that (4) is
 already used a lot in existing D code. If it is not, then will 
 slices of
 the possible future library implementation of arrays be 
 considered ranges?

 I cannot see all difficulties arising from allowing (4), but I 
 imagine
 code complexity will increase as a result. Perhaps the 
 compiler can
 special case arrays to avoid possible issues making (4) 
 allowable for
 all containers?
No, what Andrei is referring to is modification of the referenced structure (not just the elements). In other words, imagine removing 5 elements from the array while you are doing this iteration, and pushing all the other elements up. Modification of the range itself is not ever going to be illegal! A range is for iterating, and if you need to iterate it, you must modify it. Note also that although the above sample code uses a string which is technically a range, it's not used with range primitives (front back, popFront, popBack), and really it should be used that way to support UTF. -Steve
Yeah, that's not the input range troika. Wasn't clear on how slicing plays into the matter. Thanks Steve. I think a developer should understand what is trying to do with a particular type of collection and so am fine with undefined behavior if a collection is modified while iterating. An error resulting from such an invalid state does not seem exceptional to me, rather a logic error on the part of the developer. So exceptions do not seem a fit to me here. I don't like the proliferation of try-catch blocks in Java. Would also like to use collections in nogc code as well, as much as is possible. If assistance is added from the compiler a la contracts or asserts to catch such logic errors than that is pretty cool. Compile-time is a nice plus but if too difficult it could be left to the developer's responsibility just fine, IMO. Joseph
Jun 22 2015
prev sibling next sibling parent reply "philippecp" <philly.dilly gmail.com> writes:
On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu 
wrote:
 While I work on making std.allocator better, here's some food 
 for thought regarding std.collection.

 Consider a traditional container with reference semantics, 
 Java-style. Regarding changing the collection (e.g. 
 adding/removing elements) while iterating, we have the 
 following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too 
 extreme.

 2. Throw an exception if a remove is attempted while ranges 
 exist. This works but it's conservative - e.g. it throws even 
 if those ranges are never to be used again etc.

 3. Allow the removal but throw from the ranges if there's any 
 attempt to use a range following a remove.

 4. Make it work such that ranges continue to be valid post 
 removal. Perhaps this is on the inefficient side.


 Andrei
I think the best approach is the following: * Throw exceptions on debug (usability) * Leave undefined on release (performance) * Implement another set of collections in std.collections.persistent that allows modification of ranges without invalidating original range (or changing, aka supports snapshotting)that could be referenced somewhere else including another thread. Modifications would return a new reference rather than be done in place and collections in this namespace are immutable.
Jun 22 2015
parent reply Jeremy Powers via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Mon, Jun 22, 2015 at 8:39 PM, philippecp via Digitalmars-d <
digitalmars-d puremagic.com> wrote:

 I think the best approach is the following:
 * Throw exceptions on debug (usability)
 * Leave undefined on release (performance)
Please no. Different behavior between release and non is not something to be desired.
Jun 23 2015
next sibling parent reply "Jonathan M Davis" <jmdavisProg gmx.com> writes:
On Tuesday, 23 June 2015 at 19:13:43 UTC, Jeremy Powers wrote:
 On Mon, Jun 22, 2015 at 8:39 PM, philippecp via Digitalmars-d < 
 digitalmars-d puremagic.com> wrote:

 I think the best approach is the following:
 * Throw exceptions on debug (usability)
 * Leave undefined on release (performance)
Please no. Different behavior between release and non is not something to be desired.
It's perfectly normal if we're talking about assertions, but in that case, it's an AssertError being thrown, not a normal exception. So, in either case, it's a logic error; it's just that you get better reporting of it in debug mode than in release and don't have the cost of doing the checking in release. - Jonathan M Davis
Jun 23 2015
parent reply Jeremy Powers via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Tue, Jun 23, 2015 at 12:31 PM, Jonathan M Davis via Digitalmars-d <
digitalmars-d puremagic.com> wrote:

 On Tuesday, 23 June 2015 at 19:13:43 UTC, Jeremy Powers wrote:

 Different behavior between release and non is not something to be desired.
It's perfectly normal if we're talking about assertions, but in that case, it's an AssertError being thrown, not a normal exception. So, in either case, it's a logic error; it's just that you get better reporting of it in debug mode than in release and don't have the cost of doing the checking in release.
Well I don't like assertions either, for specifically that reason. An error is an error, I don't want something to be caught and handled in debug to then be ignored and explode on release. If my release isn't checking for it, and subsequently fails, this is now a bug in release that was not in debug. I realize other people have different views on this.
Jun 23 2015
next sibling parent ketmar <ketmar ketmar.no-ip.org> writes:
On Tue, 23 Jun 2015 13:30:52 -0700, Jeremy Powers via Digitalmars-d wrote:

 Well I don't like assertions either, for specifically that reason.  An
 error is an error, I don't want something to be caught and handled in
 debug to then be ignored and explode on release.  If my release isn't
 checking for it, and subsequently fails, this is now a bug in release
 that was not in debug.
yes. that's why i stopped using simple `assert`, and doing `if (!cond)=20 assert(0);` in my code.=
Jun 23 2015
prev sibling parent "Kagamin" <spam here.lot> writes:
On Tuesday, 23 June 2015 at 20:31:08 UTC, Jeremy Powers wrote:
 Well I don't like assertions either, for specifically that 
 reason.  An error is an error, I don't want something to be 
 caught and handled in debug to then be ignored and explode on 
 release.  If my release isn't checking for it, and subsequently 
 fails, this is now a bug in release that was not in debug.
That code can still be versioned for debug and won't make it into release and behavior will differ, there is a lot of ways to screw up, you should consider what you do.
Jun 24 2015
prev sibling parent "philippecp" <philly.dilly gmail.com> writes:
On Tuesday, 23 June 2015 at 19:13:43 UTC, Jeremy Powers wrote:
 On Mon, Jun 22, 2015 at 8:39 PM, philippecp via Digitalmars-d < 
 digitalmars-d puremagic.com> wrote:

 I think the best approach is the following:
 * Throw exceptions on debug (usability)
 * Leave undefined on release (performance)
Please no. Different behavior between release and non is not something to be desired.
Yeah, wrote that late at night, what I actually meant was for assertions in debug.
Jun 29 2015
prev sibling next sibling parent "Morbid.Obesity" <Morbid.Obesity mail.com> writes:
On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu 
wrote:
 While I work on making std.allocator better, here's some food 
 for thought regarding std.collection.

 Consider a traditional container with reference semantics, 
 Java-style. Regarding changing the collection (e.g. 
 adding/removing elements) while iterating, we have the 
 following possibilities:

 1. Leave it undefined, like the STL does. Probably this is too 
 extreme.

 2. Throw an exception if a remove is attempted while ranges 
 exist. This works but it's conservative - e.g. it throws even 
 if those ranges are never to be used again etc.

 3. Allow the removal but throw from the ranges if there's any 
 attempt to use a range following a remove.

 4. Make it work such that ranges continue to be valid post 
 removal. Perhaps this is on the inefficient side.


 Andrei
First, There is an alternative: Lazy Removal. This allows one to remove from the container while iterating over it by not removing immediately but after the iteration has actually happened. Lazy Removal can easily be implemented efficiently by using a bit sequence to represent the removed state of each item. This is to provide the appropriate null reference when retrieving an item that has been removed. Of course, one could lead it up to the user to avoid accessing removed elements. (if they removed them, it should be easy to know or keep track manually) Second, Case 1, unfortunately. There is no valid solution as T. S. has mentioned EXCEPT to prevent any immediate removal. (since T.S. showed that removal while iterating is bad, we can't have it) Hence to simulate this see :First:. To make immediate changes when they are ok. The programmer can have access to a "Flush" which will immediately remove all "cached removals". In fact, to make like easier all removals should be cached while iterating. Once iterating is done, the removals are flushed. This is a clearly defined and easily implementable solution that provides the best of both worlds. e.g., Remove(x) - Removes the item x from the container immediately if the container is not being iterated over, else it waits until the container is no longer being iterated over. This is safe since no real action on the container is taken while the container is "in use". Flush() - Removes all cached items from Remove(x) from the container. Unsafe while iterating over. RemoveNow(x) - Immediately removes the item x from the container regardless of iteration. Usafe while iterating over.
Jun 23 2015
prev sibling parent "weaselcat" <weaselcat gmail.com> writes:
On Sunday, 21 June 2015 at 23:02:38 UTC, Andrei Alexandrescu 
wrote:
 1. Leave it undefined, like the STL does. Probably this is too 
 extreme.
I don't think this is too extreme at all. If std.collections is slow, nobody will use it. If you don't believe me, go to code.dlang.org and ctrl+f json
Jun 23 2015