Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > a refinement of STL??

Reply
Thread Tools

a refinement of STL??

 
 
alex leung
Guest
Posts: n/a
 
      07-04-2003
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??




 
Reply With Quote
 
 
 
 
Michiel Salters
Guest
Posts: n/a
 
      07-04-2003
"alex leung" <(E-Mail Removed)> wrote in message news:<3f050099$1@shknews01>...
> 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,
--
Michiel Salters
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lack of refinement hurts entry-level DSLRs RichA Digital Photography 103 04-30-2010 06:45 AM
Kill a process by name and PID - needs refinement sanjayayogi Ruby 3 04-04-2009 10:06 AM
Refinement of a Java prog called by PHP Donkey Hot Java 7 02-04-2008 10:32 AM
Great Images Require Layers of Refinement Wayne J. Cosshall Digital Photography 1 04-05-2007 02:06 AM
Search Refinement John Hoge ASP .Net 2 12-02-2004 01:37 AM



Advertisments