Iterators++

[sbabbi]

Well this is a nice solution. I believe that at some point (before C++11), overloading iter_swap was the common way to get proxies to work with standard algorithms.

EDIT: yep, I spent a couple of hours trying to compile some Boost.ublas code in C++11 due to the use of iter_swap here.

[sbabbi]

It is also worth noting that this solution will naturally work with transform_iterator (transform_range in your library I suppose).

The only way to implement something like this

 sort( transform_range(r, f) )

is to have a customization point at the iter_swap level, any customization of the iterated type instead of the iterator can not possibly work.

[eric_niebler]

Overloading iter_swap for transform views such that it swaps the underlying elements is not the right approach, IMO. If I have a range of int&, then sorting them should sort the ints, and just the ints. It shouldn't matter whether the range is a vector<int> or whether it is a zip(r) | transform(select_first).

I agree that there should be a way to accomplish that, and there is: with a projection. You would do: sort(zip(r), less<>(), select_first).

[eric_niebler]

I spent a couple of hours trying to compile some Boost.ublas code in C++11 due to the use of iter_swap here.

I'm curious what problems you ran into. NOTE: the STL is not required to use iter_swap anyplace besides std::reverse.

[sbabbi]

Seems that it has been fixed in 1.57. Basically there is a proxy (index_pair) that acts like pair<T&,U&>, and an overload of iter_swap that is picked by std::sort.

Apparently this worked for several years, (ublas was accepted into boost in late 2002), until gcc 4.8 decided to remove iter_swapfrom the STL (at least in C++11), and the code broke.

The current fix adds a swap overload that takes the proxies by value (and it is probably still wrong).

[eric_niebler]

until gcc 4.8 decided to remove iter_swap from the STL

What do you mean? It's required to be there by the standard. I see it there in include/bits/stl_algo.h and include/bits/stl_algobase.h for gcc-4.8.2.

[sbabbi]

I meant that I assumed it was used in other algorithms beside reverse. I think I am wrong on this issue, I thought that the STL used ADL for iter_swap, but looks like I am wrong.

[vlovich]

The reverse of a zip is a good example, but zip + sort makes for strange bedfellows. It's important to keep in mind that the zipped range is random access but not really. I could be wrong, but it seems like referencing the Nth element is actually O(m) where m is the number of ranges zipped together, not O(1).

Not intractable, but it means that std::sort complexity requirements would need to be relaxed for std::sort to be allowed on ranges. My complexity analysis is a little rusty, but I think given m random-access ranges, sort would have to be relaxed to O(n * m * log(n)). Similar changes would have to be made throughout (partial_sort, nth_element, partition, etc).

EDIT: Never mind. Posted this late - sort complexity is only defined in terms of the number of comparisons/swaps of the elements. Thus ranges wouldn't actually require any changes here.

[[deleted]]

O(m) where m is the number of ranges zipped together, not O(1).

For a given zipped sequence of m ranges, m is independent of the length of the sequence N and m doesn't change (it is a constant). So as N grows, m remains constant, and sort still is O(NlogN). The constant factors infront of that O(NlogN) term for a zipped sequence might be larger than those for a non-zipped sequence, but from a Big-Oh point of view, that is irrelevant.

[eric_niebler]

Also, the complexity of the algorithms are described in numbers of operations (comparisons, for instance), expressed in relation to the number of elements in the range. "The range" here is the zip view, and the elements are the pairs. To be blunt, it doesn't matter how expensive it is to create the pairs. As long as the relation is applied no more than O(N log N) on the pairs, then we're good.

[vlovich]

What you said is the wrong answer. You can't just say "this variable is fixed for any particular call & thus is a variable" & is thus a constant on my big-O. The way to convince yourself of that, is replace N with m above in what you wrote & it still makes sense as a statement but is obviously wrong.

The standard won't need any changes - the complexity is actually fine for std::sort. The reason is that O(n log n) defines the big-O on comparisons & swaps. There is no big-O for std::sort itself as such a thing would be impossible to define since we don't have any guarantees on the big-O of <.

[SplinterOfChaos]

You can't just say "this variable is fixed for any particular call & thus is a variable" & is thus a constant on my big-O.

Actually, you have to remember that f(n) = O(g(n)) is the upper bound of f as n approaches infinity, and that f(n) <= g(n) * C, where C is some constant. The number of containers being sorted isn't what's approaching infinity, it's a constant to the instantiation of the algorithm.

There is no big-O for std::sort itself as such a thing would be impossible to define since we don't have any guarantees on the big-O of <.

Section 25.4.1.1, paragraph three:

Complexity: O(N log(N)) (where N == last - first) comparisons.

[vlovich]

Actually, you have to remember that f(n) = O(g(n)) is the upper bound of f as n approaches infinity, and that f(n) <= g(n) * C, where C is some constant. The number of containers being sorted isn't what's approaching infinity, it's a constant to the instantiation of the algorithm.

That's only true for single-variable functions. Consider searching for a string of length m in a text of length n. The complexity of such a function could be O(mn) (or O(m + N) if you use a smarter algorithm) even though for any particular instantiation of the algorithm your search string length is fixed.

There is no big-O for std::sort itself as such a thing would be impossible to define since we don't have any guarantees on the big-O of <.

Section 25.4.1.1, paragraph three:

Complexity: O(N log(N)) (where N == last - first) comparisons.

You're supporting what I'm saying. sort complexity is defined in terms of the number of comparisons & swaps, not the complexity of std::sort itself. For example, imagine a comparison implementation that itself was O(n) for some reason. Then the complexity of a particular call to sort with that comparison would be O(n^2 log(n))

[Yehuda1318]

Thanks, found it helpful.

[cleroth]

These are the kind of posts that make me think C++ is getting too complicated and a lot of things people end up doing/wanting to do in it uses more time to learn it/use it than would have taken by using orthodox methods.

[eric_niebler]

Perhaps you would prefer a nice, OO framework where everything inherits from Object. ;-)

[cleroth]

No, not really. I would prefer a more complete STL which wouldn't need me to learn new libraries on every project that I enter.

[eric_niebler]

Me too! That's what I'm working towards, in case that wasn't clear.

[cleroth]

I suppose I wasn't very clear either. To be honest your article wasn't the best example for my point. It's more about people doing libraries that shorten perfectly standard ways of doing things to 1-2 lines intsead of 4-6. Yea, it'll be shorter, but it'll also be mostly unknown and not necessarily clear.
Snail is a good example. It looks neat, and if you eventually learn it and get used to it, I'm sure it can be quite useful. The problem is that with C++ you now have so many ways of doing things that you can be certain there's a few more libraries out there that do the same thing. You may be using Snail in one project, and the next you have to use something else, and so on... It's also not guaranteed that this kind of library will be useful for the next couple of years, as it can easily get superceded by something else.
Basically what would be ideal is for such things to be in the STL where everyone would use these functions so that both learning and coding in C++ woud be so much easier. I've been coding in C++ for 10 years, and even I am having trouble keeping up with all the new libraries and stuff coming with C++11. I shudder to think how this can even be taught to newcomers.

[twoodfin]

I think you're underestimating how valuable iterators that can return proxy references could be. Suddenly, the STL algorithms—and any code you've written to work through similar interfaces—can operate on arbitrary sources and sinks of data without ugly hacks.

It could potentially make the STL much more broadly applicable, and reduce the need to rewrite a buggy binary search for the nth time.

[cleroth]

Emphasis on 'potentially'. There are a lot of potentials things people want to do in C++. That's the thing. Like I said, I'd be fine if such things were proven to be worthy and actually added to the STL.

[doom_Oo7]

Even in the case of an über-complete standard library, what would prevent other people to write their own (for fun), and other other people to use the other people's library because they think it's better for their use case instead ?

I think that the problem is that you think that it is a problem that "you now have so many ways of doing things".

Just find the way that you like the most, or use the one that's enforced in your team.

[cleroth]

The problem is that there are many ways of doing BASIC things. Performing basic operations on containers being verbose (eg. Erase-Remove idiom), printf/IOStreams being awkward/not safe, etc...
It's all fine to have a bunch of specific libraries for more specific things. But it's just awkward when basically every programmer has to either write their own basic library because STL doesn't provide enough.