std::iter_swap using user-defined swap?

This is a discussion on std::iter_swap using user-defined swap? within the C++ Programming forums, part of the General Programming Boards category; I have a question concerning this post: Possibly even faster, especially for member types like std::string: Code: template <typename T> ...

  1. #1
    The larch
    Join Date
    May 2006
    Posts
    3,573

    std::iter_swap using user-defined swap?

    I have a question concerning this post:
    Possibly even faster, especially for member types like std::string:
    Code:
    template <typename T>
    typename std::vector<T>::iterator
    fast_erase(std::vector<T> &vec, typename std::vector<T>::iterator it)
    {
      assert(it != vec.end());
      std::iter_swap(it, vec.rbegin());
      vec.pop_back();
      return it;
    }
    It's not entirely clear to me how it would work for user-defined types (and would it really do the right thing for strings). Here's my little test program where only the last call to swap calls my "efficient" swap for class B.

    Code:
    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    class B
    {
        public:
        B() {}
        B(const B&) {std::cout << "B(const B&)\n";}
        const B& operator= (const B&) {std::cout << "B::=\n"; return *this;}
        void swap(B&) {std::cout << "B::swap\n";}
    };
    
    void swap(B& a, B& b)
    {
        a.swap(b);
    }
    
    int main()
    {
        std::vector<B> vec_b;
        vec_b.push_back(B());
        vec_b.push_back(B());
    
        std::cout << "\niter_swap:\n";
        std::iter_swap(vec_b.begin(), vec_b.begin()+ vec_b.size() - 1); //operator=
    
        std::cout << "\nstd::swap:\n";
        std::swap(vec_b.front(), vec_b.back()); //operator=
    
        std::cout << "\nusign std::swap + swap:\n";
        using std::swap;
        swap(vec_b.front(), vec_b.back()); //operator=
    
        std::cout << "\n::swap:\n";
        ::swap(vec_b.front(), vec_b.back()); //swap(B&, B&)
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,648
    >> It's not entirely clear to me how it would work for user-defined types (and would it really do the right thing for strings).
    std::iter_swap(it1, it2) is typically identical to std::swap(*it1, *it2).
    std::swap() only requires that the type is "assignable".
    A type T is "assignable" if it supports "t = u", where the return type is T& and t and u are equivalent afterwords.
    std::string is an assignable type so it "does the right thing".

    >> Here's my little test program...
    As you can see, both std::swap() and std::iter_swap() invoke operator=().

    gg

  3. #3
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Which compiler do you use? When I compile with GCC 4.1.2 and run, I get
    Code:
    B(const B&)
    B(const B&)
    B(const B&)
    
    iter_swap:
    B::swap
    
    std::swap:
    B(const B&)
    B::=
    B::=
    
    usign std::swap + swap:
    B::swap
    
    ::swap:
    B::swap
    In other words, everything except the explicit std::swap call uses the specialized swap. Your compiler does not correctly implement argument-dependent lookup (ADL or Koenig-lookup).

    Therefore, std::iter_swap(i1, i2) is not identical to std::swap(*i1, *i2) - it is identical to using std::swap; swap(*i1, *i2) unless the std::iter_swap is overloaded itself in the std namespace. It could be done for e.g. std::list by just relinking nodes. My implementation doesn't, though.

    std::swap() also requires that the type is copy-constructible. In total, it requires that the type is copyable (the unification of copy-constructible and copy-assignable).
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  4. #4
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Which compiler do you use?
    MingW GCC 3.4.2 (guess I should update some time?)

    I also tried it with VC++ 2005 and the last two swaps use B::swap, but not iter_swap (even if using std::swap; comes first).
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  5. #5
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,648
    Does the non-draft version of the standard say that std::iter_swap() should be implemented using std::swap() - or is that left up to the implementation as the draft version implies?

    That may explain why MSDN says "swap should be used in preference to iter_swap"- since the code is more explicit that way.

    gg

  6. #6
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Apparently, the behaviour of iter_swap is underspecified. See:
    http://www.open-std.org/jtc1/sc22/wg...n2457.html#187

    The current draft for C++09 says that the effects of iter_swap are simply swap(*a, *b). It also requires that the value types of the two iterators are the same, which apparently wasn't a safe assumption previously. (At least judging by the hoops through with the libc++ implementation jumps.)
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  7. #7
    The larch
    Join Date
    May 2006
    Posts
    3,573
    So how's the idea to make two different fast erase functions, one that uses the member function swap and one that uses just assignment?

    The idea behind not using std::swap is that if the function is called with a class that does not have the swap member function, you'll get a compiler error (rather than silently using an inferior erase method) and you'll just need to use the second function.

    Code:
    template <typename T>
    typename std::vector<T>::iterator
    fast_erase_swappable(std::vector<T> &vec, typename std::vector<T>::iterator it)
    {
      assert(it != vec.end());
      it->swap( *vec.rbegin());
      vec.pop_back();
      return it;
    }
    
    template <typename T>
    typename std::vector<T>::iterator
    fast_erase_pod(std::vector<T> &vec, typename std::vector<T>::iterator it)
    {
      assert(it != vec.end());
      *it = vec.back();
      vec.pop_back();
      return it;
    }
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  8. #8
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by anon View Post
    The idea behind not using std::swap is that if the function is called with a class that does not have the swap member function, you'll get a compiler error (rather than silently using an inferior erase method) and you'll just need to use the second function.
    Not all fast-swaps are implemented as a member function called swap. Just those in the standard library and those that follow the convention. But you could, for example, implement it as a static method. Or a free function, a friend if necessary.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  9. #9
    The larch
    Join Date
    May 2006
    Posts
    3,573
    So, if that is the case how would you write the function?
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  10. #10
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,648
    How about:
    Code:
    template <typename T>
    typename std::vector<T>::iterator
    fast_erase(std::vector<T> &vec, typename std::vector<T>::iterator it)
    {
        assert(it != vec.end());
    
        using std::swap;
        swap(*it, *vec.rbegin());
        vec.pop_back();
        return it;
    }
    Then you just need a compiler that looks up the correct swap() to call.

    gg

  11. #11
    The larch
    Join Date
    May 2006
    Posts
    3,573
    Well, for STL types std::swap is not the right thing to use because it uses copy assignment and not the special efficient swap() member functions.

    One thing might be using function objects but it doesn't feel right to let the user write the most crucial part of the function. If I ever need it in practice, I guess I'll use it on a case by case basis.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  12. #12
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,893
    Quote Originally Posted by anon View Post
    Well, for STL types std::swap is not the right thing to use because it uses copy assignment and not the special efficient swap() member functions.
    The right thing to use is the ADL-detected swap(). You'll have to leave the decision whether using it over a simple assignment is really a good idea to the user.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  13. #13
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,648
    Also keep in mind that the standard specifies a version of std::swap(x, y) for all the std::containers - the effects of which are "x.swap(y)".

    I tried out the version of fast_erase() I last posted, where T was a vector<int> - and even VC++ 6.0 "did the right thing" by calling the specialized version of std::swap() - which calls "x.swap(y)".
    VC++ 2005 also "did the right thing".

    gg

  14. #14
    The larch
    Join Date
    May 2006
    Posts
    3,573
    OK thanks.
    I might be wrong.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. STL Map Problem with user defined Class
    By noobcpp in forum C++ Programming
    Replies: 21
    Last Post: 07-21-2008, 12:02 PM
  2. Replies: 14
    Last Post: 03-02-2008, 12:27 PM
  3. User defined 2-D array problem
    By Turtal in forum C Programming
    Replies: 5
    Last Post: 12-15-2007, 12:23 AM
  4. Stl lists and user defined types
    By figa in forum C++ Programming
    Replies: 8
    Last Post: 03-28-2005, 11:09 AM
  5. Help! User defined functions
    By AdrenalinFlow in forum C Programming
    Replies: 3
    Last Post: 02-22-2003, 06:36 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21