a refinement of STL??

A

alex leung

when I studing the "stl_algobase.h" (SGI Imp. of STL), I find the following
defination of swap:
template <class _Tp>
inline void swap (_Tp& __a, _Tp& __b){
_Tp __tmp = __a;
__a = __b;
__b = __tmp;
}
Couples of assignment operator, copy constructor and destructor is called
which seens affecting the efficiency greatly. imagine how many calls to
swap() in a sorting algorithm. so I started to do the refinement (not
exactly the code I used, just to show the concept):

template <class Tp>_allocate (size_t _size =1); //malloc
template <class Tp> _deallocate (Tp*);
template <class Tp> _copy (Tp *_dest, const Tp&_src); //memcpy

template <class _Tp>
inline void swap (_Tp& __a, _Tp& __b){
_Tp *_tmp = _allocate<_Tp> (); //To allocate space for temp object.
_copy (_tmp , __a);
_copy (&__a, __b);
_copy (&__b, *_tmp);
_deallocate (_tmp); //reverse of _allocate
}

No constructor nor operator= called any more. I have done a simple test with
container like vector, and it works just as I expected. what I worry about
is that,
would there be any safety problem, such as memory alignment?
Is it portable? would it be as fine if I use it on another platform.

One potential danger I can see is for a class, which store the pointer
"this" for its internal use. but what is the practical use to store "this"
statically? so I finally ignore this case.

anyway, could anybody give me a suggestion??
 
M

Michiel Salters

alex leung said:
when I studing the "stl_algobase.h" (SGI Imp. of STL), I find the following
defination of swap:
template <class _Tp>
inline void swap (_Tp& __a, _Tp& __b){
_Tp __tmp = __a;
__a = __b;
__b = __tmp;
}
Couples of assignment operator, copy constructor and destructor is called
which seens affecting the efficiency greatly. imagine how many calls to
swap() in a sorting algorithm.

Watch it - this is the "base" version. For T's where a more efficient swap
can be done, a specialized version may exist. For UDT's these will not
even be part of the STL implementation delivered with your compiler,
but come with the UDT.
so I started to do the refinement (not
exactly the code I used, just to show the concept):

template <class Tp>_allocate (size_t _size =1); //malloc
template <class Tp> _deallocate (Tp*);
template <class Tp> _copy (Tp *_dest, const Tp&_src); //memcpy

template <class _Tp>
inline void swap (_Tp& __a, _Tp& __b){
_Tp *_tmp = _allocate<_Tp> (); //To allocate space for temp object.
_copy (_tmp , __a);
_copy (&__a, __b);
_copy (&__b, *_tmp);
_deallocate (_tmp); //reverse of _allocate
}

Undefined behavior if T is not a POD. Going to the heap is much
slower as simply defining char tmp[sizeof(T)];. This isn't portable
either, though.
No constructor nor operator= called any more. I have done a simple test with
container like vector, and it works just as I expected. what I worry about
is that, would there be any safety problem, such as memory alignment?
Is it portable? would it be as fine if I use it on another platform.

Nor portable, of course. It certainly won't work with many string
implementations that contain the small-string optimalization. Of course,
a STL implementaion isn't needed on recent compilers which have a proper
Standard Library in std::. On such implementations, you can't even
change it.
One potential danger I can see is for a class, which store the pointer
"this" for its internal use. but what is the practical use to store "this"
statically? so I finally ignore this case.

A common case is the small-string optimalization. For long strings, the
char* of a string will point to the heap, but for small strings the
char* points within the string object itself. This saves expensive
heap allocations, and improves locality of reference. In this case,
when you swap two strings the lengths will be swapped but the pointers
will still point to their original locations. This will be a disaster
if only one string is short enough to be located within the object,
else it will be just surprising. Sorting will obviously fail.
anyway, could anybody give me a suggestion??

Don't. On current std:: implementations, the compiler vendor can
use a non-portable hook to the compiler internals to look at each T.
It can then provide your swap implementation if that works, use the
char[sizeof(T)] trick if that makes sense, use a specialized swap
version or use the trivial version if and only if the other
approaches fail. That's the advantage of an integrated customized
Standard Library, it can use tricks internally you may not use.

For your own classes, provide your own
template< > std::swap( myUDT&, myUDT& );
specialization. It can of course do a C-style memcpy if myUDT is a
simple C-style struct.

Regards,
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top