How to make max-heap stable with counter and account for counter overflow?

Generally I need size-efficient data structure similar to std::priority_queue but stable (preserving order of insertion).

By adding just 4 bytes to the object I could have 1 byte serving as priority and 3 bytes as counter to keep the order of insertion. Closest competitor - std::forward_list - would add an overhead of 5 bytes (in practice 8 due to alignment) - one for priority and 4 for link (32-bit architecture). It would also be slower than max-heap due to traversal when adding new element.

The problem with counter is the behavior of container when the counter overflows. In Boost the counter is 64-bits long and when it overflows, the container throws an exception ( http://ift.tt/1xtWYWw ).

One solution to this problem that comes to mind is resetting the counter whenever the queue gets empty, but this is only a partial solution to the problem.

Is there a generic (and optimal - without traversing through the whole heap each time) way this could be solved? I planned to use std::push_heap() and std::pop_heap() from <algorithm> with an array of raw storage, so I have access to "internals" of the entries. If possible, I'd prefer to stick to these standard functions instead of implementing my own heap (or any other data structure) that would be stable.