Hello,
I understand that an easy way to make the standard std::priority_q ueue
stable is by including an integer stamp with each node that is
incremented each time a new node is pushed into the queue. However, no
matter what reasonably-sized type I use for the stamp, eventually the
stamp will 'wrap around' and possibly cause incorrect ordering of
elements. For my application, which queues elements very quickly and
runs for an indefinite amount of time, this scenario is a real concern,
and will eventually cause incorrect results.
Is there any easy and painless way of correcting this order-stamp
wraparound problem?
Aaron W. LaFramboise 38 5806
"Aaron W. LaFramboise" <aa********@c ox-internet.com> wrote in message
news:10******** *****@corp.supe rnews.com... Hello,
I understand that an easy way to make the standard std::priority_q ueue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonably-sized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this order-stamp wraparound problem?
Aaron W. LaFramboise
I don't know if this will help you but...
In a server application I helped write, we got the local date/time info and
created a string from that which identified the ordering of the queue. We
set the string to be the following format:
YYYYMMDDHHNNSST TT
where
YYYY=year
MM=month
DD=day
HH=hours
NN=minutes
SS=seconds
TTT=millisecond s
(If you are queuing faster than that will allow for, then you can add an
integer count to the end of that, which can be free to wrap since you're not
likely to exceed THAT limit! :-))
That's worked fine for three years now. Wel, the system's been rebooted
several times in that time (it is Windows, after all :-)), but the queue is
restored on startup, so the ordering is still preserved properly.
-Howard
"Aaron W. LaFramboise" <aa********@c ox-internet.com> wrote in message
news:10******** *****@corp.supe rnews.com... Hello,
I understand that an easy way to make the standard std::priority_q ueue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonably-sized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this order-stamp wraparound problem?
Aaron W. LaFramboise
I don't know if this will help you but...
In a server application I helped write, we got the local date/time info and
created a string from that which identified the ordering of the queue. We
set the string to be the following format:
YYYYMMDDHHNNSST TT
where
YYYY=year
MM=month
DD=day
HH=hours
NN=minutes
SS=seconds
TTT=millisecond s
(If you are queuing faster than that will allow for, then you can add an
integer count to the end of that, which can be free to wrap since you're not
likely to exceed THAT limit! :-))
That's worked fine for three years now. Wel, the system's been rebooted
several times in that time (it is Windows, after all :-)), but the queue is
restored on startup, so the ordering is still preserved properly.
-Howard
"Aaron W. LaFramboise" <aa********@c ox-internet.com> wrote in message I understand that an easy way to make the standard std::priority_q ueue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonably-sized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this order-stamp wraparound problem?
What is a stable priority queue?
"Aaron W. LaFramboise" <aa********@c ox-internet.com> wrote in message I understand that an easy way to make the standard std::priority_q ueue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonably-sized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this order-stamp wraparound problem?
What is a stable priority queue?
Siemel Naran wrote: What is a stable priority queue?
I'm guessing items of the same priority come out in the order they were
inserted.
-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.
Siemel Naran wrote: What is a stable priority queue?
I'm guessing items of the same priority come out in the order they were
inserted.
-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.
On Mon, 05 Apr 2004 14:57:53 -0500, "Aaron W. LaFramboise"
<aa********@c ox-internet.com> wrote in comp.lang.c++: Hello,
I understand that an easy way to make the standard std::priority_q ueue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonably-sized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this order-stamp wraparound problem?
Aaron W. LaFramboise
Define the time stamp as an unsigned long (or unsigned long long, if
your compiler supports this extension from C), and do the increment
like this:
if (timestamp < ULONG_MAX) /* ULLONG_MAX */
++timestamp;
Don't forget to include <limits.h> or <climits>.
If you are really likely to exceed 0xffffffff, the minimum possible
value for ULONG_MAX, and your implementation doesn't support 64 bit
integer types (long long or __int64), you could always use a double or
long double.
--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++ http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
On Mon, 05 Apr 2004 14:57:53 -0500, "Aaron W. LaFramboise"
<aa********@c ox-internet.com> wrote in comp.lang.c++: Hello,
I understand that an easy way to make the standard std::priority_q ueue stable is by including an integer stamp with each node that is incremented each time a new node is pushed into the queue. However, no matter what reasonably-sized type I use for the stamp, eventually the stamp will 'wrap around' and possibly cause incorrect ordering of elements. For my application, which queues elements very quickly and runs for an indefinite amount of time, this scenario is a real concern, and will eventually cause incorrect results.
Is there any easy and painless way of correcting this order-stamp wraparound problem?
Aaron W. LaFramboise
Define the time stamp as an unsigned long (or unsigned long long, if
your compiler supports this extension from C), and do the increment
like this:
if (timestamp < ULONG_MAX) /* ULLONG_MAX */
++timestamp;
Don't forget to include <limits.h> or <climits>.
If you are really likely to exceed 0xffffffff, the minimum possible
value for ULONG_MAX, and your implementation doesn't support 64 bit
integer types (long long or __int64), you could always use a double or
long double.
--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.l earn.c-c++ http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html
"Kevin Goodsell" <us************ *********@never box.com> wrote in message Siemel Naran wrote: What is a stable priority queue?
I'm guessing items of the same priority come out in the order they were inserted.
Then maybe we can use the protected member 'c'. The standard says
template <class T, class Container = std::vector<T>, ...>
class priority_queue {
protected:
Container c;
...
};
So we could derive our own class from priority_queue, and add read and write
functions that read directly into and out of 'c'. If deriving from a
non-polymorphic class bothers us, we can use private inheritance with using
declarations.
We could get stable queue's and stacks too.
Anyway, what is a priority_queue? Is it just like a queue, except that
items with the highest priority get retrieved by top() and pop() first? How
do they achieve O(lg(N)) for both push and pop (ie. how does the heap
work?). This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Aaron W. LaFramboise |
last post by:
Hello,
I understand that an easy way to make the standard std::priority_queue
stable is by including an integer stamp with each node that is
incremented each time a new node is pushed into the queue. However, no
matter what reasonably-sized type I use for the stamp, eventually the
stamp will 'wrap around' and possibly cause incorrect ordering of
elements. For my application, which queues elements very quickly and
runs for an...
|
by: Dan H. |
last post by:
Hello,
I have implemented a C# priority queue using an ArrayList. The objects
being inserted into the priority queue are being sorted by 2 fields, Time
(ulong) and Priority (0-100).
When I enqueue, I do a binary search on where to put the object and then
insert using that index and arraylist.insert(index, obj)
The bottom of my arraylist is always my lowest, therefore, dequeueing is
very fast and effecient.
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers, it seems that the internal comparison operator "<=>" tries to promote arguments from unsigned to signed.
This is as boiled down as I can make it.
Here is my compilation command:
g++-12 -std=c++20 -Wnarrowing bit_field.cpp
Here is the code in...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: tracyyun |
last post by:
Dear forum friends,
With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
|
by: isladogs |
last post by:
The next Access Europe User Group meeting will be on Wednesday 1 May 2024 starting at 18:00 UK time (6PM UTC+1) and finishing by 19:30 (7.30PM).
In this session, we are pleased to welcome a new presenter, Adolph Dupré who will be discussing some powerful techniques for using class modules.
He will explain when you may want to use classes instead of User Defined Types (UDT). For example, to manage the data in unbound forms.
Adolph will...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
|
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |