Geek Answers Handbook

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

I am trying to clear std :: queue using an example in https://stackoverflow.com/a/2202/ via a swap. However, it does not work with the lambda comparator due to a "remote function" error.

Minimum working bad 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 curious what exactly is going on here, but more importantly, I would really like to know how to do this.

+6
source share
4 answers

While the result of the lambda expression moves constructively, it is not necessarily carried over by the assignable and, of course, is not copied. I just got around the problem using 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 full information about the type of lambda expression is stored by the reference shell, this should work even if the closure is not empty and, when it is viable, it should be possible to inline the function.

+7
source

Have you tried using 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); }
+1
source

Lambdas are not assigned - 5.1.2 / 19:

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

Container swapping also wants to assign comparators, so this will not work.

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

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

+1
source

As a compilation error indicates, lambda objects cannot be assigned. You can use a different type of functor for the queue, but still write it like labmda:

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

    But this adds a (possibly noticeable) overhead due to some limitations in the implementation of std::function , but I assume that it largely depends on the implementation of the standard library and compiler optimization. Perhaps the most pleasant solution is how the code looks.

  • Use the pointer to the bool(*)(ifpair,ifpair) function bool(*)(ifpair,ifpair) : http://ideone.com/ZhFq3C

    This should not suffer from any overhead compared to std::function , but with your current solution, as there may be some kind of compiler optimization made for your lambda code, which is then impossible (i.e. inserting its the rest of the std::queue code, which, for example, eliminates the copying of two pairs). However, using function pointers seems pretty old.

  • Use a special class of functors that can be simple: 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 the overheads discussed above. I would prefer this if performance matters.

+1
source

More articles:


All Articles