Today, my interest was piqued by the problem of reversing the contents
of a sequence container.

[A sequence container maintains elements in sequence (list/vector
like), rather than in order (set/map like), or even unordered (hash)]

Since both list::iterator and vector::iterator are Bidirectional, I
can use:

   std::reverse(listOrVector.begin(), listOrVector.end());

If I know that I have a std::list, I can also use:

   knownAsList.reverse();

But I cannot:

   knownAsVector.reverse();    // vector cannot itself reverse

So I'll use std::reverse in the following generic function, accessing
the optimizations of the standard algorithms and insulating myself
from a change of Container from std::list to std::vector:

   template <typename Container>
   void doReverse(Container& container) {
       std::reverse(container.begin(), container.end());
   }

But then, C++0x introduces the forward_list and forward_list::iterator
is not Bidirectional.  Someone changes the Container from std::list or
std::vector to std::forward_list and then where am I?  std::reverse
can't help me unless I give it Bidirectionals.

std::reverse requires Bidirectional iterators because it swaps the
front with the back, then moves both towards the middle until it meets
itself.  It's O(n).

But I can think of a nice O(n) reverse algorithm for
std::forward_list, in fact, there is a proposed
std::forward_list::reverse that probably does just that algorithm.

In summary:

   list.reverse(); // okay
   std::reverse(list.begin(), list.end()); // okay

   vec.reverse();  // no method
   std::reverse(vec.begin(), vec.end()); // okay

   fwdlist.reverse(); // okay
   std::reverse(fwdlist.begin(), fwdlist.end());  // bad

No generic combination.

C++0x adds new containers and defines those in terms of the new
concept of concepts, but are the algorithms keeping pace with the rest
of the language and the library?

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

On 18 juin, 04:11, Nick Mocha <nic...@gmail.com> wrote:

> Since both list::iterator and vector::iterator are Bidirectional, I
> can use:
>
>    std::reverse(listOrVector.begin(), listOrVector.end());
>
> If I know that I have a std::list, I can also use:
>
>    knownAsList.reverse();
>
> But I cannot:
>
>    knownAsVector.reverse();    // vector cannot itself reverse

The reason std::list has is own reverse function is because the data
structure allows efficient reversal without accessing the elements.

A better generic reverse would be range-based.

template<typename Range>
typename disable_if<has_reverse<Range>>::type reverse(Range&& r)
{
     std::reverse(begin(r), end(r));
}

template<typename Range>
typename enable_if<has_reverse<Range>>::type reverse(Range& r)
{
     r.reverse();
}

Range-based algorithms may come in TR2.


--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]

> The reason std::list has is own reverse function is because the data
> structure allows efficient reversal without accessing the elements.

Agreed, likewise for std::forward_list.

But note that std::reverse(b,e) cannot be applied to
std::forward_list::iterators.

Note also that there is a possible algorithm for reversing a
std::forward_list through std::forward_list::iterators (with at most
one swap, plus O(e-b) internal relinking in a O(e-b) traversal).

Such an algorithm can (at least) match the std::reverse complexity
requirement, but it can never match the std::reverse requirement for
bidirectional iterators.

The fact that std::reverse precludes its application to
std::forward_list::iterators, on the bidirectional requirement alone,
seems to demonstrate a regression of cohesion within the container/
algorithm framework.

Cohesion existed when all sequence containers were bidirectional in
nature - now that we have a "sequence container" (sic) that is not
bidirectional.

Should we leak cohesion or strengthen the algorithms?

(Reference also std::partition).

--
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@netlab.cs.rpi.edu]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html                      ]