Should (and can) the <algorithm> functions be extended by convenience helpers that take generic containers as parameters?

49 views
Skip to first unread message

Martin B.

unread,
Aug 1, 2011, 8:49:09 AM8/1/11
to

Hi!

Note: I am pretty sure this has been brought up in various places a lot
of times, but it's a tad hard to google for. :-)


Many [algorithm
functions](http://www.cplusplus.com/reference/algorithm/) work with a
pair (or pairs) of iterators.

Often, these iterators will be used with container.begin() and
container.end().

Wouldn't it therefore make a lot of sense to have additional helper
functions that just take a generic container argument instead of a pair
of iterators?

Example:

//from <algorithm>:
template <class RandomAccessIterator, class Compare>
void sort ( RandomAccessIterator first,
RandomAccessIterator last,
Compare comp );

//useful(??) additional version:
template <class RandomAccessContainer, class Compare>
void sort ( RandomAccessContainer cont,
Compare comp )
{
sort(cont.begin(), cont.end(), comp);
}

Personally, I think this should just be part of the standard library.

Barring this, does any such convenience header already exists, that
tries to add such helpers where they make sense?

cheers,
Martin

--
Stop Software Patents
http://petition.stopsoftwarepatents.eu/841006602158/
http://www.ffii.org/


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

Bo Persson

unread,
Aug 1, 2011, 11:30:47 PM8/1/11
to

There were proposals for this when the C++0x draft still contained
"concepts". In the general case, you would need the "concepts" to
decide what function to call. Otherwise there might be problems for
the compiler to decide among function like:

template <class RandomAccessContainer, class Compare>

void sort ( RandomAccessContainer cont, Compare comp );

template <class RandomAccessIterator>
void sort ( RandomAccessIterator first, RandomAccessIterator last);


How do we know what is an iterator, a container, or a comparer?


Bo Persson


--

Martin B.

unread,
Aug 2, 2011, 2:13:14 PM8/2/11
to
On 02.08.2011 05:30, Bo Persson wrote:

> Martin B. wrote:
>>
>> Many [algorithm
>> functions](http://www.cplusplus.com/reference/algorithm/) work with
>> a pair (or pairs) of iterators.
>>
>> Often, these iterators will be used with container.begin() and
>> container.end().
>>
>> Wouldn't it therefore make a lot of sense to have additional helper
>> functions that just take a generic container argument instead of a
>> pair of iterators?
>>
>> Example:
>>...

>>
>> Personally, I think this should just be part of the standard
>> library.
>> Barring this, does any such convenience header already exists, that
>> tries to add such helpers where they make sense?
>>
>
> There were proposals for this when the C++0x draft still contained
> "concepts". In the general case, you would need the "concepts" to
> decide what function to call. Otherwise there might be problems for
> the compiler to decide among function like:
>
> template<class RandomAccessContainer, class Compare>
> void sort ( RandomAccessContainer cont, Compare comp );
>
> template<class RandomAccessIterator>
> void sort ( RandomAccessIterator first, RandomAccessIterator last);
>

Hmm ... I'd have thought this would be gracefully handled via SFINAE?:

The container version would call `.begin()` and/or `.end()` on `cont`
and the iterator version would dereference `first` -- neither of which
could compile for the other.

What am I missing?

cheers,
Martin

Carlos Moreno

unread,
Aug 2, 2011, 2:25:24 PM8/2/11
to
>> [ ... ]

>
> There were proposals for this when the C++0x draft still contained
> "concepts". In the general case, you would need the "concepts" to
> decide what function to call. Otherwise there might be problems for
> the compiler to decide among function like:
>
> template<class RandomAccessContainer, class Compare>
> void sort ( RandomAccessContainer cont, Compare comp );
>
> template<class RandomAccessIterator>
> void sort ( RandomAccessIterator first, RandomAccessIterator last);
>
> How do we know what is an iterator, a container, or a comparer?

Traits?

Something like:

template <typename Iterator>
void sort (Iterator begin, Iterator end,
typename Iterator::iterator_category
= typename Iterator::iterator_category())
{
// ...
}

Only calls with two parameters that *are iterators* can match
the above.

HTH,

Carlos

Seungbeom Kim

unread,
Aug 3, 2011, 3:18:22 AM8/3/11
to

On 2011-08-02 11:25, Carlos Moreno wrote:
>>
>> How do we know what is an iterator, a container, or a comparer?
>
> Traits?
>
> Something like:
>
> template <typename Iterator>
> void sort (Iterator begin, Iterator end,
> typename Iterator::iterator_category
> = typename Iterator::iterator_category())
> {
> // ...
> }

'Iterator' may be a pointer, so 'Iterator::some_name' fails for pointers.
Instead of 'Iterator::iterator_category', you should use
'std::iterator_traits<Iterator>::iterator_category'.

--
Seungbeom Kim

Yechezkel Mett

unread,
Aug 3, 2011, 8:10:31 AM8/3/11
to

On Aug 1, 3:49 pm, "Martin B." <0xCDCDC...@gmx.at> wrote:
> Many [algorithm
> functions](http://www.cplusplus.com/reference/algorithm/) work with a
> pair (or pairs) of iterators.
>
> Often, these iterators will be used with container.begin() and
> container.end().
>
> Wouldn't it therefore make a lot of sense to have additional helper
> functions that just take a generic container argument instead of a pair
> of iterators?

See Boost.Range (http://www.boost.org/doc/libs/1_47_0/libs/range/doc/
html/index.html).

Yechezkel Mett


--

Bo Persson

unread,
Aug 3, 2011, 9:18:48 AM8/3/11
to

That you are adding new requirements that just *might* break existing
code.

Right now I can sort a Matrix class that has both begin, end, and
operator* defined. How will the SFINAE find out which template to use?

I have seen ever more perverse examples where the container object
could have operator() defined and be used as its own comparer...


Bo Persson

Marc

unread,
Aug 3, 2011, 9:19:11 AM8/3/11
to

Seungbeom Kim wrote:

> On 2011-08-02 11:25, Carlos Moreno wrote:
>>>
>>> How do we know what is an iterator, a container, or a comparer?
>>
>> Traits?
>>
>> Something like:
>>
>> template <typename Iterator>
>> void sort (Iterator begin, Iterator end,
>> typename Iterator::iterator_category
>> = typename Iterator::iterator_category())
>> {
>> // ...
>> }
>
> 'Iterator' may be a pointer, so 'Iterator::some_name' fails for pointers.
> Instead of 'Iterator::iterator_category', you should use
> 'std::iterator_traits<Iterator>::iterator_category'.

which fails in case of a substitution failure. Some libraries make it
sfinae-capable as an extension (libstdc++ in C++0X mode, libc++), but
you have to reimplement it yourself if you want to rely on it.


--

Martin B.

unread,
Aug 3, 2011, 9:19:53 AM8/3/11
to

On 03.08.2011 14:10, Yechezkel Mett wrote:
>
> On Aug 1, 3:49 pm, "Martin B."<0xCDCDC...@gmx.at> wrote:
>> Many [algorithm
>> functions](http://www.cplusplus.com/reference/algorithm/) work with a
>> pair (or pairs) of iterators.
>>
>> Often, these iterators will be used with container.begin() and
>> container.end().
>>
>> Wouldn't it therefore make a lot of sense to have additional helper
>> functions that just take a generic container argument instead of a pair
>> of iterators?
>
> See Boost.Range (http://www.boost.org/doc/libs/1_47_0/libs/range/doc/
> html/index.html).
>

I assume more specifically <boost/range/algorithm.hpp>.

Nice. I didn't remember that Boost.Range algorithms can just be called
for any STL container.

cheers,
Martin

german diago

unread,
Aug 3, 2011, 6:38:12 PM8/3/11
to

On 1 ago, 14:49, "Martin B." <0xCDCDC...@gmx.at> wrote:
> Hi!
>
> Note: I am pretty sure this has been brought up in various places a lot
> of times, but it's a tad hard to google for. :-)
>
> Many [algorithm
> functions](http://www.cplusplus.com/reference/algorithm/) work with a
> pair (or pairs) of iterators.
>
> Often, these iterators will be used with container.begin() and
> container.end().
>
> Wouldn't it therefore make a lot of sense to have additional helper
> functions that just take a generic container argument instead of a pair
> of iterators?

It's not part of the standard, but boost implements range-based
algorithms
in its Boost.Range library. It's exactly what you're looking for and
much more.


--

Martin Bonner

unread,
Aug 4, 2011, 8:35:03 PM8/4/11
to


The Boost Range library handles this.


--

piotrN

unread,
Aug 4, 2011, 8:35:11 PM8/4/11
to

Martin,

> Example:
>
> //from <algorithm>:
> template <class RandomAccessIterator, class Compare>
> void sort ( RandomAccessIterator first,
> RandomAccessIterator last,
> Compare comp );
>
> //useful(??) additional version:
> template <class RandomAccessContainer, class Compare>
> void sort ( RandomAccessContainer cont,
> Compare comp )

I remember from my "C" years such tricky method to make many
parameters from one:

#define FULL_RANGE(cont) (cont).begin(), (cont).end()

So, placing this in your example:

sort(FULL_RANGE(cont), comp);

Achieving the same effect with templates, however without doubts more
safe, would much more complicated.

Best Regards,
Piotr


--

Reply all
Reply to author
Forward
0 new messages