std::iter_swap using user-defined swap?

[anon]

I have a question concerning this post:

Possibly even faster, especially for member types like std::string:

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.

#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&)
}

[Codeplug]

>> 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

[CornedBee]

Which compiler do you use? When I compile with GCC 4.1.2 and run, I get

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).

[anon]

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).

[Codeplug]

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

[CornedBee]

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.)

[anon]

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.

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;
}

[CornedBee]

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.

[anon]

So, if that is the case how would you write the function?

[Codeplug]

How about:

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

[anon]

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.

[CornedBee]

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.

[Codeplug]

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

[anon]

OK thanks.