I want to maintain a heap where the payloads are MoveConstructible (because they hold a std::unique_ptr inside.) Although the documentation suggests that the object must be MoveAssignable and MoveConstructible, doing so throws an error both in GCC and Clang.
Sample Code
I don't use an std::unique_ptr yet, but just disable the corresponding copy operators):
#include <iostream>
#include <vector>
#include <algorithm>
struct Data {
explicit Data(int value) : value(value) {}
int value;
bool operator<(const Data& d) const {
return value > d.value;
}
/**
* Commenting out the rest of the section for this struct
* gets the code working by using copy operator/ctor.
*/
explicit Data(const Data& d) = delete;
Data& operator=(const Data& d) = delete;
explicit Data(Data&& d) = default;
Data& operator=(Data&& d) = default;
};
struct MinHeap {
void Push(Data&& d) {
container_.emplace_back(std::move(d));
std::push_heap(container_.begin(), container_.end());
}
Data Pop() {
std::pop_heap(container_.begin(), container_.end());
Data d = std::move(container_.back());
container_.pop_back();
return std::move(d);
}
size_t size() const { return container_.size(); }
bool empty() const { return size() == 0; }
private:
std::vector<Data> container_;
};
int main() {
MinHeap h;
h.Push(Data(5));
h.Push(Data(8));
h.Push(Data(11));
h.Push(Data(3));
h.Push(Data(7));
while (!h.empty()) {
Data d = std::move(h.Pop());
std::cout << d.value << std::endl;
}
return 0;
}
Any idea what I am doing wrong, and how I can get the heap working with move semantics ?
Errors
In file included from /usr/include/c++/4.9.2/bits/stl_pair.h:59:0,
from /usr/include/c++/4.9.2/bits/stl_algobase.h:64,
from /usr/include/c++/4.9.2/bits/char_traits.h:39,
from /usr/include/c++/4.9.2/ios:40,
from /usr/include/c++/4.9.2/ostream:38,
from /usr/include/c++/4.9.2/iostream:39,
from main.cpp:1:
/usr/include/c++/4.9.2/bits/stl_heap.h: In instantiation of 'void std::push_heap(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__norma
l_iterator<Data*, std::vector<Data> >]':
main.cpp:25:56: required from here
/usr/include/c++/4.9.2/bits/stl_heap.h:164:28: error: no matching function for call to 'Data::Data(std::remove_reference<Data&>::type
)'
_ValueType __value = _GLIBCXX_MOVE(*(__last - 1));
^
In file included from /usr/include/c++/4.9.2/bits/stl_algo.h:61:0,
from /usr/include/c++/4.9.2/algorithm:62,
from main.cpp:3:
/usr/include/c++/4.9.2/bits/stl_heap.h:167:45: error: no matching function for call to 'Data::Data(std::remove_reference<Data&>::type
)'
__gnu_cxx::__ops::__iter_less_val());
^
/usr/include/c++/4.9.2/bits/stl_heap.h:124:5: error: initializing argument 4 of 'void std::__push_heap(_RandomAccessIterator, _Dist
ance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Data*, std::vector<Data> >; _Distance = lo
ng int; _Tp = Data; _Compare = __gnu_cxx::__ops::_Iter_less_val]'
__push_heap(_RandomAccessIterator __first,
^
In file included from /usr/include/c++/4.9.2/bits/stl_pair.h:59:0,
from /usr/include/c++/4.9.2/bits/stl_algobase.h:64,
from /usr/include/c++/4.9.2/bits/char_traits.h:39,
from /usr/include/c++/4.9.2/ios:40,
from /usr/include/c++/4.9.2/ostream:38,
from /usr/include/c++/4.9.2/iostream:39,
from main.cpp:1:
/usr/include/c++/4.9.2/bits/stl_heap.h: In instantiation of 'void std::__pop_heap(_RandomAccessIterator, _RandomAccessIterator, _Rand
omAccessIterator, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Data*, std::vector<Data> >; _Compare = __gnu_c
xx::__ops::_Iter_less_iter]':
/usr/include/c++/4.9.2/bits/stl_heap.h:280:42: required from 'void std::pop_heap(_RAIter, _RAIter) [with _RAIter = __gnu_cxx::__nor
mal_iterator<Data*, std::vector<Data> >]'
main.cpp:29:55: required from here
/usr/include/c++/4.9.2/bits/stl_heap.h:243:28: error: no matching function for call to 'Data::Data(std::remove_reference<Data&>::type
)'
_ValueType __value = _GLIBCXX_MOVE(*__result);
^
In file included from /usr/include/c++/4.9.2/bits/stl_algo.h:61:0,
from /usr/include/c++/4.9.2/algorithm:62,
from main.cpp:3:
/usr/include/c++/4.9.2/bits/stl_heap.h:247:35: error: no matching function for call to 'Data::Data(std::remove_reference<Data&>::type
)'
_GLIBCXX_MOVE(__value), __comp);
^
/usr/include/c++/4.9.2/bits/stl_heap.h:207:5: error: initializing argument 4 of 'void std::__adjust_heap(_RandomAccessIterator, _Di
stance, _Distance, _Tp, _Compare) [with _RandomAccessIterator = __gnu_cxx::__normal_iterator<Data*, std::vector<Data> >; _Distance =
long int; _Tp = Data; _Compare = __gnu_cxx::__ops::_Iter_less_iter]'
__adjust_heap(_RandomAccessIterator __first, _Distance __holeIndex,
^
Never mark your copy constructor or move constructor as
explicit. It isn't illegal. It is just unusual enough to be confusing. There is no benefit to it, and only downside.The
expliciton your move constructor is the cause of this error.