I'm writing a Priority Queue, here is my code
#include <iostream>
#include<vector>
#include <functional>
template <class T>
class MaxPQ
{
public:
MaxPQ(size_t size): container(size)
{
}
MaxPQ(std::vector<T>& Raw)
{
//hard-code set it inside of class
//this->setWrapper([=](size_t x, size_t y) -> bool { return this->container[x] < this->container[y]; });
container.clear();
for (const auto& val : Raw)
{
this->insert(val);
}
}
MaxPQ(): container(0)
{
}
~MaxPQ()
{
container.clear();
}
void setWrapper(std::function<bool(size_t, size_t)> input)
{
compare_wrapper = input;
}
void insert(T newEle)
{
container.push_back(newEle);
swim(container.size() - 1);
}
T delMax()
{
T result = max();
swapByIndex(0, container.size() - 1);
container.erase(container.end());
sink(0);
return result;
}
inline T max()
{
return container[0];
}
void swapByIndex(size_t Left, size_t Right)
{
using std::swap;
swap(container[Left], container[Right]);
}
inline size_t left(size_t parent)
{
return parent * 2 + 1;
}
inline size_t right(size_t parent)
{
return parent * 2 + 2;
}
inline size_t parent(size_t child)
{
return (child - 1) >= 0 ? (child - 1) / 2 : -1;
}
void print()
{
using std::cout;
for (const auto& val : container)
cout << val << " ";
cout << std::endl;
}
private:
std::vector<T> container;
std::function<bool(size_t, size_t)> compare_wrapper;
void swim(size_t targetIndex)
{
while (targetIndex > 0 && compare_wrapper(parent(targetIndex), targetIndex))
{
swapByIndex(parent(targetIndex), targetIndex);
targetIndex = parent(targetIndex);
}
}
void sink(size_t targetIndex)
{
while (left(targetIndex) < container.size())
{
size_t maxIndex = left(targetIndex);
if (right(targetIndex) < container.size() && compare_wrapper(maxIndex, right(targetIndex)))
{
maxIndex = right(targetIndex);
}
if (compare_wrapper(maxIndex, targetIndex))
{
break;
}
swapByIndex(targetIndex, maxIndex);
targetIndex = maxIndex;
}
}
};
int main()
{
std::vector<int> temp{1, 8, 0, 9, 12, 4};
auto myPQ = new MaxPQ<int>(temp);
myPQ->setWrapper([=](size_t x, size_t y) -> bool
{
//error here, trying to access private member `container`
return myPQ->container[x] < myPQ->container[y];
}); //set it out of class
myPQ->print();
}
all code works pretty fine when I hard-code compare
to bool less(int,int)()
bool less(int,int)()
is a private (because there is no need to let other call it) member function which will access private member container
but others may want to custom the function I guess it looks like a function come from outside, but can act like a member function (which could access private member)
so How could I do so(to set such wrapper function by using lambda function or std::function), where should I write the setWrapper funtion, and where should I call it
is this a good design?
how does std::for_each set its function wrapper?
I'm new to STL, I may have some term or concept wrong, and English is not my first language, please forgive me.
thanks in advance
Aucun commentaire:
Enregistrer un commentaire