Topic: Comments please on this view of STL (containers)
Author: "Bill Wade" <bill.wade@stoner.com>
Date: 1998/12/16 Raw View
Matt Austern wrote in message ...
>I wouldn't bother worrying about how priority_queue fits into
>a classification scheme for containers. It is not a container, and
>neither is stack or queue. A container in the STL framework is ...
I find it convenient to distinguish between the general concept of a
container (23p1 "components that ... organize collections of information")
and the STL classification of Container.
The original poster was proposing an alternate classification scheme. I
admit that I didn't find his scheme too compelling. However there are
undoubtedly valid classification schemes which call a C array a container,
they just aren't the STL classification scheme.
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: James Kuyper <kuyper@wizard.net>
Date: 1998/12/15 Raw View
Tony wrote:
>
> In article <3671C396.71241C89@wizard.net>, kuyper@wizard.net says...
> >
> > Tony wrote:
> > ....
> > > post. PriQueue is impemented (in SGI STL) as a vector though. Is
> > > PriQueue the only offender to the classification scheme?
> >
> > In Standard C++, priority_queue<T> takes an optional Container template
> > parameter, which defaults to vector<T>, but can be any sequence which
> > supports front(), push_back(), and pop_back().
>
> So how would you recommend changing the classification presented to
> accommodate priority queues?
I've no opinions on the classification scheme. I was just responding
about a non-standard (and hopefully obsolescent) feature of that
implementation. I'm not even sure it is non-standard, because it
apparently has a different name. If that name is inside namespace std,
strictly conforming code wouldn't even notice its presence. Do they also
implement priority_queue<>, or only PriQueue? Is it PriQueue or
std::PriQueue?
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Pete Becker <petebecker@acm.org>
Date: 1998/12/15 Raw View
Tony wrote:
> In article <3671B05F.4F70C60D@acm.org>, petebecker@acm.org says...
> >
> > Tony wrote:
> > >
> > > In article <F3GrMK.xD@research.att.com>, bs@research.att.com says...
> > > > It is unwise and confusing to rename standard containers.
> > >
> > > Maybe I found them confusing as they were though.
> > >
> >
> > Ah, so you'd rather confuse the people who have to maintain your code
> > after you leave.
>
> No, rather make them efficient immediately instead of a longer learning
> curve. And reduce the gotcha's. And work at a higher level... etc.
So how does using names that they won't recognize for things that they
should already be familiar with accomplish this?
--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Matt Austern <austern@sgi.com>
Date: 1998/12/15 Raw View
James Kuyper <kuyper@wizard.net> writes:
> > > > post. PriQueue is impemented (in SGI STL) as a vector though. Is
> > > > PriQueue the only offender to the classification scheme?
> > >
> > > In Standard C++, priority_queue<T> takes an optional Container template
> > > parameter, which defaults to vector<T>, but can be any sequence which
> > > supports front(), push_back(), and pop_back().
> >
> > So how would you recommend changing the classification presented to
> > accommodate priority queues?
>
> I've no opinions on the classification scheme. I was just responding
> about a non-standard (and hopefully obsolescent) feature of that
> implementation. I'm not even sure it is non-standard, because it
> apparently has a different name. If that name is inside namespace std,
> strictly conforming code wouldn't even notice its presence. Do they also
> implement priority_queue<>, or only PriQueue? Is it PriQueue or
> std::PriQueue?
First of all, SGI's STL implementation has no class named PriQueue,
and never has had a class with that name. I imagine that the original
poster was just using it as an abbreviation for priority_queue.
Second, I wouldn't bother worrying about how priority_queue fits into
a classification scheme for containers. It is not a container, and
neither is stack or queue. A container in the STL framework is
something that supports a well-defined set of operations, including
access to and interation through the contained elements; stack, queue,
and priority_queue do not support those operations.
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Andrei Alexandrescu" <alexandrescua@micromodeling.com>
Date: 1998/12/11 Raw View
David Abrahams wrote in message <3670591b.890968215@news.motu.com>...
>The user can specialize container_traits<> for their collection.
>Consider it a requirement of containers for use in your framework.
Acceptable, but if one can come with something better...
I guess there is a way.
Andrei
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Tony@ask.me (Tony)
Date: 1998/12/11 Raw View
In article <F3GrMK.xD@research.att.com>, bs@research.att.com says...
> It is unwise and confusing to rename standard containers. Even if you did
> nothing else you'd have something nonstandard.
Obviously though I don't necessarily think the existing names are
optimal. I'll buy the previous poster's comments with "Associative"
instead of "Unsequenced" though. I was trying to come up with a
hierarchy based upon common thought processes when selecting the
appropriate container to use rather than the "Comp Sci-like" names.
Also, I find that wrapping STL containers and iterators (especially) into
higher level abstractions makes programming much easier than using STL
directly with all it's gotchas (for instance, when and in what containers
are iterators invalidated when deleting objects?).
> The question is "why?" What is the purpose of this classification/hierarchy?
> What exactly does the lines mean?
Just an organization in kind of a decision-tree. It was just a quickie
mnemonic (not that I didn't ponder an actually class hierarchy, perhaps
of interfaces).
> The standard containers were not designed to fit into such a hierarchy and
> doesn't seem to fit.
So I'm pushing the envelope you mean? ;)
> The hierarchial ordering here isn't inheritance.
No, but perhaps could be.
> For example, a stack isn't a deque - because they support different
> operations and their implementations usually differ.
Yep. The excercise was an attempt to thrash out the similar interfaces.
Again, I just threw the ponderings in a post here to do a little more
thinking aloud with the group on it very open-endedly.
> STL maps and multimaps are ordered.
Yep. The "some renamed" in the title applies to my "hierarchy". STL Map
= My OrdMap whereas my Map = STL Hashed Map. (FastMap comes to mind as a
good alternative name for the STL hashed map and perhaps my Map. My
reasoning was that performance and non-ordered would be the most used so
the hashed version would get the most basic name of "Map". Again, it
could just as easily be FastMap which has more resemblance to the
naming convention of OrdMap). Again, I was aiming toward an approach
facilitating _usage_ rather than Comp Sci.
> You may or may not have a reasonable design here, but it is not the STL.
STL Wrappers(tm)? :)
Tony
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Tony@ask.me (Tony)
Date: 1998/12/11 Raw View
In article <F3GrMK.xD@research.att.com>, bs@research.att.com says...
> It is unwise and confusing to rename standard containers.
Maybe I found them confusing as they were though.
Tony
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Tony@ask.me (Tony)
Date: 1998/12/11 Raw View
In article <3.0.5.32.19981209191320.009552c0@central.beasys.com>,
dtribble@technologist.com says...
> > The question is "why?" What is the purpose of this
> > classification/hierarchy? What exactly does the lines mean?
>
> Perhaps he's attempting to organize a complex collection of types
> into a visual taxonomy for, say, learning it, or perhaps teaching it
> to beginners? (The lines mean "is related to", obviously.) Beyond
> a handful of types, it becomes hard to remember all of them; a
> diagram helps in this regard.
"Let's see.. what kind of container do I need (from my organized
toolbox)...". Among other things. Viewing all the containers in a
"flattened" (one level, ungrouped) way would be like not being able to
recognize socket-wrenches from open-end wrenches. My automotive toolbox
has drawers in it and the tools are distinct. (All kinds of potential
analogies apply).
Now that's just my preference--others make like all of their socket-
wrenches and combination-wrenches and hammers and pliers... all mixed
together in one big box. Still others may like to use a hammer for
everything and have no need for other tools or a toolbox! :)
Tony
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Tony@ask.me (Tony)
Date: 1998/12/11 Raw View
In article <74h6dj$p0v$1@uuneo.neosoft.com>, bill.wade@stoner.com says...
>
> Containers may be classified by several more or less orthogonal
> characteristics, such as the type and behavior (and performance) of
> iterators and algorithms. In general I don't believe there is any
> particular reason to consider Map vs. Set to be a "higher" concept than
> "Ordered vs. Unordered".
Yep. But if you promote the ordering names to where Sets and Maps now
are, you end up with a less elegant (IMO) hierarchy that mixes sets and
maps at the lowest level. Also, I think that thinking "keyed" vs. "non-
keyed" is somehow a more dominant first thought than thinking about the
ordering (YMMV). I believe the way the tree ends up with all the Sets
together and all the Maps together somehow naturally seems to "verify"
the "correctness".
> Based on your definition of "sequenced vs. unsequenced" I believe a priority
> queue qualifies as an unsequenced container. The "location" of an element
> in a priority queue depends much more on the value of the element than on
> insertion order.
Agreed. And that's the kind of discussion I hoped to generate with the
post. PriQueue is impemented (in SGI STL) as a vector though. Is
PriQueue the only offender to the classification scheme?
I really like the "Unsequenced" hierarchy, as it seems to "work". Again
though, I didn't call it "Associative" because I have a hard time viewing
Sets as being associative (like the keyed maps are). Any thoughts or way
of thinking about that?
Tony
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Pete Becker <petebecker@acm.org>
Date: 1998/12/12 Raw View
Tony wrote:
>
> In article <F3GrMK.xD@research.att.com>, bs@research.att.com says...
> > It is unwise and confusing to rename standard containers.
>
> Maybe I found them confusing as they were though.
>
Ah, so you'd rather confuse the people who have to maintain your code
after you leave.
--
Pete Becker
Dinkumware, Ltd.
http://www.dinkumware.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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: James Kuyper <kuyper@wizard.net>
Date: 1998/12/12 Raw View
Tony wrote:
....
> post. PriQueue is impemented (in SGI STL) as a vector though. Is
> PriQueue the only offender to the classification scheme?
In Standard C++, priority_queue<T> takes an optional Container template
parameter, which defaults to vector<T>, but can be any sequence which
supports front(), push_back(), and pop_back().
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Tony@ask.me (Tony)
Date: 1998/12/14 Raw View
In article <3671B05F.4F70C60D@acm.org>, petebecker@acm.org says...
>
> Tony wrote:
> >
> > In article <F3GrMK.xD@research.att.com>, bs@research.att.com says...
> > > It is unwise and confusing to rename standard containers.
> >
> > Maybe I found them confusing as they were though.
> >
>
> Ah, so you'd rather confuse the people who have to maintain your code
> after you leave.
No, rather make them efficient immediately instead of a longer learning
curve. And reduce the gotcha's. And work at a higher level... etc.
Tony
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Tony@ask.me (Tony)
Date: 1998/12/14 Raw View
In article <3671C396.71241C89@wizard.net>, kuyper@wizard.net says...
>
> Tony wrote:
> ....
> > post. PriQueue is impemented (in SGI STL) as a vector though. Is
> > PriQueue the only offender to the classification scheme?
>
> In Standard C++, priority_queue<T> takes an optional Container template
> parameter, which defaults to vector<T>, but can be any sequence which
> supports front(), push_back(), and pop_back().
So how would you recommend changing the classification presented to
accommodate priority queues?
Tony
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: AllanW@my-dejanews.com
Date: 1998/12/10 Raw View
In article <366d5c32.0@10.1.1.65>,
"Andrei Alexandrescu" <alexandrescua@micromodeling.com> wrote:
> Inside a template of which a parameter is a container, I want to figure out
> whether the container is a sequence one or a associative one. If it's
> sequence, I may want to call Container.find(obj), else I want to call
> std::find(Container.begin(), Container.end(), obj).
The definition of std::find<> should specialize the sequences. Then
std::find<sequence> will be defined in terms of std::sequence::find,
making the two forms equivalent for sequences. So you can always use
the latter form.
--
AllanW@my-dejanews.com is a "Spam Magnet" -- never read.
Please reply in USENET only, sorry.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Andrei Alexandrescu" <alexandrescua@micromodeling.com>
Date: 1998/12/10 Raw View
AllanW@my-dejanews.com wrote in message <74p4kg$pnp$1@nnrp1.dejanews.com>...
>
>In article <366d5c32.0@10.1.1.65>,
> "Andrei Alexandrescu" <alexandrescua@micromodeling.com> wrote:
>> Inside a template of which a parameter is a container, I want to figure
out
>> whether the container is a sequence one or a associative one. If it's
>> sequence, I may want to call Container.find(obj), else I want to call
>> std::find(Container.begin(), Container.end(), obj).
>
>The definition of std::find<> should specialize the sequences. Then
>std::find<sequence> will be defined in terms of std::sequence::find,
>making the two forms equivalent for sequences. So you can always use
>the latter form.
??? The find() algorithm doesn't know anything about the container - only
the iterators. Try to write a specialized version of find() for set and
you'll see.
Andrei
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: abrahams@spam.motu.com (David Abrahams)
Date: 1998/12/10 Raw View
On 10 Dec 1998 17:33:24 GMT, "Andrei Alexandrescu"
<alexandrescua@micromodeling.com> wrote:
>Thank you very much.
>Yes, I have thought of that and it's a good idea. I wanted the solution to
>be open-ended, though - it should work with any container that the user
>defines.
The user can specialize container_traits<> for their collection.
Consider it a requirement of containers for use in your framework.
>I wanted to be able to ask a collection: "Can you do find by yourself?" If
>not, I do it linearly. If yes, I pass it this job. For instance, on vector,
>deque, list -> linear, on set, hash_set -> fast.
I don't see the problem. You ask the container by checking its
container_traits. If you like, you can add a convenient base class
"associative_container" to your framework for which container_traits
is also specialized, and let users derive their associative containers
from this base class. Then they won't need another specialization of
container_traits.
>hash_set illustrates one aspect of the problem: I have to define
>container_traits< hash_set >. But what if one doesn't uses an implementation
>with hash_set?
That's what compiler switches are for
#ifdef IMPLEMENTATION_SUPPORTS_HASH_SET
template<>
class container_traits<hash_set> {...
#endif
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: David R Tribble <dtribble@technologist.com>
Date: 1998/12/10 Raw View
Reference: <F3GrMK.xD@research.att.com>
Tony@ask.me (Tony) writes:
> STL Containers (some renamed)
[diagram snipped]
Bjarne Stroustrup wrote:
> The STL containers can be grouped into 2 sub-hierarchies according to
> the way objects are stored upon input: either in an order that is
> container-dependent or in a sequence that is related to the insertion
> order.
...
> The question is "why?" What is the purpose of this
> classification/hierarchy? What exactly does the lines mean?
Perhaps he's attempting to organize a complex collection of types
into a visual taxonomy for, say, learning it, or perhaps teaching it
to beginners? (The lines mean "is related to", obviously.) Beyond
a handful of types, it becomes hard to remember all of them; a
diagram helps in this regard.
As I recall, you organized the standard exceptions into a similar
diagram in chap.14 of C++PL:3. Perhaps chap.17 could have used an
organizational chart like Tony suggested?
-- David R. Tribble, dtribble@technologist.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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Andrei Alexandrescu" <alexandrescua@micromodeling.com>
Date: 1998/12/10 Raw View
David Abrahams wrote in message <366dcab3.723414837@news.motu.com>...
>On 8 Dec 1998 17:10:51 GMT, "Andrei Alexandrescu"
><alexandrescua@micromodeling.com> wrote:
>
>>While indeed the taxonomy doesn't excel in clarity, I did feel a
compelling
>>need related to part of what the poster presented. Maybe someone could
help.
>>
>>Inside a template of which a parameter is a container, I want to figure
out
>>whether the container is a sequence one or a associative one. If it's
>>sequence, I may want to call Container.find(obj), else I want to call
>>std::find(Container.begin(), Container.end(), obj).
>
>I suggest you take a look at std::iterator_traits<>, and define a
>similar my_namespace::container_traits<>. You can then do partial
>specialization for each of the standard containers (see
>std::iterator_traits<T*> for an example).
Thank you very much.
Yes, I have thought of that and it's a good idea. I wanted the solution to
be open-ended, though - it should work with any container that the user
defines.
I wanted to be able to ask a collection: "Can you do find by yourself?" If
not, I do it linearly. If yes, I pass it this job. For instance, on vector,
deque, list -> linear, on set, hash_set -> fast.
hash_set illustrates one aspect of the problem: I have to define
container_traits< hash_set >. But what if one doesn't uses an implementation
with hash_set?
Andrei
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Andrei Alexandrescu" <alexandrescua@micromodeling.com>
Date: 1998/12/08 Raw View
Bjarne Stroustrup wrote in message ...
>The question is "why?" What is the purpose of this
classification/hierarchy?
>What exactly does the lines mean?
While indeed the taxonomy doesn't excel in clarity, I did feel a compelling
need related to part of what the poster presented. Maybe someone could help.
Inside a template of which a parameter is a container, I want to figure out
whether the container is a sequence one or a associative one. If it's
sequence, I may want to call Container.find(obj), else I want to call
std::find(Container.begin(), Container.end(), obj).
Is there any compile-time way to do this? If all sequence containers would
derive from an empty class called "sequence" and all associative containers
would derive from an empty class called "associative", I would be able to do
it. Otherwise I didn't find any means to achieve this.
Andrei
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Bill Wade" <bill.wade@stoner.com>
Date: 1998/12/08 Raw View
Andrei Alexandrescu wrote in message <366d5c32.0@10.1.1.65>...
>Inside a template of which a parameter is a container, I want to figure out
>whether the container is a sequence one or a associative one. If it's
>sequence, I may want to call Container.find(obj), else I want to call
>std::find(Container.begin(), Container.end(), obj).
This is a little fuzzy. For maps, container.find(obj) does not mean the
same thing as std::find(container.begin(), container.end(), obj). In one
case 'obj' is the key, in the other it is the key/value pair.
I suppose you could make your own container_traits<> class with a find_type
member. Specialize the class so that you get one find_type for the various
sets and another find_type for the various sequences.
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: abrahams@spam.motu.com (David Abrahams)
Date: 1998/12/09 Raw View
On 8 Dec 1998 17:10:51 GMT, "Andrei Alexandrescu"
<alexandrescua@micromodeling.com> wrote:
>While indeed the taxonomy doesn't excel in clarity, I did feel a compelling
>need related to part of what the poster presented. Maybe someone could help.
>
>Inside a template of which a parameter is a container, I want to figure out
>whether the container is a sequence one or a associative one. If it's
>sequence, I may want to call Container.find(obj), else I want to call
>std::find(Container.begin(), Container.end(), obj).
>
>Is there any compile-time way to do this? If all sequence containers would
>derive from an empty class called "sequence" and all associative containers
>would derive from an empty class called "associative", I would be able to do
>it. Otherwise I didn't find any means to achieve this.
I suggest you take a look at std::iterator_traits<>, and define a
similar my_namespace::container_traits<>. You can then do partial
specialization for each of the standard containers (see
std::iterator_traits<T*> for an example). Finally, you can do
dispatching to the appropriate find function (see std::distance() for
an example of this).
Good luck!
Dave
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: "Bill Wade" <bill.wade@stoner.com>
Date: 1998/12/07 Raw View
Containers may be classified by several more or less orthogonal
characteristics, such as the type and behavior (and performance) of
iterators and algorithms. In general I don't believe there is any
particular reason to consider Map vs. Set to be a "higher" concept than
"Ordered vs. Unordered". Of course if you are trying to teach STL to
someone, you may find it convenient to present one concept before the other.
Based on your definition of "sequenced vs. unsequenced" I believe a priority
queue qualifies as an unsequenced container. The "location" of an element
in a priority queue depends much more on the value of the element than on
insertion order.
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Tony@ask.me (Tony)
Date: 1998/12/04 Raw View
/* --------------------------------------------------------------------
STL Containers (some renamed)
Unsequenced
________________|__________________
| |
Sets Maps
_________|_______ _________|________
| | | |
Ordered Unordered Ordered Unordered
_____|_____ ____|___ _____|____ ____|____
| | | | | | | |
OrdSet OrdMultiSet Set MultiSet OrdMap OrdMultiMap Map MultiMap
Sequenced
_____________|_____________
| |
Arrays Lists
______|______ ____|___
| | | |
Vector Deque SList DList
| ___|___
| | |
PriQueue Queue Stack
The STL containers can be grouped into 2 sub-hierarchies according to the
way objects are stored upon input: either in an order that is container-
dependent or in a sequence that is related to the insertion order.
Therefor we have "Unsequenced" and "Sequenced" containers as the first
level of decision making when we are choosing an appropriate container.
(It would appear that getting a container that is sequenced and allows
keyed access is not possible unless composition is used to create a new
container composed of a List and a Map e.g.).
Sequenced Container Notes
1. Sets hold objects that act as their own keys (I don't like this
definition).
2. Maps _associate_ a val with key (why sets would also be considered
associative containers escapes me).
3. Unordered Maps and Sets are hashed containers in many implementations.
Unsequenced Container Notes
1. Arrays are Random Access containers.
2. Lists are Sequential Access containers.
---------------------------------------------------------------------- */
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: Joachim Achtzehnter <joachim@kraut.bc.ca>
Date: 1998/12/04 Raw View
Tony@ask.me (Tony) writes:
>
> The STL containers can be grouped into 2 sub-hierarchies according
> to the way objects are stored upon input: either in an order that is
> container- dependent or in a sequence that is related to the
> insertion order.
In general, this distinction is certainly a criteria one can choose to
group container types. But as far as the STL is concerned it makes
more sense, IMHO, to use different terms, namely "associative
containers" versus "sequences". The significant property of sets and
maps in the STL is not that they are stored in a "container-dependent"
way. This is more an implementation issue and one can argue that lists
and vectors also store their elements in a "container-dependent" way.
> 2. Maps _associate_ a val with key (why sets would also be considered
> associative containers escapes me).
The term "associative container" expresses the fact that retrieval is
done based on an element's internal properties. For sequences,
retrieval is by index (or position in a list) which is external to the
element. For maps and sets retrieval is via element properties, in
case of sets the element's value itself is used for finding it in the
set, for maps a key is used.
Joachim
--
joachim@kraut.bc.ca (http://www.kraut.bc.ca)
joachim@mercury.bc.ca (http://www.mercury.bc.ca)
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]
Author: bs@research.att.com (Bjarne Stroustrup)
Date: 1998/12/04 Raw View
Tony@ask.me (Tony) writes:
>
>
>/* --------------------------------------------------------------------
> STL Containers (some renamed)
It is unwise and confusing to rename standard containers. Even if you did
nothing else you'd have something nonstandard.
> Unsequenced
> ________________|__________________
> | |
> Sets Maps
> _________|_______ _________|________
> | | | |
> Ordered Unordered Ordered Unordered
> _____|_____ ____|___ _____|____ ____|____
> | | | | | | | |
> OrdSet OrdMultiSet Set MultiSet OrdMap OrdMultiMap Map MultiMap
>
>
> Sequenced
> _____________|_____________
> | |
> Arrays Lists
> ______|______ ____|___
> | | | |
> Vector Deque SList DList
> | ___|___
> | | |
> PriQueue Queue Stack
>
>
> The STL containers can be grouped into 2 sub-hierarchies according to the
> way objects are stored upon input: either in an order that is container-
> dependent or in a sequence that is related to the insertion order.
> Therefor we have "Unsequenced" and "Sequenced" containers as the first
> level of decision making when we are choosing an appropriate container.
> (It would appear that getting a container that is sequenced and allows
> keyed access is not possible unless composition is used to create a new
> container composed of a List and a Map e.g.).
The question is "why?" What is the purpose of this classification/hierarchy?
What exactly does the lines mean?
The standard containers were not designed to fit into such a hierarchy and
doesn't seem to fit. The hierarchial ordering here isn't inheritance.
For example, a stack isn't a deque - because they support different
operations and their implementations usually differ.
STL maps and multimaps are ordered.
You may or may not have a reasonable design here, but it is not the STL.
> Sequenced Container Notes
>
> 1. Sets hold objects that act as their own keys (I don't like this
> definition).
> 2. Maps _associate_ a val with key (why sets would also be considered
> associative containers escapes me).
> 3. Unordered Maps and Sets are hashed containers in many implementations.
>
> Unsequenced Container Notes
>
> 1. Arrays are Random Access containers.
> 2. Lists are Sequential Access containers.
> ---------------------------------------------------------------------- */
- Bjarne
Bjarne Stroustrup - http://www.research.att.com/~bs
[ 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://reality.sgi.com/austern_mti/std-c++/faq.html ]