SR multiple timeout timers

[Swathi Amarala]

In the assignment description, it is given that we must implement multiple
timeout timers for SR using a priority queue.
Instead, can I implement it with a map?

[Martin Karsten]

Post by Swathi Amarala
In the assignment description, it is given that we must implement
multiple timeout timers for SR using a priority queue.
Instead, can I implement it with a map?

Yes, "priority queue" is a general type of data structure with many possible
implementations.

[Swathi Amarala]

Thank you. I have another question.

template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class
priority_queue;

In priority queue , it is said that we can only use a vector or a deque for
a "Container". In this case I cannot use a priority queue to store elements
with a key and a value (such as map and multimap) right.

Post by Martin Karsten

Post by Swathi Amarala
In the assignment description, it is given that we must implement
multiple timeout timers for SR using a priority queue.
Instead, can I implement it with a map?

Yes, "priority queue" is a general type of data structure with many possible
implementations.

[Martin Karsten]

Sorry, I meant "priority queue" in the general sense. Not necessarily the STL
container that's called 'priority_queue'.

See e.g.
http://www.itl.nist.gov/div897/sqg/dads/HTML/priorityque.html

for a general description.

Post by Swathi Amarala
Thank you. I have another question.
template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class
priority_queue;
In priority queue , it is said that we can only use a vector or a deque
for a "Container". In this case I cannot use a priority queue to store
elements with a key and a value (such as map and multimap) right.

Post by Martin Karsten

Post by Swathi Amarala
In the assignment description, it is given that we must implement
multiple timeout timers for SR using a priority queue.
Instead, can I implement it with a map?

Yes, "priority queue" is a general type of data structure with many possible
implementations.

[Tom Gault]

If I might be picky for a moment, from my understanding, map is technically
a dictionary, not a priority queue. Dictionaries are optimized for random
access whereas priority queues are optimized to retrieve either the maximum
or minimum value of the set. While dictionaries may use the notion of order
to optimize lookups, the user of a dictionary doesn't neccesarily care what
order elements are in.

I haven't gotten to this point in the assignment but my from reading the
assignment I think a prioritiy queue really is needed because we are
interested specifically in the NEXT timer (i.e. min or max value) but we
don't really care about the rest of the timers. I love maps, and maybe
there's a way they can be used in conjunction with the priority queue, but I
don't see yet how it could be used AS the priority queue.

From Tom

Post by Martin Karsten
Sorry, I meant "priority queue" in the general sense. Not necessarily the STL
container that's called 'priority_queue'.
See e.g.
http://www.itl.nist.gov/div897/sqg/dads/HTML/priorityque.html
for a general description.

Post by Swathi Amarala
Thank you. I have another question.
template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class
priority_queue;
In priority queue , it is said that we can only use a vector or a deque
for a "Container". In this case I cannot use a priority queue to store
elements with a key and a value (such as map and multimap) right.

Post by Martin Karsten

Post by Swathi Amarala
In the assignment description, it is given that we must implement
multiple timeout timers for SR using a priority queue.
Instead, can I implement it with a map?

Yes, "priority queue" is a general type of data structure with many possible
implementations.

[Martin Karsten]

True in the most abstract/general case, but the STL implementation (and
definition) of a map (and probably most others) uses ordering to distinguish
keys, so it can be used to implement the priority queue.

Post by Tom Gault
If I might be picky for a moment, from my understanding, map is technically
a dictionary, not a priority queue. Dictionaries are optimized for random
access whereas priority queues are optimized to retrieve either the maximum
or minimum value of the set. While dictionaries may use the notion of order
to optimize lookups, the user of a dictionary doesn't neccesarily care what
order elements are in.
I haven't gotten to this point in the assignment but my from reading the
assignment I think a prioritiy queue really is needed because we are
interested specifically in the NEXT timer (i.e. min or max value) but we
don't really care about the rest of the timers. I love maps, and maybe
there's a way they can be used in conjunction with the priority queue, but I
don't see yet how it could be used AS the priority queue.
From Tom

Post by Martin Karsten
Sorry, I meant "priority queue" in the general sense. Not necessarily the STL
container that's called 'priority_queue'.
See e.g.
http://www.itl.nist.gov/div897/sqg/dads/HTML/priorityque.html
for a general description.

Post by Swathi Amarala
Thank you. I have another question.
template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class
priority_queue;
In priority queue , it is said that we can only use a vector or a deque
for a "Container". In this case I cannot use a priority queue to store
elements with a key and a value (such as map and multimap) right.

Post by Martin Karsten

Post by Swathi Amarala
In the assignment description, it is given that we must implement
multiple timeout timers for SR using a priority queue.
Instead, can I implement it with a map?

Yes, "priority queue" is a general type of data structure with many possible
implementations.

[Tom Gault]

Oh, right. Good point. myMap.begin() will always be the minimum element,
won't it. I'll remember this trick! :)

From Tom

Post by Martin Karsten
True in the most abstract/general case, but the STL implementation (and
definition) of a map (and probably most others) uses ordering to distinguish
keys, so it can be used to implement the priority queue.

Post by Tom Gault
If I might be picky for a moment, from my understanding, map is technically
a dictionary, not a priority queue. Dictionaries are optimized for random
access whereas priority queues are optimized to retrieve either the maximum
or minimum value of the set. While dictionaries may use the notion of order
to optimize lookups, the user of a dictionary doesn't neccesarily care what
order elements are in.
I haven't gotten to this point in the assignment but my from reading the
assignment I think a prioritiy queue really is needed because we are
interested specifically in the NEXT timer (i.e. min or max value) but we
don't really care about the rest of the timers. I love maps, and maybe
there's a way they can be used in conjunction with the priority queue, but I
don't see yet how it could be used AS the priority queue.
From Tom

Post by Martin Karsten
Sorry, I meant "priority queue" in the general sense. Not necessarily
the
STL
container that's called 'priority_queue'.
See e.g.
http://www.itl.nist.gov/div897/sqg/dads/HTML/priorityque.html
for a general description.

Post by Swathi Amarala
Thank you. I have another question.
template < class T, class Container = vector<T>,
class Compare = less<typename Container::value_type> > class
priority_queue;
In priority queue , it is said that we can only use a vector or a deque
for a "Container". In this case I cannot use a priority queue to store
elements with a key and a value (such as map and multimap) right.

Post by Martin Karsten

Post by Swathi Amarala
In the assignment description, it is given that we must implement
multiple timeout timers for SR using a priority queue.
Instead, can I implement it with a map?

Yes, "priority queue" is a general type of data structure with many possible
implementations.