[Home]STLAlgorithmExtensions/IsSortedFunction

BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List

Difference (from prior major revision) (minor diff)

Added: 49a50,61



Another way to do it, in case you don't have an operator>(), is to use reverse iterators:

Container container; // e.g. typedef vector<Foo> Container;
...

if (adjacent_find(container.rbegin(),container.rend(),less<Container::value_type>())==container.rend())
...; // container is sorted

People/Andre Mostert


The [is_sorted] function is terribly useful for testing purposes.

Too bad it isn' t in the C++ std.


Yes, we definitely need it! -- People/Vladimir Prus

It does exist in stl. One can use "adjacent_find" with predicate "less" to obtain the same result


People/Michael Goldshteyn By the way, I think it's adjacent_find with predicate greater, not less, since we are looking for the first item out of sorted order. For example (with std:: omitted for brevity):

Container container; // e.g. typedef vector<int> Container;
...

if (adjacent_find(container.begin(),container.end(),greater<Container::value_type>())==container.end())
  ...; // container is sorted

Of course, greater (i.e. operator>() ) may not be defined for the type in question. In any case, here is the is_sorted duo:

template <class ForwardIterator>
bool is_sorted(ForwardIterator first, ForwardIterator last)
{
  if (first!=last)
    for (ForwardIterator it(first++);first!=last;++it /* or it=first */,++first)
      if (*first<*it)
        return false;

  return true;
}

template <class ForwardIterator, class Predicate>
bool is_sorted(ForwardIterator first, ForwardIterator last,
               Predicate pred)
{
  if (first!=last)
    for (ForwardIterator it(first++);first!=last;++it /* or it=first */,++first)
      if (!pred(*it,*first))
        return false;

  return true;
}

If anyone finds bugs or can improve performance, please do so...


Another way to do it, in case you don't have an operator>(), is to use reverse iterators:
Container container; // e.g. typedef vector<Foo> Container;
...

if (adjacent_find(container.rbegin(),container.rend(),less<Container::value_type>())==container.rend())
  ...; // container is sorted
People/Andre Mostert


BOOST WIKI | STLAlgorithmExtensions | RecentChanges | Preferences | Page List | Links List
Edit text of this page | View other revisions
Last edited April 12, 2005 2:41 pm (diff)
Search:
Disclaimer: This site not officially maintained by Boost Developers