a refinement of STL??

Discussion in 'C++' started by alex leung, Jul 4, 2003.

  1. alex leung

    alex leung Guest

    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??
    alex leung, Jul 4, 2003
    #1
    1. Advertising

  2. "alex leung" <> 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
    Michiel Salters, Jul 4, 2003
    #2
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. John Hoge

    Search Refinement

    John Hoge, Dec 1, 2004, in forum: ASP .Net
    Replies:
    2
    Views:
    335
    JerryK
    Dec 2, 2004
  2. Allan Bruce

    To STL or not to STL

    Allan Bruce, Oct 16, 2003, in forum: C++
    Replies:
    41
    Views:
    1,012
    Christopher Benson-Manica
    Oct 17, 2003
  3. Replies:
    4
    Views:
    784
    Daniel T.
    Feb 16, 2006
  4. Donkey Hot
    Replies:
    7
    Views:
    479
    Nigel Wade
    Feb 4, 2008
  5. sanjayayogi
    Replies:
    3
    Views:
    127
    Martin DeMello
    Apr 4, 2009
Loading...

Share This Page