Hi,
Igor Krasnopeev wrote:
> Dietmar Kuehl wrote:
> >This problem is corrected by the adaptors found in the Boost
> >priority queue library which contains, amoung a bunch of different
> >priority queues, also adaptors for stacks and queues.
>
> Explain me please, why somebody needs access to contents of
> stack or queue. It's more logically to use deque in this case.

The state of a stack and a queue is not completely described by the
access functions available in STL's interface: The state both these
data structures is made up of a sequence of elements. These are, at
least occasionally, very useful. For example, when searching a path
from a source node to a destination node can obtain the path from
a stack used during a depth first search. Extracting all elements from
the stack itself is destructive and does not allow searching for more
pathes.

Although it would be possible to use a 'std::deque' or a 'std::vector'
for this, Depth First Search is defined to use a "stack", not something
else. The "stack" in the standard library is not reasonably applicable
in this context. ... and what is wrong with allowing const_iterator
access to the elements on the stack or in a queue? These things are
clearly part of the logical state of the "priority queue" (both are
priority queue using the insertion time to order the elements). It
is reasonable to expose the logical state of an object!

... and, of course, 'std::deque' fails to provide the correct
interfaces in another respect: It does not have "push()" and "pop()"
members to insert and extract elements. How can I write my generic
graph search algorithm using 'std::deque'? I can do so easily using
'std:queue' and 'std::stack' but unfortunately, these classes don't
give me the necessary access :-(
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]

Dietmar Kuehl wrote:
...
> clearly part of the logical state of the "priority queue" (both are
> priority queue using the insertion time to order the elements). It
> is reasonable to expose the logical state of an object!

Actually, the state is fairly well exposed, but only through a protected
interface, rather than a public one.
std::priority_queue<T,Container,Compare> is defined by the standard as
having protected members named 'c' and 'comp', containing the Container
and Compare objects, respectively. Therefore, you can get access to them
by deriving from priority_queue. Furthermore, the behavior of
std::priority_queue<> is defined entirely in terms of the make_heap,
push_heap and pop_heap functions acting on 'c', using 'comp'. Therefore,
in a class derived from priority_queue, it would be feasible to actually
mess with 'c', as long as you  call make_heap(c.begin(),c.end(),comp)
before the next call to any of the base class member functions.

This is a somewhat debateable issue; in other contexts the standard
lists private members of standard library classes "for exposition only",
which means that an implementation is free to use a different name, or
even a completely different way of achieving the same functionality. It
could be argued that 'c' and 'comp' are provided only in the same sense.
However, there's no such disclaimer covering 'c' and 'comp', and the
fact that they're protected rather than private means that they are
accessible, though not as easily as the public members are.

---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html                ]