remove last added element from priority_queue

I assume you mean you want to remove the element with
the lowest priority. Maybe I am wrong, but I don't see
anyway of doing this easily. The only thing I can think
of is :

1) create a new priority_queue of the same type

2) loop thru the original priority_queue

* retrieve element via top()
* pop()
* if (not empty)
add element retrieved via the top() to the new priority_queue
else
break out of loop

3) basically the same loop, but add all the elements in
the new container to the old one.

Maybe a better way would be to create your own class with
a deque as the internal container. If you have the Josuttis
book, I think the code in the "Class priority_queue<> in Detail"
could be used as is, just adding a function to remove the
first element.

First thanks for the responses.

I don't want to remove the member with the lowest priority, I
want to remove the member I just added regardless of its
priority. I am trying to implement some exception safety
for another wrapper

void InsertElementSetEvent(const T& element)
{
LOCKING_POINTER<WRAP_CONTAINER<T, C>, SYNC_CRITICAL_SECTION> locked_buffer(Buffer_, BufferCS_);
locked_buffer->AddElement(element);
SCOPE_GUARD guard = MakeGuard(REMOVE_ELEMENT_ON_FAILURE_HELPER<T, C>(&locked_buffer));
BufferEvent_.Set(); //throws
guard.Dismiss();
}

template<typename T, typename C>
class REMOVE_ELEMENT_ON_FAILURE_HELPER
{
private:
LOCKING_POINTER<WRAP_CONTAINER<T, C>, SYNC_CRITICAL_SECTION>* LockedObj_;
public:
REMOVE_ELEMENT_ON_FAILURE_HELPER(LOCKING_POINTER<WRAP_CONTAINER<T, C>, SYNC_CRITICAL_SECTION>* locked_obj):LockedObj_(locked_obj){}
void operator()()
{
(*LockedObj_)->RemoveLastAddedElement();
}
};

Here I am just using ScopeGuard to execute a functor (I used
a functor here because that is the way I found to get the thing
to compile in VC++)

The details of this wrapper I posted in another thread, although
I have changed it somewhat, based on all the feedback I got there:)

I will just write my own priority queue

Well I gave it a shot with heaps, tell me what you think

template<typename Tp>
class in_order_compare
{
public:
bool operator()(const pair<unsigned long, Tp>& rhs, const pair<unsigned long, Tp>& lhs) const
{
return rhs.first < lhs.first;
}

};

template<typename _Tp, typename _Compare>
class wrap_compare
{
private:
_Compare Comp_;
public:
wrap_compare(_Compare _x):Comp_(_x){}
bool operator()(const pair<unsigned long, _Tp>& rhs, const pair<unsigned long, _Tp>& lhs) const
{
return Comp_(rhs.second, lhs.second);
}
};

template <typename _Tp, typename _Compare>
class my_priority_queue {
protected:
vector<pair<unsigned long, _Tp> > c;
_Compare comp;
unsigned long InOrder_;
public:
my_priority_queue():c(), InOrder_(0){}
bool empty() const { return c.empty(); }
vector<pair<unsigned long, _Tp> >::size_type size() const { return c.size(); }
const _Tp& top() const { return c.front().second; }
void push(const _Tp& __x)
{
c.push_back(make_pair(InOrder_++,__x));
push_heap(c.begin(), c.end(), wrap_compare<_Tp, _Compare>(comp));
}
void pop()
{
pop_heap(c.begin(), c.end(), wrap_compare<_Tp, _Compare>(comp));
c.pop_back();
if(c.empty())
InOrder_ = 0;
}
void pop_last_queued()
{
make_heap(c.begin(), c.end(), in_order_compare<_Tp>());
pop_heap(c.begin(), c.end(), in_order_compare<_Tp>());
c.pop_back();
make_heap(c.begin(), c.end(), wrap_compare<_Tp, _Compare>(comp));
if(c.empty())
InOrder_ = 0;
}
};

Actually I am a little disturbed at this check for empty on each pop
[Yves: Someday I'll stone you to death for using the PHP tags which make code really long and hard to read]

But yves, I love the pretty colors...

1. The problem you mentioned about overflowing int does
reallly bug me, while I am 99% percent sure that it will not be
a problem, it just is ugly to have the possibility.
Do you have any suggestions?

2. Yah, I pulled the code for the priority_queue out of STLPort
and modified

3. I agree I will make the first template function more generic

4. I was aware of the problem with accessing an empty container
but I will check that in a higher level wrapper. This gives me the
option to not check.

Thanks for all the imput Yves :thumb:

Of course. Thanks Yves.

Good Idea, I was using a constant member to compare InOrder_ to

here is the next attempt

using namespace std;
#include <vector>
#include <algorithm>
#include <limits>
#include <stdexcept>

template<typename K, typename T, typename Compare = less<K> >
class pair_less_on_first
{
private:
Compare Comp_;
public:
pair_less_on_first(Compare comp = less<K>()):Comp_(comp){}
bool operator()(const pair<K, T>& rhs, const pair<K, T>& lhs) const
{
return Comp_(rhs.first, lhs.first);
}

};

template<typename K, typename T, typename Compare = less<T> >
class pair_less_on_second
{
private:
Compare Comp_;
public:
pair_less_on_second(Compare comp = less<T>()):Comp_(comp){}
bool operator()(const pair<K, T>& rhs, const pair<K, T>& lhs) const
{
return Comp_(rhs.second, lhs.second);
}
};

template <typename T, typename CompareT = less<T> >
class my_priority_queue {
protected:
vector<pair<unsigned long, T> > C_;
CompareT CompT_;
unsigned long InOrder_;
void RebaseInOrder()
{
make_heap(C_.begin(), C_.end(), pair_less_on_first<unsigned long, T>());
sort_heap(C_.begin(), C_.end(), pair_less_on_first<unsigned long, T>());
for(vector<pair<unsigned long, T> >::size_type i = 0; i < C_.size(); i++)
C_[i].first = i;
InOrder_ = C_.size() + 1;
make_heap(C_.begin(), C_.end(), pair_less_on_second<unsigned long, T, CompareT>(CompT_));
}
public:
my_priority_queue():C_(), InOrder_(0){}
bool empty() const { return C_.empty(); }
vector<pair<unsigned long, T> >::size_type size() const { return C_.size(); }
const T& top() const { return C_.front().second; }
void push(const T& t)
{
if(numeric_limits<unsigned long>::max() == InOrder_)
throw;
C_.push_back(make_pair(InOrder_++, t));
push_heap(C_.begin(), C_.end(), pair_less_on_second<unsigned long, T, CompareT>(CompT_));
if(InOrder_ & 0x40000000)
RebaseInOrder();
}
void pop()
{
pop_heap(C_.begin(), C_.end(), pair_less_on_second<unsigned long, T, CompareT>(CompT_));
C_.pop_back();
}
void pop_last_queued()
{
make_heap(C_.begin(), C_.end(), pair_less_on_first<unsigned long, T>());
pop_heap(C_.begin(), C_.end(), pair_less_on_first<unsigned long, T>());
C_.pop_back();
make_heap(C_.begin(), C_.end(), pair_less_on_second<unsigned long, T, CompareT>(CompT_));
}
};

Originally posted by Yves M

Moreover, the line

if(numeric_limits<unsigned long>::max() == InOrder_)
throw;

Should be superflous. Remember that you are writing a container, so it's up to the container itself to guarantee integrity of its invariants.

Can you explain that a bit more

well I do rebase, but if it happens to be the case that there are
actually 0x40000000 elements or more in the queue, then that number will be exceeded. So that is not an invariant. Actually this is a problem.

Well, that would mean at least one gigabyte of data (assuming each data item has only one byte), but if you want to allow for that, then you'll have to use a bigger datatype for InOrder_ or use 0x80000000 (which works, since you're using unsigned longs) which will allow up to at least 2 Gibaytes. On a IA32 machine you can't get much further than that anyways.

I guess there could be problem with this design is the queue size
actually exceeds 0x40000000, it will be rebasing all the time.

Do you really expect to hold that many items at one single time? Note that a vector will only be able to hold up to 0xFFFFFFFF items on an IA32 machine, but my guess is that you run out of memory way before that.

I am probably just over engineering this:)

Yes it does
Thanks Yves

I have a question about your constructor in your comparison functions. Currently it's:

pair_less_on_first(Compare comp = less<K>()):Comp_(comp){}

Wouldn't it make more sense to make them:

pair_less_on_first(const Compare &comp = Compare()):Comp_(comp){}

Also, instead of having a variable that holds Compare, it may be an idea to hold one that has CompareSecond(CompT_), since that's all you use.