About swap algorithm.
Isaac Rodriguez
I am just reading an article in InformIT about the swap algorithm, and it
says something that I believe is wrong. They are showing various
implementations of it and the first one looks like this.
template<class T> void swap (T& t1, T& t2)
{
T temp = t1;
t1 = t2;
t2 = temp;
}
The article says that this is the implementation used in STL. Now my
question is, if this is the implementation that STL does of the swap()
algorithm, how come that the algorithm is used for exception safety in
assignment operators? This doesn't make much sense to me, so I believe that
the article is actually wrong. Any comments are highly appreciated.
--
Regards,
Isaac Rodriguez
=======================
Software Engineer - Autodesk
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
Daniel Anderson
you are confuse with the container swap. read E.4.3 in TC++PL.
Danderson
"Isaac Rodriguez" <isaac.r...@autodesk.com> a écrit dans le message de
news: 10606039...@hqnntp01.autodesk.com...
Ivan Vecerina
news:10606039...@hqnntp01.autodesk.com...
| I am just reading an article in InformIT about the swap algorithm, and it
| says something that I believe is wrong. They are showing various
| implementations of it and the first one looks like this.
|
| template<class T> void swap (T& t1, T& t2)
| {
| T temp = t1;
| t1 = t2;
| t2 = temp;
| }
This *is* the(/a conform) default implementation of the std::swap
function. However, this function is specialized by all standard
containers. It is also encouraged that all user-defined classes
that have a throwing copy constructor/assignment operator
specialize this function.
And yes, the latter tends to be cumbersome:
namespace MyNamespace {
template<class T>
class MyContainer {
/*....ctrs, assignment, and whatever....*/
void swap( MyContainer<T> other )
{ /*...implement memberwise swap...*/ }
};
}
// specialize the standard swap operation
namespace std {
template<class T> inline
void swap( MyNamespace::MyContainer<T>& x
, MyNamespace::MyContainer<T>& y )
{ x.swap(y); }
}
There is no built-in support for non-throwing swap operations.
Yes, all this would be simpler if a built-in swap operatior
existed in C++. It is in the list of often-requested ones...
hth,
--
http://www.post1.com/~ivec
Richard Smith
> It is also encouraged that all user-defined classes
> that have a throwing copy constructor/assignment operator
> specialize this function.
Specialize, perhaps, but that is not what you've done in
your code. You've overloaded std::swap which is not allowed
[17.4.3.1/1]. Unfortunately as the standard doesn't permit
partial specialisations of functions (though this may change
-- see N1295), putting an illegal overload into namespace
std is often the best way to supply custom swap functions.
The alternative, which appears to be the Standards
Committee's current favourite solution [N1439], relies on
Standard headers being written in such a way as to enable
ADL on swap, e.g. with an unqualified call to swap after a
using declaration for std::swap:
using std::swap;
swap(a, b);
With this, you just put a swap function in your own
namespace, and let ADL find it. There's perhaps even an
argument of defining it inline as a friend function so
it is *only* found through ADL:
template <class T, class Allocator>
class container
{
// ...
friend void swap( container<T, Allocator>& a,
container<T, Allocator>& b )
{
using std::swap;
swap( a.data, b.data );
swap( a.allocator, b.allocator );
}
}
Unfortunately relying on ADL can break in the presence of a
user-defined swap function which takes two arguments
[DR225], and many STL vendors have, quite wisely, chosen not
to support finding swap overloads of swap through ADL.
--
Richard Smith
Siemel Naran
news:SOVZa.4773
> They are right,
> you are confuse with the container swap. read E.4.3 in TC++PL.
But could even container swap throw? What if you run out of stack space?
template <class T>
void std::vector<T>::swap(vector& that) {
swap(this->d_size, that.d_size);
swap(this->d_data, that.d_data);
swap(this->d_capacity, that.d_capacity);
}
The standard swap is
T temp(lhs);
lhs = rhs;
rhs = temp;
This create a T object on the stack. For us T is size_type or T* -- ie. an
integer or pointer, both builtin types. It is possible that the compiler
could run out of stack space. In most implementations I doubt this would
actually happen. Also the compiler may allocate temp in a register.
--
+++++++++++
Siemel Naran
Siemel Naran
> // specialize the standard swap operation
> namespace std {
> template<class T> inline
> void swap( MyNamespace::MyContainer<T>& x
> , MyNamespace::MyContainer<T>& y )
> { x.swap(y); }
> }
You can rely on Koenig lookup.
In a function call function(a,b) not qualified for a particular namespace
the compiler looks for a match A::function(b) if function is an operator,
then looks in the namespace where 'a' and 'b' live for a match, then looks
in the current namespace.
For us function is swap which is not an operator (unfortunately). In
swap(mycontainer1, mycontainer2), mycontainer1 and mycontainer2 live in
namespace MyNamespace. So the compiler will look for function swap in
namespace MyNamespace.
Of course, this assumes that standard library implementors use swap(a,b)
rather than std::swap(a,b). For example, the sort algorithm calls swap.
But the standard algorithms already live in namespace std, and there's no
need to qualify the namespace anyway.
But in your own functions keep this in mind. For example in the code below
we wish to call std::floor for T as float or double. But it is possible
that the user has written their own numerical type, say
MyNamespace::SuperFloat, and then we'd want to call MyNamespace::floor(const
MyNamespace::SuperFloat&).
namespace enhanced
{
template <class T>
class round_down
{
public:
explicit round_down(int precision) : factor(calc_factor(precision))
{ }
T operator()(T x) const
{
using namespace std;
return floor(x*factor)/factor;
}
private:
static T calc_factor(int precision)
{
using namespace std;
return pow(T(10),(T)precision);
}
const T factor;
};
}
On the downside, many compilers don't support Koenig lookup.
--
+++++++++++
Siemel Naran
Siemel Naran
> The alternative, which appears to be the Standards
> Committee's current favourite solution [N1439], relies on
> Standard headers being written in such a way as to enable
> ADL on swap, e.g. with an unqualified call to swap after a
> using declaration for std::swap:
>
> using std::swap;
> swap(a, b);
How does this compare with
using namespace std;
swap(a, b);
--
+++++++++++
Siemel Naran
Richard Smith
> > using std::swap;
> > swap(a, b);
>
> How does this compare with
>
> using namespace std;
> swap(a, b);
Different in a number of important respects. Take this
code for example.
namespace std {
template <class T> void swap( T&, T& );
}
namespace my_ns {
class A; // This is important to this
void swap( A&, A& ); // example even though it is not
// used.
class B {}; // Don't bother overloading swap for this
// -- perhaps because the default one in
// namespace std is good enough.
void f() {
B a, b;
using std::swap;
swap(a, b);
}
}
Now, when swap(a, b) is called, the set of candiate
functions is constructed by considering both functions found
by ordinary lookup and by ADL. Ordinary lookup starts in
the inner most scope (block scope) and proceeds outwards
until it finds the name. In this case, the first swap name
it finds is the using declaration, so the candidate
functions found by ordinary lookup are limited to those in
namespace std -- here, just the template one. For ADL, the
only associated namespaces for the arguments (of type
my_ns::B) is the namespace my_ns, and lookup just occurs in
that namespace (it doesn't, for example, continue outwards
until if finds a match). In this example, it finds the swap
for class A. Therefore, for overload resolution, the
candidate set of functions includes the template one and the
non-template one, and the template one in namespace std is
selected.
Now let's replace the using declaration with a using
directive:
void f() {
B a, b;
using namespace std;
swap(a, b);
}
ADL still finds exactly the same function -- the one for
class A. However, ordinary lookup also finds this one.
This can seem counter-intuitive, but it due to the way in
which using directives work. Unlike a using declaration, a
using directive does not pull names from that namespace into
the current scope (which would be block scope in this
example), but instead pulls them into the innermost scope
that encloses both target namespace and the scope containing
the using directive. In this case, the using directive's
scope is ::my_ns::f() and the target namespace is ::std,
which means the innermost enclosing scope is the global
namespace. Thus, during ordinary lookup, lookup proceeds
outwards until it finds a match, and this time, the first
swap it finds is the one in my_ns. So, both ordinary lookup
and ADL find the same overload of swap -- the wrong one --
and the code fails to compile.
In template code, such as you'd probably find in the STL,
life is more complicated because of two-phase lookup, but
the issues are broadly the same.
--
Richard Smith
Bo Persson
"Siemel Naran" <Sieme...@REMOVE.att.net> skrev i meddelandet
news:6qj_a.98770$0v4.6...@bgtnsc04-news.ops.worldnet.att.net...
> "Ivan Vecerina" <iv...@myrealbox.com> wrote in message news:3f38a533
>
> > // specialize the standard swap operation
> > namespace std {
> > template<class T> inline
> > void swap( MyNamespace::MyContainer<T>& x
> > , MyNamespace::MyContainer<T>& y )
> > { x.swap(y); }
> > }
This isn't a specialization, but an overload of the function.
Overloads are not allowed.
>
> You can rely on Koenig lookup.
No, you cannot. Library elements should not rely on Koenig lookup,
because that would reserve the library names not only in namespace std
but in *all* namespaces. If I define the functions find(), copy(), and
equal() in my namespace, I generally wouldn't like std::vector or
std::sort to use my functions instead of their std:: counterparts,
just because I happen to declare a std::vector<mytype> somewhere.
There might be reasons to have another rule specifically for swap, but
we are not there yet.
>
> For us function is swap which is not an operator (unfortunately).
In
> swap(mycontainer1, mycontainer2), mycontainer1 and mycontainer2 live
in
> namespace MyNamespace. So the compiler will look for function swap
in
> namespace MyNamespace.
>
> Of course, this assumes that standard library implementors use
swap(a,b)
> rather than std::swap(a,b). For example, the sort algorithm calls
swap.
And issue #229 proposes that all names x in the standard library
should actually be read as ::std::x.
> But the standard algorithms already live in namespace std, and
there's no
> need to qualify the namespace anyway.
*If* you rely on Koening lookup, there *is* a reason specify that the
compiler should look in namespace std as well, and not just in the
argument's namespaces.
Bo Persson
Ivan Vecerina
news:tAu_a.24017$dP1....@newsc.telia.net...
|
| "Siemel Naran" <Sieme...@REMOVE.att.net> skrev i meddelandet
| news:6qj_a.98770$0v4.6...@bgtnsc04-news.ops.worldnet.att.net...
| > "Ivan Vecerina" <iv...@myrealbox.com> wrote in message news:3f38a533
| >
| > > // specialize the standard swap operation
| > > namespace std {
| > > template<class T> inline
| > > void swap( MyNamespace::MyContainer<T>& x
| > > , MyNamespace::MyContainer<T>& y )
| > > { x.swap(y); }
| > > }
|
| This isn't a specialization, but an overload of the function.
| Overloads are not allowed.
|
| >
| > You can rely on Koenig lookup.
|
| No, you cannot.
So, what is a pragmatic solution for C++ programmers today ?
either:
- accept that expensive intermediate copies may be used when
standard algorithms such as swap_ranges/reverse/rotate/etc
are called -- and potentially other user-written algorithms.
- choose to rely on Koenig lookup -- works today on (some)
existing combinations of library implementation and C++
compiler (supports ADL).
- cheat and 'specialize' std::swap by overloading it -- which
tends to work, but is illegal...
Any alternative I am leaving out?
And yes, one should prefer to use the swap *member* function
of containers in his own code whenever possible.
This makes me wish there was a swap operator ( e.g. <-> )...
Regards,
Ivan
Siemel Naran
> > Of course, this assumes that standard library implementors use
> swap(a,b)
> > rather than std::swap(a,b). For example, the sort algorithm calls
> swap.
>
> And issue #229 proposes that all names x in the standard library
> should actually be read as ::std::x.
What is this rule 229?
{It is not a rule but an issue and refers to the C++ Standard Library
Issues list -- i.e. potential defects. -mod/fwg}
BTW, my file _algo.c and _algobase.c do not contain the text "std::". The
call unqualified swap(a,b), which seems to violate your rule 229.
--
+++++++++++
Siemel Naran
{Excessive quote snipped. -mod}
Siemel Naran
> Now let's replace the using declaration with a using
> directive:
>
> void f() {
> B a, b;
> using namespace std;
> swap(a, b);
> }
>
> ADL still finds exactly the same function -- the one for
> class A. However, ordinary lookup also finds this one.
> This can seem counter-intuitive, but it due to the way in
> which using directives work. Unlike a using declaration, a
> using directive does not pull names from that namespace into
> the current scope (which would be block scope in this
> example), but instead pulls them into the innermost scope
> that encloses both target namespace and the scope containing
> the using directive. In this case, the using directive's
> scope is ::my_ns::f() and the target namespace is ::std,
> which means the innermost enclosing scope is the global
> namespace. Thus, during ordinary lookup, lookup proceeds
> outwards until it finds a match, and this time, the first
> swap it finds is the one in my_ns. So, both ordinary lookup
> and ADL find the same overload of swap -- the wrong one --
> and the code fails to compile.
Very interesting. I may have to change my { using namespace std; return
floor(x*factor)/factor; } to { using std::floor; return
floor(x*factor)/factor; }.
BTW I tried your program on Borland 6 with both versions of f() -- one using
"using std::swap" and the other "using namespace std" -- and both compile.
According to what you say the second way should not compile. I'll try MSVC
7 tomorrow and get back to you.
--
+++++++++++
Siemel Naran
Siemel Naran
> "Richard Smith" <ric...@ex-parrot.com> wrote in message
> > Now let's replace the using declaration with a using
> > directive:
> >
> > void f() {
> > B a, b;
> > using namespace std;
> > swap(a, b);
> > }
> BTW I tried your program on Borland 6 with both versions of f() -- one using
> "using std::swap" and the other "using namespace std" -- and both compile.
> According to what you say the second way should not compile. I'll try MSVC
> 7 tomorrow and get back to you.
I just tried your program on MSVC 7.0.9466, which is known to be very
conforming. As you state, the "using std::swap" passes compile and
works, but the "using namespace std" way does not. Thanks.
-----------
Bo Persson
"Ivan Vecerina" <iv...@myrealbox.com> skrev i meddelandet
news:3f3b7d08$1...@news.swissonline.ch...
No, I think that is about it.
The pragmatist would probably choose the third alternative, as being
the least evil. The correct, but sometimes second best, choice is of
course to not use objects with expensive copies. :-)
In practise you cannot rely on Koening lookup, because (with a very
few exeptions) it is not specified if and how the standard library
uses other parts of the library. I have even seen proposals to forbid
it. The lastest proposal suggests that they should all use the std::
prefix.
>
>
> And yes, one should prefer to use the swap *member* function
> of containers in his own code whenever possible.
>
>
> This makes me wish there was a swap operator ( e.g. <-> )...
Probably something that should be considered.
Bo Persson
bo...@telia.com
johnchx
> So, what is a pragmatic solution for C++ programmers today ?
>
> either:
> - accept that expensive intermediate copies may be used when
> standard algorithms such as swap_ranges/reverse/rotate/etc
> are called -- and potentially other user-written algorithms.
> - choose to rely on Koenig lookup -- works today on (some)
> existing combinations of library implementation and C++
> compiler (supports ADL).
> - cheat and 'specialize' std::swap by overloading it -- which
> tends to work, but is illegal...
> Any alternative I am leaving out?
>
Possibly one: apply the algorithms to pointers, rather than directly
to the objects themselves. Not applicable in every case, but
certainly a strategy to be considered.
Long term, the standards committee seems to be leaning towards the ADL
solution. The current proposal seems to be to make calls to std
algorithms within the standard library std::-qualified by default,
with explicit exceptions for calls to swap made by certain specific
algorithms (as well as valarray transcendentals), which are guaranteed
to be *unqualified* calls.
Howard Hinnant's paper on this is at:
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1387.htm