Below is an implementation of the insert()
member function of a max heap. I tried to use std::forward
as I think it can be alternative to writing an overload of this function that accepts lvalues. However, the code is still not working for lvalues. Any ideas why?
Note: values
is a private vector<T>
in the max_heap
class.
template <typename T, typename compare_type>
void max_heap<T, compare_type>::insert(T&& item){
if(values.empty()){
values.push_back(std::forward<T>(item));
return;
}
values.push_back(std::forward<T>(item));
size_t child_pos = values.size()-1;
size_t parent_pos = (child_pos-1)/2;
//stop swapping either when inserted child at root or smaller than parent
while(child_pos != 0 && pred(values[parent_pos], values[child_pos])){
std::swap(values[parent_pos], values[child_pos]);
child_pos = parent_pos;
parent_pos = (child_pos-1)/2;
}
}
CodePudding user response:
To create a forwarding reference, your argument's type must exist as a template parameter of the same function template. (See (1) of forward references for more information.)
In your case, the template parameter T
is from the class max_heap
and not from the function's template argument list, so item
serves as an rvalue reference (which can't bind to lvalues) and not as a forwarding reference.
For your case, try something like this:
#include <cstddef>
#include <utility>
#include <vector>
// Other header includes go here ...
template <typename T, typename compare_type>
class max_heap {
// Other instance variables go here ...
public:
template <typename U> // <- Notice how the template parameter 'U' is bound to the 'same function template'
void insert(U&& item);
// Other member methods go here ...
};
// ...
template <typename T, typename compare_type>
template <typename U>
void max_heap<T, compare_type>::insert(U&& item){
if(values.empty()){
values.push_back(std::forward<U>(item));
return;
}
values.push_back(std::forward<U>(item));
size_t child_pos = values.size()-1;
size_t parent_pos = (child_pos-1)/2;
//stop swapping either when inserted child at root or smaller than parent
while(child_pos != 0 && pred(values[parent_pos], values[child_pos])){
std::swap(values[parent_pos], values[child_pos]);
child_pos = parent_pos;
parent_pos = (child_pos-1)/2;
}
}
// Other definitions go here ...