Dave Harris wrote:
>
> marco@technoboredom.net (Marco Manfredini) wrote (abridged):
> > Because there is not unstable_sort, I'd guess & there is no need to
> > distinguish between sorts of sort then.
>
> Consistent naming would be helpful when writing templates. Compile-time
> polymorphism relies on it.
>
> Suppose I have my own containers, which provide both sort and stable_sort
> (perhaps by being simple wrappers for std::vector()). And suppose I write
> some template, like:
>
>     template <typename Container>
>     void demo( Container &c ) {
>         c.stable_sort();
>         //...
>     }
>
> meaning that I rely on the stable property. This will not work with
> std::list, even though its sort is stable, because of the naming problem.
>
> Still, it won't work with std::vector, either. In practice I'm probably
> better off using some kind of specialised global adapter function than
> calling a member function directly.

Alternatively, you could define a sorting_traits:

template<class Container> struct sorting_traits
{
  // per default, we just call the standard algorithm
  static void sort(Container& c)
    { std::sort(c.begin(), c.end()); }
  static void stable_sort(Container& c)
    { std::stable_sort(c.begin(), c.end()); }
};

template<class T, class Alloc>
 struct sorting_traits<std::list<T, alloc> >
{
  // for list, we use std::sort in all cases
  static void sort(std::list<T, Alloc>& c)
    { c.sort(); }
  static void stable_sort(std::list<T, Alloc>& c)
    { c.sort(); }
};

template<class T>
 struct sorting_traits<YourContainer<T> >
{
  // for your containers, the appropriate member functions are called
  static void sort(YourContainer<T>& c)
    { c.sort(); }
  static void stable_sort(YourContainer<T>& c)
    { c.stable_sort(); }
};

Now you could make a template which works on any container:

template<clas Container> void foo(Container& c)
{
  // ... do something ...
  sorting_traits<Container>::sort(c);
  // ... do more ...
  sorting_traits<Container>::stable_sort(c);
}

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

I just noticed that list::sort is required to be stable.  Okay, I'll bite:
Why isn't it called stable_sort?

Scott

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

Scott Meyers <smeyers@aristeia.com> wrote in
<MPG.1522c81326c1e2229897a7@news.supernews.com>:

>I just noticed that list::sort is required to be stable.  Okay, I'll
>bite: Why isn't it called stable_sort?
>
Because there is not unstable_sort, I'd guess & there is no need to
distinguish between sorts of sort then.

--
Marco

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

Scott Meyers wrote:
>
> I just noticed that list::sort is required to be stable.  Okay, I'll bite:
> Why isn't it called stable_sort?
>

Why should it.  It doesn't add anything to the complexity to make it stable,
so they are just telling you it always will be.

With iterators, adding stability DOES increase the complexity of the sort,
so it allows you to specify the difference.

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

On Thu, 22 Mar 2001 21:57:47 GMT, Marco Manfredini wrote:
> Because there is not unstable_sort, I'd guess & there is no need to
> distinguish between sorts of sort then.

I guess I wasn't clear enough.  There is an algorithm, sort, which is not
required to be stable.  There is another algorithm, stable_sort, which is
required to be stable.  Given that list::sort is a list-specific version of
sort that is required to be stable, why isn't it called stable_sort?  What is
the rationale behind this inconsistency?

Scott

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

Scott Meyers wrote:
>
> On Thu, 22 Mar 2001 21:57:47 GMT, Marco Manfredini wrote:
> > Because there is not unstable_sort, I'd guess & there is no need to
> > distinguish between sorts of sort then.
>
> I guess I wasn't clear enough.  There is an algorithm, sort, which is not
> required to be stable.  There is another algorithm, stable_sort, which is
> required to be stable.  Given that list::sort is a list-specific version of
> sort that is required to be stable, why isn't it called stable_sort?  What is
> the rationale behind this inconsistency?

No, that's not true.  On iterators, there is a stable stable_sort and unstable sort.

On the sequence itself, there is only SORT, which is stable, because there
is no reason for it not to be.  The order of complexity doesn't go up when
you are workign on the container and you are sorting thewhole thing (n log n).

If you are working via iterators on something where random access takes linear
time, it  can be n log**2 n.

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

Scott Meyers <smeyers@aristeia.com> once said:
>On Thu, 22 Mar 2001 21:57:47 GMT, Marco Manfredini wrote:
>> Because there is not unstable_sort, I'd guess & there is no need to
>> distinguish between sorts of sort then.
>
>I guess I wasn't clear enough.  There is an algorithm, sort, which is not
>required to be stable.  There is another algorithm, stable_sort, which is
>required to be stable.  Given that list::sort is a list-specific version of
>sort that is required to be stable, why isn't it called stable_sort?  What is
>the rationale behind this inconsistency?

I think the real question is "why is there no list::stable_sort?"  It's
implementation would just be
   this->sort();

The only reason that I know of why there are separate algorithms is the
practical performance difference.  std::sort() may often be faster than
std::stable_sort(), despite the fact that I think std::stable_sort()
has better big-oh complexity.

In the case of list, it's hard to imagine (impossible?) a non-stable sort
which performs better than the stable version in any circumstance.  As a
result, from an implementation point of view, only one algorithm is
necessary--the most-efficient-for-all-cases happens to also be stable,
killing two birds with one stone.

However, the interface/naming should, indeed, reflect "the interface"
and not this implementation detail, IMO.  As a result, it would be nice
if list had both members, even if they do (in fact) do exactly the same
thing.  Clients ought not have to care about implementation details.

--
 Brian M. McNamara   lorgon@acm.org  :  I am a parsing fool!
   ** Reduce - Reuse - Recycle **    :  (Where's my medication? ;) )

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

In article <MPG.15242439d5c691e69897a9@news.supernews.com>, Scott Meyers
<smeyers@aristeia.com> writes
>I guess I wasn't clear enough.  There is an algorithm, sort, which is not
>required to be stable.  There is another algorithm, stable_sort, which is
>required to be stable.  Given that list::sort is a list-specific version of
>sort that is required to be stable, why isn't it called stable_sort?  What is
>the rationale behind this inconsistency?

Possibly because a sort method is not, in general, required to be
unstable. In the case of the generic algorithms, sort is not required to
be unstable, just allowed to be (yes we both know that we both know that
the general efficient solution for most containers is unstable). I
suspect that the choice was just to save seven characters by not making
explicit something that would always be true - for list.

--
Francis Glassborow
See http://www.accu.org for details of The ACCU Spring Conference, 2001
(includes many regular participants to C & C++ newsgroups)

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

Scott Meyers wrote:
>
> On Thu, 22 Mar 2001 21:57:47 GMT, Marco Manfredini wrote:
> > Because there is not unstable_sort, I'd guess & there is no need to
> > distinguish between sorts of sort then.
>
> I guess I wasn't clear enough.  There is an algorithm, sort, which is not
> required to be stable.  There is another algorithm, stable_sort, which is
> required to be stable.  Given that list::sort is a list-specific version of
> sort that is required to be stable, why isn't it called stable_sort?  What is
> the rationale behind this inconsistency?

Obviously, list should also have a stable_sort that just forwards to
list::sort.
Or maybe list::sort should forward to list::stable_sort?
Does it matter?

There are a lot of things left out of standard C++ that,
in some sense, should be in there.

Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/

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

marco@technoboredom.net (Marco Manfredini) wrote (abridged):
> Because there is not unstable_sort, I'd guess & there is no need to
> distinguish between sorts of sort then.

Consistent naming would be helpful when writing templates. Compile-time
polymorphism relies on it.

Suppose I have my own containers, which provide both sort and stable_sort
(perhaps by being simple wrappers for std::vector()). And suppose I write
some template, like:

    template <typename Container>
    void demo( Container &c ) {
        c.stable_sort();
        //...
    }

meaning that I rely on the stable property. This will not work with
std::list, even though its sort is stable, because of the naming problem.

Still, it won't work with std::vector, either. In practice I'm probably
better off using some kind of specialised global adapter function than
calling a member function directly.

  Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
      brangdon@cix.co.uk      |   And close your eyes with holy dread,
                              |  For he on honey dew hath fed
 http://www.bhresearch.co.uk/ |   And drunk the milk of Paradise."

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

"Brian McNamara!" <gt5163b@prism.gatech.edu> wrote

> In the case of list, it's hard to imagine (impossible?) a non-stable sort
> which performs better than the stable version in any circumstance.

1) Create vector of pointers to the list elements
2) Sort the vector
3) Weave the list into the vector's order.

Steps 1 and 3 are O(N)
Step 2 may not be stable, but it is often faster (if not big-O faster) than
the traditional list sort.

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