Can you swap a std::queue with a lambda comparator?

Question

I am trying to clear a std::queue using the example in https://stackoverflow.com/a/709161/837451 via a swap. However, it doesn't seem to work with a lambda comparator due to the "deleted function" error.

Minimal working failing example:

#include <queue>
#include <vector>
using namespace std;
int main(){
    typedef pair<int,float> ifpair;
    auto comp = []( ifpair a,  ifpair b ) { return a.second > b.second; };
    typedef priority_queue< ifpair , vector<ifpair>, decltype( comp ) > t_npq;
    t_npq npq( comp );
    //do something with npq. finish using it (without emptying it) and clear for next round
    t_npq empty( comp );
    swap(npq , empty);
}

Compile with

g++ -std=c++11 /tmp/test.cpp -o /tmp/o

And I get the following error:

/usr/include/c++/4.8/bits/move.h:176:11: error: use of deleted function ‘main()::__lambda0& main()::__lambda0::operator=(const main()::__lambda0&)’
   __a = _GLIBCXX_MOVE(__b);
       ^
/tmp/test.cpp:6:18: note: a lambda closure type has a deleted copy assignment operator

g++ -v

Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/4.8/lto-wrapper
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.8.1-10ubuntu9' --with-bugurl=file:///usr/share/doc/gcc-4.8/README.Bugs --enable-languages=c,c++,java,go,d,fortran,objc,obj-c++ --prefix=/usr --program-suffix=-4.8 --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.8 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --enable-gnu-unique-object --enable-plugin --with-system-zlib --disable-browser-plugin --enable-java-awt=gtk --enable-gtk-cairo --with-java-home=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64/jre --enable-java-home --with-jvm-root-dir=/usr/lib/jvm/java-1.5.0-gcj-4.8-amd64 --with-jvm-jar-dir=/usr/lib/jvm-exports/java-1.5.0-gcj-4.8-amd64 --with-arch-directory=amd64 --with-ecj-jar=/usr/share/java/eclipse-ecj.jar --enable-objc-gc --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu
Thread model: posix
gcc version 4.8.1 (Ubuntu/Linaro 4.8.1-10ubuntu9) 

I'm kind of curious what exactly is going on here but more importantly I would really like to know how to make this work.

Answer 1

While the result of a lambda expression is move constructible it isn't necessarily move assignable and certainly not copyable. I would just bypass the problem by using a std::reference_wrapper<decltype(comp)> for the comparator object:

typedef pair<int,float> ifpair;
auto comp = []( ifpair a,  ifpair b ) { return a.second > b.second; };
typedef priority_queue< ifpair , vector<ifpair>,
                        std::reference_wrapper<decltype( comp ) >> t_npq;
t_npq npq( std::ref(comp) );
t_npq empty( std::ref(comp) );
swap(npq , empty);

Since the full type information of the lambda expression is retained by the reference wrapper, this should work even if the closure isn't empty and, where viable, it should be possible to inline the function.

Answer 2

Have you tried to use std::function?

#include <queue>
#include <vector>
#include <functional>
using namespace std;
int main(){
    typedef pair<int,float> ifpair;
    std::function< bool ( ifpair, ifpair )> comp = []( ifpair a,  ifpair b ) { return a.second > b.second; };
    typedef priority_queue< ifpair , vector<ifpair>, decltype( comp ) > t_npq;
    t_npq npq( comp );
    //do something with npq. finish using it (without emptying it) and clear for next round
    t_npq empty( comp );
    swap(npq , empty);
}

Answer 3

Lambdas aren't assignable – 5.1.2/19:

The closure type associated with a lambda-expression has a deleted default constructor and a deleted copy assignment operator.

The swap of the containers wants to assign the comparators, too, so that doesn't work.

However, you can easily make it work by converting the stateless lambda to a function pointer first:

bool (*p)(ifpair, ifpair) = [](ifpair a, ifpair b) { return a.second > b.second; };

Now use:

priority_queue<ifpair, vector<ifpair>, bool(*)(ifpair, ifpair)>

(You might want to introduce a typedef for the function type: using comp_type = bool(iftype, iftype), and then use comp_type * everywhere.)

Answer 4

As the compile error indicates, lambda objects aren't assignable. You can use a different type of functor for the queue but still write it as a labmda:

1. Use std::function<bool(ifpair,ifpair)>: http://ideone.com/HZywoV

   But this adds (probably noticable) overhead due to some more indirections in the implementation of std::function but I guess this heavily depends on the implementation of the standard library and the compiler optimizations. Might be the nicest solution regarding how the code looks though.

2. Use a function pointer bool(*)(ifpair,ifpair): http://ideone.com/ZhFq3C

   This should not suffer from any overhead compared to std::function but to your current solution, since there might be some compiler optimizations done to your lambda code which are then not possible (i.e. inlining it into the rest of the std::queue code which for example eliminates copying the two pairs). Using function pointers looks pretty old-school though.

3. Use a custom functor class which can be as simple as: http://ideone.com/9pcQFc

   template<typename Pair>
   struct GreaterBySecond {
       bool operator()(Pair a, Pair b) const {
           return a.second > b.second;
       }
   };
   

   This should eliminate all overhead discussed above. I'd prefer this if performance matters.