I love this blog, but I'm not sure that I agree with this:<p>> In my mind, I’d just rather not have a reject! at all, and callers who need to mutate an array in-place can figure out how to do safely with respect to their own use cases.<p>We ought to have a standard version of the reject! code precisely <i>because</i> it's so difficult to get right. Saying application developers should solve the problem themselves just sounds like some sort of political move: 'sure they may get the edge cases wrong, but then it will be their fault not ours'.<p>One of the best things about Ruby is that having helper methods for every kind of possible operation frees application developers from re-solving these edge-case problems and allows them to just write their business logic.
Shameless plug:<p>After years working with Ruby, I felt that "bang" methods should only be used for methods which mutate the receiver. Many methods which <i>do</i> do so do not have a "!" at the end.<p>To that end I created a little library called "Bang All The Things" :) <a href="https://github.com/pmarreck/ruby-snippets/blob/master/bang_all_the_things.rb" rel="nofollow">https://github.com/pmarreck/ruby-snippets/blob/master/bang_a...</a><p>I'm convinced that this simplification helps prevent bugs, at the minor cost of changing some conventions possibly borrowed from other languages.<p>I have since (mostly) moved on to Elixir which does not have the "mutability problem" at all.
I think that perhaps the most interesting part of this article is that it comes from a blog called 'accidentallyquadratic' with more than one entry.
One of the more confusing parts of the C++ standard library algorithms is remove/remove_if. A new user would think calling remove(v.begin(), v.end(), value_to_remove) would result in the value being removed from the container[1]. Instead, they'll find that all it did was shift around the ordering of the vector and leave the elements you wanted removed in place at the end (if you read the linked article you can already see where this is going) which is a very unintuitive result. They might look up the function signature and notice it returns an iterator which is also surprising.<p>Even after discovering they have to call the container's erase method using the result of remove and an iterator to the end of the container[2] they'd probably just decide that remove just has a terrible design. It takes experience and some data structures knowledge to realize why it is designed the way it is.<p>The design of remove means every element that remains are only be shifted (in the case of an array/vector), at most, one time. The naive approach results in the problem described in the article where you are constantly shifting the elements forward as you progress through the container.<p>The usability of remove is still a problem (the concept shouldn't need a wikipedia page explaining it) but the way it was done was done for good reasons (within the design decisions of STL at least). It's probably fixed in the C++ ranges proposal but I haven't looked.<p>D's standard algorithm library remove[3] (which is very much based on Stepanov's STL too) goes one performance step further and lets you specify the swap strategy so that if stability isn't a requirement the number of shifts required is the absolute minimum possible (essentially moving elements from the end of the range into spots freed up by the items being removed).<p>1. Slightly more experienced users would quickly notice that it can't remove the value, it has no reference to the container to change its length.<p>2. So common and unintuitive it gets its own wikipedia page: <a href="https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom" rel="nofollow">https://en.wikipedia.org/wiki/Erase%E2%80%93remove_idiom</a><p>3. <a href="http://dlang.org/phobos/std_algorithm_mutation.html#.remove" rel="nofollow">http://dlang.org/phobos/std_algorithm_mutation.html#.remove</a>
Why is `reject!` even a separate, and different implementation than `select!`? Perf reasons?<p>Haskell's Data.List doesn't seem to even have a remove/reject. Clojure's remove is simply a complement of filter.
I can't agree with the conclusion. Sure complexity is complex, but the solution here would seem to be better performance analysis of the standard library rather than blindly avoiding risk. How do you know where to stop? All built in block-accepting methods for enumerator types would seem to be equally risky in this analysis.
I find it weird that the case is called a "bug" multiple times. Sure, if its o(n^2), that's a problem, but if the code works correctly at the end, it's not a bug.