 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Martin
Guest
|
 Posted: Wed May 10, 2006 7:21 pm Post subject: Can 'qsort' have an advantage over 'std::sort'? |
 |
|
Hi.
Let's consider the following realization of Shell sorting:
void shellsort(
void *pBase,
unsigned N,
unsigned Width,
bool (*Pred)(const void*, const void*)
)
{
char *pData = (char *)pBase;
// Using step sequence 1, 4, 13, 40, ..., 3*n+1
unsigned s;
for (s = 1; s < N/6; s = 3*s + 1);
void *pCur = malloc(Width);
for (; s >= 1; s /= 3)
for (unsigned i = s; i < N; ++i)
{
memcpy(pCur, pData + i*Width, Width);
for (unsigned j = i; j >= s &&
Pred(pCur, pData + (j-s)*Width); j -= s)
memcpy(pData + j*Width,
pData + (j-s)*Width, Width);
if (j != i)
memcpy(pData + j*Width, pCur, Width);
}
free(pCur);
}
Yes, I know, it has many drawbacks, among which are:
1) It lacks type checking, so is not type safe;
2) It's not intuitive, works on a lower level, i. e. deals
with memory, rather than with objects;
3) Writing such code is cumbersome and error prone
Will you agree with me, that it also has one significant advantage?
Let's assume we have an array of objects, which contain a pointer
to a large amount of data. Also the project doesn't provide for a
reference counted realization of this objects' class, so the copy
semantics for our objects is simple deep copying of underlying
data. On the other hand I can't resign deep copying, and use
mere copying of inner pointers. It follows, that using 'std::sort'
for sorting our array is extremely wasteful. In my opinion, better
to use ANSI C's 'qsort', which copies only so-called static part of
objects, leaving alone underlying data. Someone can advice to use
'std::sort' on array of pointers, but what I have is an array of
objects, and I can't make signigicant changes to data representation.
Waiting for your comments.
Best regards
Martin
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
 |
johnchx2@yahoo.com
Guest
|
| Posted: Thu May 11, 2006 1:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
Martin wrote:
| Quote: | Yes, I know, it has many drawbacks, among which are:
1) It lacks type checking, so is not type safe;
2) It's not intuitive, works on a lower level, i. e. deals
with memory, rather than with objects;
3) Writing such code is cumbersome and error prone
|
Plus, #4: it has undefined behavior (memcpy-ing a non-pod). So there's
no telling what it will actually do.
| Quote: | Will you agree with me, that it also has one significant advantage?
|
I'm not sure I'd call the advantage significant, inasmuch as it comes
at the cost of making the program's behavior undefined.
| Quote: | Someone can advice to use
'std::sort' on array of pointers, but what I have is an array of
objects, and I can't make signigicant changes to data representation.
|
Can you create a second array, this time containing pointers (or
indexes into the first array) and sort that instead of sorting the
array of objects itself?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Phlip
Guest
|
| Posted: Thu May 11, 2006 1:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
Martin wrote:
| Quote: | In my opinion, better
to use ANSI C's 'qsort', which copies only so-called static part of
objects, leaving alone underlying data.
|
Such copies are the equivalent of memcpy(). So your question, without the
excess details of sorting, is essentially when memcpy() is superior to a
copy operator.
memcpy() is only well-behaved on PODS data. The complete definition of PODS
is beyond the scope of this post; it essentially means no virtuals, no
constants, no references, etc. So now you must remove all those useful
things just to use memcpy(). And if you forget and add one, the program
will not warn you, and its behavior will be undefined.
--
Phlip
http://www.greencheese.us/ZeekLand <-- NOT a blog!!!
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Greg Herlihy
Guest
|
| Posted: Thu May 11, 2006 1:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
Martin wrote:
| Quote: | Hi.
Let's consider the following realization of Shell sorting:
void shellsort(
void *pBase,
unsigned N,
unsigned Width,
bool (*Pred)(const void*, const void*)
)
{
char *pData = (char *)pBase;
// Using step sequence 1, 4, 13, 40, ..., 3*n+1
unsigned s;
for (s = 1; s < N/6; s = 3*s + 1);
void *pCur = malloc(Width);
for (; s >= 1; s /= 3)
for (unsigned i = s; i < N; ++i)
{
memcpy(pCur, pData + i*Width, Width);
for (unsigned j = i; j >= s &&
Pred(pCur, pData + (j-s)*Width); j -= s)
memcpy(pData + j*Width,
pData + (j-s)*Width, Width);
if (j != i)
memcpy(pData + j*Width, pCur, Width);
}
free(pCur);
}
Yes, I know, it has many drawbacks, among which are:
1) It lacks type checking, so is not type safe;
2) It's not intuitive, works on a lower level, i. e. deals
with memory, rather than with objects;
3) Writing such code is cumbersome and error prone
Will you agree with me, that it also has one significant advantage?
Let's assume we have an array of objects, which contain a pointer
to a large amount of data. Also the project doesn't provide for a
reference counted realization of this objects' class, so the copy
semantics for our objects is simple deep copying of underlying
data. On the other hand I can't resign deep copying, and use
mere copying of inner pointers. It follows, that using 'std::sort'
for sorting our array is extremely wasteful. In my opinion, better
to use ANSI C's 'qsort', which copies only so-called static part of
objects, leaving alone underlying data. Someone can advice to use
'std::sort' on array of pointers, but what I have is an array of
objects, and I can't make signigicant changes to data representation.
|
No, the ANSI C qsort has no advantages over std::sort. And the fact
that qsort must copy items in order to sort them - and std::sort does
not - is in fact a significant disadvantage for qsort. Why copy items
if it's not necessary, or if there are more efficient techniques
available?
So how does std::sort rearrange items in a container if not by copying
them? The answer is: by swapping them. So the program should simply
implement a reasonably efficient std::swap for the type of contained
item. Doing so will more than make up std::sort's current deficit
vis-à-vis qsort. And the rest of us (as self-respecting C++
programmers) will then all agree to pretend that the qsort idea was
never a serious suggestion. :-)
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
johnchx2@yahoo.com
Guest
|
| Posted: Fri May 12, 2006 12:21 am Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
Greg Herlihy wrote:
| Quote: | So how does std::sort rearrange items in a container if not by copying
them? The answer is: by swapping them.
|
I thought that this might be the case, but (a) I can't find any
requirement in the standard that it do so and (b) the implementations I
have handy (STLPort and libstdc++) appear to require the copy
constructor and assignment operator, even though I provide a suitable
swap() overload.
Here's the test I ran:
#include <algorithm>
class foo {
foo(const foo&);
foo& operator=(const foo&);
int mData;
public:
foo(int i = 0): mData(i) {}
foo& operator=( int i ) { mData = i; return *this; }
bool operator<( const foo& rhs ) const
{ return mData < rhs.mData; }
friend void swap(foo& lhs, foo& rhs);
};
void swap( foo& lhs, foo& rhs )
{
std::swap( lhs.mData, rhs.mData );
}
int main()
{
foo af [3];
af[0] = 3;
af[1] = 2;
af[2] = 1;
std::sort( af, af + 3 );
}
I checked stable_sort() as well, with the same result.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Fri May 12, 2006 12:21 am Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
In article <1147231231.107088.141280 (AT) e56g2000cwe (DOT) googlegroups.com>,
"Martin" <martin-g (AT) mail (DOT) ru> wrote:
| Quote: | It follows, that using 'std::sort'
for sorting our array is extremely wasteful. In my opinion, better
to use ANSI C's 'qsort', which copies only so-called static part of
objects, leaving alone underlying data. Someone can advice to use
'std::sort' on array of pointers, but what I have is an array of
objects, and I can't make signigicant changes to data representation.
|
You make a good point. Strictly speaking today, std::sort's only
mechanism for moving elements about is via copy construction and
assignment. That is about to change in the standard. And from a
practical point of view, has already changed in some implementations.
The CodeWarrior implementation of std::sort uses unqualified swap
exclusively in std::sort for this very reason. This is not legal, but
it is effective. Gcc now uses unqualified swap in about 40% of its data
moves during a sort (random distribution) (which is a nice start). The
C++0X working draft:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2009.pdf
introduces the Swappable concept and requires that types fed to
std::sort satisfy this concept. Such types can satisfy the concept in
two ways: either with a local-namespace swap function, or by being copy
constructible and copy assignable.
This will have the effect of making it legal for std::sort to use swap,
but also retaining the legality of it to use copy construction and copy
assignment to move elements around.
The "rvalue reference" work (move semantics) proposed for C++0X goes
even further to make std::sort reliably and portably higher performing
for heavy weight objects. See:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1771.html
About mid-way through this paper there is a table titled "Summary of
algorithm requirements". This table specifies which algorithms require
the following concepts of the manipulated elements:
Swappable (S)
MoveConstructible (MC)
MoveAssignable (MA)
CopyConstructible (CC)
CopyAssignable (CA)
For heavy weight objects, a move assign, and a swap are practically the
same thing. For light weight objects (e.g. int), a move assign is the
same thing as a copy assign. In a nutshell, move assign means you want
the target to get the value of the source, and you don't care what
happens to the value of the source.
Similar comments about move construction.
This table proposes the following concept requirements for std::sort:
Swappable (S)
MoveConstructible (MC)
MoveAssignable (MA)
Notably absent are CopyConstructible and CopyAssignable. If this
proposal is accepted, a conforming std::sort will be prohibited from
copy constructing or copy assigning elements during a sort. This will
allow one to even use std::sort on sequences of movable-but-non-copyable
elements (such as the proposed unique_ptr or stringstreams).
-Howard
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Fri May 12, 2006 12:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
johnchx2 (AT) yahoo (DOT) com wrote:
| Quote: | Greg Herlihy wrote:
So how does std::sort rearrange items in a container if not
by copying them? The answer is: by swapping them.
I thought that this might be the case, but (a) I can't find
any requirement in the standard that it do so and (b) the
implementations I have handy (STLPort and libstdc++) appear to
require the copy constructor and assignment operator, even
though I provide a suitable swap() overload.
|
Well, that's a requirement of the standard. Recent versions of
g++ will complain that they are missing even if it doesn't use
them.
In fact, g++ does use them. For small sequences, insertion sort
is faster than quick sort (at least for built-in types), so the
g++ implementation switches to insertion sort (which doesn't
swap) when the partition becomes small enough. And quick sort
has some degenerate cases, where it is O(n^2); g++ detects when
quick sort starts to degenerate, and switches to a heap sort --
which also doesn't use swap.
Note that typically, an implementation will not use swap
directly, but will use iter_swap -- and iter_swap must work even
if the iterators are of different types, and have different
value_types. Which means that it cannot normally use swap
directly -- g++ contains some meta-programming so that it will
use swap if the value types of the iterators are identical,
apparently in response to DR 187 (but DR 187 requires an
implementation of iter_swap which doesn't work if the value
types are different, without introducing an additional
constraint to require that they be the same). I wouldn't be
sure that other implementations are up to date here, and there
is still no guarantee that std::sort use either swap or
iter_swap.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Fri May 12, 2006 12:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
Carl Barron wrote:
[...]
| Quote: | Although c++98 does not require swap to be used the oct 2005
draft does. Any current stl implementation will use swap or
equivalently iter_swap to swap elements rather than the hard
coded generic swap algorithm.
|
If it swaps elements. The g++ implementation only swaps
elements in the general case. It uses an insertion sort when
the partition is smaller than a certain size, and a heap sort if
quick sort starts to degenerate. And neither of these
alternatives swap anything.
| Quote: | using std::swap() allows it to be overloaded for your type so
that it can swap data efficiently.
Any class A that is cheaper to swap than copy,assign twice and
destroy as per std::swap(T &,T&) should provide void
A::swap(A &); and the inline void swap(A &a,A&b) {a.swap(b);}
since it gives no implementation details away and allows
efficient moving of the data. It should also if possible have
a cheap default constructor. [not required for sort algorithms
of <algorithm> ] .
Since writing the predicate is at least as simple as writing a
compare for qsort. I see no need for qsort except for legacy
code.
|
(I suppose you mean "writing the swap function", rather than
"writing the predicate".)
It depends. If you don't have write access to the header file
where the class is defined, and swap requires accessing private
data members, writing the specialized swap function can be
impossible.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
kanze
Guest
|
| Posted: Fri May 12, 2006 12:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
Greg Herlihy wrote:
| Quote: | Martin wrote:
Let's consider the following realization of Shell sorting:
|
[...]
| Quote: | Will you agree with me, that it also has one significant
advantage? Let's assume we have an array of objects, which
contain a pointer to a large amount of data. Also the
project doesn't provide for a reference counted realization
of this objects' class, so the copy semantics for our
objects is simple deep copying of underlying data. On the
other hand I can't resign deep copying, and use mere copying
of inner pointers. It follows, that using 'std::sort' for
sorting our array is extremely wasteful. In my opinion,
better to use ANSI C's 'qsort', which copies only so-called
static part of objects, leaving alone underlying data.
Someone can advice to use 'std::sort' on array of pointers,
but what I have is an array of objects, and I can't make
signigicant changes to data representation.
No, the ANSI C qsort has no advantages over std::sort. And the
fact that qsort must copy items in order to sort them - and
std::sort does not - is in fact a significant disadvantage for
qsort. Why copy items if it's not necessary, or if there are
more efficient techniques available?
So how does std::sort rearrange items in a container if not by
copying them? The answer is: by swapping them.
|
And how does it swap them? The typical implementation of
std::swap is:
template< typename T >
void
swap( T& a, T& b )
{
T tmp( a ) ;
a = b ;
b = a ;
}
A copy and two assignments.
Of course, std::sort is not required to use std::swap -- g++
doesn't use it for all of the exchanges, for example (and I
think earlier versions never used it). Once the size of the
partitions is less than a certain limit, g++ uses an insertion
sort, which doesn't swap at all, and if the quick sort starts to
degenerate, it switches to heap sort, which doesn't swap either.
| Quote: | So the program should simply implement a reasonably efficient
std::swap for the type of contained item.
|
That's a good idea in general, but it won't necessarily help
std::sort.
--
James Kanze GABI Software
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Sat May 13, 2006 12:21 am Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
In article <1147425356.843561.115520 (AT) g10g2000cwb (DOT) googlegroups.com>,
"kanze" <kanze@gabi-soft.fr> wrote:
| Quote: | but DR 187 requires an
implementation of iter_swap which doesn't work if the value
types are different, without introducing an additional
constraint to require that they be the same
|
DR 187 specifically does not require failure in this event. It only
requires that swap(*a, *b) work (and that's unqualified swap). The
client could easily create such a swap overload. Motivation might be
(for example) to make the following code work (or code similar to it
involving proxy references):
#include <vector>
#include <cassert>
int main()
{
bool x = true;
std::vector<bool> v(1);
std::iter_swap(v.begin(), &x);
assert(!x);
assert(v[0]);
}
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Carlos Moreno
Guest
|
| Posted: Sat May 13, 2006 1:21 am Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
Carl Barron wrote:
| Quote: | Since writing the predicate is at least as simple as writing a compare
for qsort. I see no need for qsort except for legacy code.
|
You're joking, right? I mean, you were being sarcastic for the
purpose of ridiculing qsort... Right?
Writing the predicate for sort is so infinitely simpler than
writing the mega-twisted comparison function for std::sort that
it is really a joke to even mention both in the same phrase.
First of all, in a good fraction of the cases, you wouldn't even
write anything -- if you're sorting, it means the notion of
order makes sense for the type; if the notion of order in the
general sense applies, then you'd define operator< as part of
the class interface, and that's all std::sort would need.
Even if you need to write it, you write a function that receives
arguments of your type T, period. Not a pointer to void with
an extra parameter to indicate the size of each element's
memory footprint... Oh, God, it's so barbaric that it pains
me to even try to remember the details to describe them here!
Do not forget the fact that the comparison functor or op< is
in most cases inlined, making std::sort potentially faster.
In fact, in all the benchmarks that I've done (with at least
three or four different compilers, sorting built-in types),
std::sort has been at least twice as fast as qsort for the
exact sets of data -- in all the cases, I sorted 1000 sets,
all randomly shuffled (and used the exact same ranges for
each instance of sort and qsort)
Carlos
--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
johnchx2@yahoo.com
Guest
|
| Posted: Sat May 13, 2006 1:21 am Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
kanze wrote:
| Quote: | johnchx2 (AT) yahoo (DOT) com wrote:
I thought that this might be the case, but (a) I can't find
any requirement in the standard that it do so and (b) the
implementations I have handy (STLPort and libstdc++) appear to
require the copy constructor and assignment operator, even
though I provide a suitable swap() overload.
Well, that's a requirement of the standard.
|
How so? I actually expected to find requirements similar to those for
the standard containers (assignable and copy-able) but if they're
there, I overlooked them. The iterators are required to be mutable,
but I didn't see any requirement that their value types be assignable
or copyable. What am I missing?
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Sat May 13, 2006 12:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
In article <6n%8g.18423$3B5.190807 (AT) weber (DOT) videotron.net>,
Carlos Moreno <moreno_at_mochima_dot_com (AT) mailinator (DOT) com> wrote:
| Quote: | In fact, in all the benchmarks that I've done (with at least
three or four different compilers, sorting built-in types),
|
This is THE weakness. If we remain unconcerned about sorting
heavyweight types, then we (C++) are doomed. Fortunately I don't think
that is in the cards for C++0X. But it has been for C++03. I'm not
saying qsort is better. I'm saying std::sort could be A LOT better (and
looks promising for C++0X).
-Howard
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
James Kanze
Guest
|
| Posted: Sun May 14, 2006 9:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
johnchx2 (AT) yahoo (DOT) com wrote:
| Quote: | kanze wrote:
johnchx2 (AT) yahoo (DOT) com wrote:
I thought that this might be the case, but (a) I can't find
any requirement in the standard that it do so and (b) the
implementations I have handy (STLPort and libstdc++) appear
to require the copy constructor and assignment operator,
even though I provide a suitable swap() overload.
Well, that's a requirement of the standard.
How so? I actually expected to find requirements similar to
those for the standard containers (assignable and copy-able)
but if they're there, I overlooked them. The iterators are
required to be mutable, but I didn't see any requirement that
their value types be assignable or copyable. What am I
missing?
|
I can't find them either. What I think is required is that the
iterators be dereferenciable -- if not, they're not
RandomAccessIterators. If it1 and it2 are random access
iterators, the expression *it1 = *it2 must be legal. As it
stands, however, I think the standard requires std::sort to work
even when the value type is neither copy constructable nor
default constructable, and doesn't have a specialization for any
sort of swap. Which is, I think, an impossible condition.
Howard Hinnant has mentionned a defect report, but I don't think
it covers this issue.
--
James Kanze kanze.james (AT) neuf (DOT) fr
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
9 place Sémard, 78210 St.-Cyr-l'École, France +33 (0)1 30 23 00 34
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
Howard Hinnant
Guest
|
| Posted: Sun May 14, 2006 11:21 pm Post subject: Re: Can 'qsort' have an advantage over 'std::sort'? |
|
|
In article <e47mpv$lis$1 (AT) emma (DOT) aioe.org>,
James Kanze <kanze.james (AT) neuf (DOT) fr> wrote:
| Quote: | but I didn't see any requirement that
their value types be assignable or copyable. What am I
missing?
I can't find them either. What I think is required is that the
iterators be dereferenciable -- if not, they're not
RandomAccessIterators. If it1 and it2 are random access
iterators, the expression *it1 = *it2 must be legal. As it
stands, however, I think the standard requires std::sort to work
even when the value type is neither copy constructable nor
default constructable, and doesn't have a specialization for any
sort of swap. Which is, I think, an impossible condition.
Howard Hinnant has mentionned a defect report, but I don't think
it covers this issue.
|
Agreed. CopyAssignable is covered by 25p4:
| Quote: | If an algorithm's Effects section says that a value pointed to by any
iterator passed as an argument is modified, then that algorithm has an
additional type requirement: The type of that argument shall satisfy the
requirements of a mutable iterator
|
24.1.3p1:
If X is mutable, *a = t is valid.
But CopyConstructible I can't find either.
However the C++0X working draft:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2006/n2009.pdf
has in the description of sort, 25.3.1.1p2:
| Quote: | Requires: The type of *first shall satisfy the Swappable requirements
|
and Swappable is defined in 20.1.4p2:
| Quote: | The Swappable requirement is met by satisfying one or more of the
following conditions:
* T is Swappable if T satisfies the CopyConstructible requirements
(20.1.3) and the Assignable requirements (23.1);
* T is Swappable if a namespace scope function named swap exists in
the same namespace as the definition of T, such that the expression
swap(t,u) is valid and has the semantics described in Table 33.
|
The intent there was that CopyAssignable and CopyConstructible were
already specified somewhere.
However N1860 (not yet accepted into the working draft) has for sort:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1860.html#25.3%2
0-%20Sorting%20and%20related%20operations
| Quote: | Requires: The type of *first shall satisfy the Swappable requirements
(20.1.4), the MoveConstructible requirements, and the MoveAssignable
requirements.
|
So this does look like a defect, and there does seem to be a fix already
in the works.
-Howard
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ] |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
