petebecker@acm.org (Pete Becker) wrote in message news:<3E14DEEA.A62EA317@acm.org>...
> I'm perfectly willing to assume that you know what you think and have
> reported it correctly. However, that has nothing to do with the
> technical merits of templates with eight parameters.

My original posting actually consisted of two issues:

1. The current proposal isn't useful because it specifies a family of
containers with different performance characteristics. The hash
containers as defined in the proposal will be hard to use portably.
(Existing example: std::list).

2. The solution might be the use of policy parameters.

I didn't follow the development of the discussion (New Year
celebrations, still dizzy...), but having reviewed it now, I see that
the emphasis has been on the second issue. And one of the opinions in
the thread seems to be '8 template parameters are bad, therefore, the
current proposal is fine'.

Regardless of the solution (the second issue), the current proposal is
underspecified. If everyone thinks 5 parameters is the maximum, let
there be 5 of them, but let the implementation strategy be more
specific. This is yet another - simple - solution to the first issue
(which I like less).

OTOH, if you think the first issue isn't valid, I think it makes sense
to first discuss and discard it, and thus avoid discussing the second.

I consider the policy-based solution to be superior, and agree with
what David Held said about it. If it's easy to give users control over
the hash container, it's better than fixing a single strategy and
forcing users to write their own containers that are 80% the same code
as the standard one.

I agree that default values will eliminate the learning overhead for
those who don't care. I think it's possible to pack the policy
parameters into a single parameter to hash, and provide a bunch of
standard types for the user to choose from.

I think even 8 template parameters in this case are more ugly than
technically deficient. Let's update our aesthetic standards :)

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) wrote in message news:<3e15961c.1034343@news.earthlink.net>...
> On Thu, 2 Jan 2003 19:13:29 +0000 (UTC), dheld@codelogicconsulting.com
> ("David B. Held") wrote:
>
> > "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> > news:3e10e9ff.43255703@news.earthlink.net...
> > > On Mon, 30 Dec 2002 20:33:59 +0000 (UTC), dheld@codelogicconsulting.com
> > > ("David B. Held") wrote:
>
> > > > [...]
> > > > Whatever would produce the "basic" hash container with five parameters,
> > > > I would expect.
>
> > > I guess that means accept Matt's proposal.
>
> > How does that follow?
>
> There is a proposal.  You want three additional policy template
> parameters.  You have offered no default options.  Conclusion: you
> accept the proposal's defaults.

The choice of reasonable defaults is not hard. Example: no storing of
hash-codes, bidirectional iterators, manual resizing. A hash-table
with these defaults is portably usable. Matt's proposal leaves these
things unspecified and that's what concerns me.

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Vahan Margaryan" <marg64@yahoo.com> wrote in message
news:44d2ad1a.0301050250.591f3563@posting.google.com...

> I agree that default values will eliminate the learning overhead for
> those who don't care. I think it's possible to pack the policy
> parameters into a single parameter to hash, and provide a bunch of
> standard types for the user to choose from.
>
> I think even 8 template parameters in this case are more ugly than
> technically deficient. Let's update our aesthetic standards :)

Then you might like our current implementation as a starting point.
(See our on-line C++ Library Reference at our web site.) It packs
various types, parameters, and functors into a single traits class.
So hash_map has four template parameters and hash_set has only three.

I have much less trouble extending this traits class to add more
(sensible) policy alternatives, provided the defaults give our
customers the current behavior. Sure beats adding template parameters
*after* the allocator type.

P.J. Plauger
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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Vahan Margaryan" <marg64@yahoo.com> wrote in message
news:44d2ad1a.0301050252.6f6475a0@posting.google.com...

> > There is a proposal.  You want three additional policy template
> > parameters.  You have offered no default options.  Conclusion: you
> > accept the proposal's defaults.
>
> The choice of reasonable defaults is not hard. Example: no storing of
> hash-codes, bidirectional iterators, manual resizing. A hash-table
> with these defaults is portably usable. Matt's proposal leaves these
> things unspecified and that's what concerns me.

Maybe it wasn't a hard choice for you, but I don't agree with the result.
Why require manual resizing? We use incremental hashing, so the default
behavior is sensible growth with no sophisticated intervention required
by the user. In fact, you can use our hash_map<Key, Val> as a drop-in
replacement for map<Key, Val>, in all but the rarest of applications.

P.J. Plauger
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://www.jamesd.demon.co.uk/csc/faq.html                       ]

""P.J. Plauger"" <pjp@dinkumware.com> wrote in message
news:3e1997fd$0$11995$724ebb72@reader2.ash.ops.us.uu.net...
> [...]
> I have much less trouble extending this traits class to add more
> (sensible) policy alternatives, provided the defaults give our
> customers the current behavior. Sure beats adding template
> parameters *after* the allocator type.

For the record, I have no particular love of large numbers of template
parameters.  It seems perfectly reasonable to me to encapsulate
multiple policies into one parameter in various cases.  I suppose
when policy alternatives are not as likely to be used as the defaults,
this is probably the case.

This section from the proposal seems to indicate that a policy choice
(in whatever form) might be most appropriate:

    I don't know how to specify invariants that are precise enough
    to be meaningful and normative, but loose enough to
    accommodate traditional and incremental hashing, empty hash
    tables, hash tables with bucket counts that are restricted to prime
    numbers, manual rehashing, and empty hash tables. We could
    include a member function for setting the growth factor (or
    minimum load factor) but not say exactly how that number is
    used.  However, I see very little value in such a vacuous
    requirement. This proposal provides user control of the
    maximum load factor, but not of growth factor or minimum load
    factor.

What if the proposal instead mandated a rehashing policy that
provides its own interface for controlling growth/load?  This gives
implementors freedom, while offering users flexibility.  It doesn't
seem so different from an Allocator.  Presumably, a custom
allocator can have its own interface for users that need to tinker
with performance.  The default policy would not guarantee any
standard way to change the max load factor or growth factor,
since these choices are probably implementation-sensitive
anyway.  But a policy interface that allows users to plug in a
policy with predictable behaviour for their application would
seem to allow implementation freedom and satisfy most users
at the same time.

For this route, an open issue is how to define the policy interface.
Would it be better to specify it in a way that makes it easy for
users to write their own policies, or would it be better to simply
let the user choose between traditional vs. incremental, thereby
giving implementors more freedom?

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

pjp@dinkumware.com ("P.J. Plauger") wrote in message news:<3e1999a9$0$11997$724ebb72@reader2.ash.ops.us.uu.net>...
>
> Maybe it wasn't a hard choice for you, but I don't agree with the result.
> Why require manual resizing? We use incremental hashing, so the default
> behavior is sensible growth with no sophisticated intervention required
> by the user. In fact, you can use our hash_map<Key, Val> as a drop-in
> replacement for map<Key, Val>, in all but the rarest of applications.

To me the important thing is that they be fixed, so the choice of
defaults reflected my personal preference. I don't mind it to be
incremental by default, as long as I can set it to manual explicitly.
I chose manual because it's traditional and more familiar for hash
users, and because my short experience with (your ;) incremental
resizing indicated that its performance is worse.

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

pjp@dinkumware.com ("P.J. Plauger") wrote in message news:<3e1997fd$0$11995$724ebb72@reader2.ash.ops.us.uu.net>...
> "Vahan Margaryan" <marg64@yahoo.com> wrote in message
> news:44d2ad1a.0301050250.591f3563@posting.google.com...
>
> Then you might like our current implementation as a starting point.
> (See our on-line C++ Library Reference at our web site.) It packs
> various types, parameters, and functors into a single traits class.
> So hash_map has four template parameters and hash_set has only three.

I actually had your implementation in mind when talking about a single
parameter taking care of several policy issues :)

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Pete Becker" <petebecker@acm.org> wrote in message
news:3E14DEEA.A62EA317@acm.org...
> "David B. Held" wrote:
> > [...]
> > Only if you use the options.  Is there really anyone who carefully
> > studied char_traits<> before using std::string?
>
> std::string isn't a template.

Then would you object to a policy-based interface with a simplified
interface that uses the default policies?  Or a template typedef of the
same if/when we get them?

> > [...]
> > Is the "average programmer" that is so scared of template
> > parameters actually using your library?  And if it's so easy for her to
> > specify a custom allocator, why is it so hard for her to specify a non-
> > default policy, or use a class that has reasonable default policies?
>
> Once again changing the subject. The issue isn't the use of policies,
> but the use of eight template parameters.

I think it's the same issue.  If you tell the user the defaults are good
enough for modest performance, and the user does not wish to learn
about new features, she can simply accept the defaults, as she does
most of the time for Allocator.  And if the user has a specific need
that can be met by an alternative policy, then specifying 6 or 7 or 8
template parameters instead instead of writing a new container
doesn't seem like such a bad tradeoff.  If users can learn to ignore
the Compare and Allocator parameters for std::map<> (when
appropriate, which is probably most of the time), then surely they
can learn to ignore a few more parameters until there is compelling
reason to study them.

I think a simplified interface that implements the most common
policy defaults would be appropriate, but I think a configurable
interface increases the usefulness and flexibility of standard
containers, and has precedent in iostreams (and Vandevoorde &
Josuttis admit that charT is almost a policy).  Then, the average
user doesn't even have to see any extra template parameters.  But
then I have to wonder, if obscure extra template parameters are
so bad (or is 4 not "bad"?), why don't we have a simplified
std::map<> interface that fixes Allocator and/or Compare?

> > [...]
> > Then let's just provide non-template containers that only work
> > for int.
>
> There's a difference between not solving every possible problem
> and only solving a very small problem.
> [...]

The difference is a matter of degrees.  One man's "small" is another
man's "large".

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

dheld@codelogicconsulting.com ("David B. Held") wrote in message news:<v195q1ctnktmab@corp.supernews.com>...
> "Peter Dimov" <pdimov@mmltd.net> wrote in message
> news:7dc3b1ea.0301020421.6f4e4436@posting.google.com...
> > [...]
> > When evaluating policy-based designs, it's important to understand
> > the meaning of providing/not providing a particular policy. An
> > additional degree of freedom means that the library author has tried
> > several design options, has been unable to determine a "winner", and
> > is passing judgement on to the user. The lack of a certain policy
> > means "trust me, I have done the experimenting for you, don't waste
> > your time exploring the design space, it is better spent elsewhere, as
> > any potential gains are typically not worth the effort."
>
> I agree that this is the meaning for some (perhaps even many) policies.
> Perhaps in the context of the hash table proposal, that is the case.

That is what I was responding to. The suggestion was to remove
implementation freedom and replace it with policies. It is very
tempting to "resolve" controversial design issues by adding an
additional policy.

Consider the infamous list::size. It's easy to just add a "constant
size" parameter to std::list, but does it solve the problem? Will
people realize the implications of choosing a constant/linear size? Is
it likely that the constant size list generated by the parameterized
design will offer the op==/resize optimizations? The parameterized
std::list is twice as hard to test, and this is for a single binary
policy.

> But it seems to me that people are resistant to policy-based designs in
> general, and I don't think this meaning is true of all policies.

It is not.

[...]
> I submit that A) for some types, there is no sensible notion of "policy
> winner".  There may be completely complementary policies which are
> equally useful in different situations.  And B) that the lack of a policy
> does not imply that the design optimum has been found.  It could
> simply be that the author did not feel the need to provide alternatives
> via policies, for whatever reasons (including that she feels the library
> has already achieved some kind of optimum, granted; or possibly
> because the extra work simply didn't interest her).

One could also argue that presence of policies does not imply that the
design optimums are reachable within this particular parameterization.
Picking the right policy set isn't easy, and the best way (I know of)
to achieve this is to start with non-parameterized design(s) and
gather experience.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Thu, 2 Jan 2003 19:13:29 +0000 (UTC), dheld@codelogicconsulting.com
("David B. Held") wrote:

> "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> news:3e10e9ff.43255703@news.earthlink.net...
> > On Mon, 30 Dec 2002 20:33:59 +0000 (UTC), dheld@codelogicconsulting.com
> > ("David B. Held") wrote:

> > > [...]
> > > Whatever would produce the "basic" hash container with five parameters,
> > > I would expect.

> > I guess that means accept Matt's proposal.

> How does that follow?

There is a proposal.  You want three additional policy template
parameters.  You have offered no default options.  Conclusion: you
accept the proposal's defaults.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:3e15961c.1034343@news.earthlink.net...
> [...]
> There is a proposal.  You want three additional policy template
> parameters.  You have offered no default options.  Conclusion: you
> accept the proposal's defaults.

Actually, after looking at the proposal in some detail, I honestly don't
know that the contentious issues call for policy parameters.  To be
honest, I would be more interested in a policy for hash_*map that
allows you to specify the key in terms of the value, instead of having
to use just std::pair<>.  Otherwise, I think a hash_* with no storing of
hash codes, traditional rehashing, and bidirectional iterators is quite
reasonable, but only because when I think std containers, I think
"a little fat".  To be honest, I think the underspecification is a bigger
problem than the lack of policies.  Imagine if std::list were only required
to have forward iterators, but allowed to provide bidirectional as a
QoI feature.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <v1bo2p53dg2620@corp.supernews.com>, David B. Held
<dheld@codelogicconsulting.com> wrote:

| Actually, after looking at the proposal in some detail, I honestly don't
| know that the contentious issues call for policy parameters.  To be
| honest, I would be more interested in a policy for hash_*map that
| allows you to specify the key in terms of the value, instead of having
| to use just std::pair<>.  Otherwise, I think a hash_* with no storing of
| hash codes, traditional rehashing, and bidirectional iterators is quite
| reasonable, but only because when I think std containers, I think
| "a little fat".  To be honest, I think the underspecification is a bigger
| problem than the lack of policies.  Imagine if std::list were only required
| to have forward iterators, but allowed to provide bidirectional as a
| QoI feature.

I agree with the basic premise of your post.

Focusing just on the forward/bidirectional iterator issue:

An interesting exercise is to go over the 60-odd algorithms in
<algorithm> and find the algorithms that you would be able to use with
a bidirectional hash container, but not be able to use with a forward
only hash container.

While recognizing that <algorithm> in no way represents a universal set
of algorithms (go ahead and include <numeric> too just for fun), I find
it an enlightening exercise.  It gives a quantifiable answer (if only
partially) to the question:  what exactly does that extra word per node
buy me?

I'll leave the results of this little exercise for the truly interested
reader to discover on his/her own. (why spoil the fun! :-) )

--
Howard Hinnant
Metrowerks

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"David B. Held" wrote:
>
> "Pete Becker" <petebecker@acm.org> wrote in message
> news:3E148CBF.C077FB5E@acm.org...
> > "David B. Held" wrote:
> > > [...]
> > > Only if you have to specify the options every time.  If the defaults are
> > > suitable, then more options don't increase the learning time or ease of
> > > use.
> >
> > Huh? More options means more to learn.
>
> Only if you use the options.  Is there really anyone who carefully studied
> char_traits<> before using std::string?

std::string isn't a template.

>
> > [...]
> > There are add-on packages (including our CoreX library) that provide
> > useful allocators which "the average programmer" is perfectly capable
> > of using.
>
> Is the "average programmer" that is so scared of template parameters
> actually using your library?  And if it's so easy for her to specify a
> custom
> allocator, why is it so hard for her to specify a non-default policy, or use
> a class that has reasonable default policies?
>

Once again changing the subject. The issue isn't the use of policies,
but the use of eight template parameters.

> > > How are extra policy parameters any different?
> >
> > They're not. Too many options make code hard to use. You want
> > hash tables to require eight parameters. That's far more than any of
> > the current standard containers, and more than the present proposal
> > calls for.
>
> Technically, I don't care how many parameters hash tables have.  But
> I would like to see more policy parameterization in the standard
> containers.  And I don't see the significance of how many parameters
> the current containers have, except that they establish precedence.
> Why is it so evil to have a few extra template parameters?  It's not like
> anyone is asking for a new keyword. ;)
>
> > > And if a programmer decides that a different policy might be
> > > appropriate for some situation, isn't it easier to learn about
> alternative
> > > policies than to hunt for alternative containers, or write his own?
> >
> > Maybe. But the standard library doesn't have to solve every possible
> > problem.
>
> Then let's just provide non-template containers that only work for int.

There's a difference between not solving every possible problem and only
solving a very small problem.

> >
> > You're changing the subject. We were talking about eight template
> > parameters, not policy-based designs in general.
> > [...]
>
> I think most people (yourself included) would offer the same kinds of
> arguments if most other policy-based designs were substituted for the
> hash table.  Correct me if I'm wrong.
>

I'm perfectly willing to assume that you know what you think and have
reported it correctly. However, that has nothing to do with the
technical merits of templates with eight parameters.

--

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Pete Becker" <petebecker@acm.org> wrote in message
news:3E148CBF.C077FB5E@acm.org...
> They're not. Too many options make code hard to use. You want hash
> tables to require eight parameters. That's far more than any of the
> current standard containers, and more than the present proposal calls
> for.
>

It seems like this kind of issue (in general) could be much less of a
concern with template typedefs, for example you could have a low-level
8-param template, followed by several higher-level 3-param typedefs with
fixed choices for the other 5 params.

(Of course, for this case, you'd still need the full implementation of the
8-param template hash table, etc...).

Generic interfaces are more important to me than specific container
definitions, anyhow. If you don't like the std version of a container, you
can worst case just roll your own. As long as it fits the same interface, it
will work fine with generic code.

hys

--
(c) 2003 Hillel Y. Sims
hsims AT factset.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.jamesd.demon.co.uk/csc/faq.html                       ]

"David B. Held" wrote:
>
> "Pete Becker" <petebecker@acm.org> wrote in message
> news:3E10C801.87364DFF@acm.org...
> > "David B. Held" wrote:
> > >
> > > Are template parameters still that scary to people?
> >
> > Templates with eight parameters are. And they should be.
>
> Why and why?
>
> > Functions with eight parameters usually indicate a design problem.
>
> I wouldn't pass judgement until I saw the parameters and their intent.
>
> > Same for templates.
>
> And my response would be the same.  Given that you don't have to
> write all the parameters most of the time, I really don't see what the
> issue is.  Since you have to specify all non-default function parameters
> every time a function is called, I can see that an excessive number of
> parameters could be a problem.  But one usually need only specify
> template parameters once for any given type.  So is it that problematic
> that you might have to specify 8 of them instead of 5, when the
> alternative is to rewrite an entire container?

It's not a matter of what you have to specify, but of what you have to
understand. Too many options make code hard to use.

> I must be missing
> something.
>

You're missing a concrete proposal, an implementation, and real world
experience with them.

--

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Pete Becker" <petebecker@acm.org> wrote in message
news:3E11A87C.3024E244@acm.org...
> [...]
> It's not a matter of what you have to specify, but of what you have to
> understand. Too many options make code hard to use.

Only if you have to specify the options every time.  If the defaults are
suitable, then more options don't increase the learning time or ease of
use.  I dare say the average programmer would not be able to specify a
useful alternative to std::allocator<>, but that doesn't stop him from using
the standard containers.  How are extra policy parameters any different?
And if a programmer decides that a different policy might be appropriate
for some situation, isn't it easier to learn about alternative policies than
to hunt for alternative containers, or write his own?  I don't see how a
policy-based design is really harder to use than a non-policy design.  In
the default configuration, it degenerates to the single-policy usage, in
which case ease of use has not changed.  In a non-default configuration,
it surely must be easier to specify a different policy than opt for one of
the alternatives (different container, or hand-written implementation).

> > I must be missing something.
>
> You're missing a concrete proposal, an implementation, and real world
> experience with them.

Maybe for the hash table.  But I wrote a policy-based map that more or
less constitutes a concrete proposal and implementation.  However, I
have no idea how many (if any) other people have used it, so I can't
comment on "real world experience" other than my own.  And I'm not
really interested in the hash table itself so much as the issue of policy-
based design.  Another one, of course, is Loki's SmartPtr.  I dare say
it has plenty of real-world experience, and the policy parameters don't
seem to scare people who use it.

I think iostreams are much harder to use than policy-based containers,
not because of any template complexity, but because of the size of the
interface.  You might call that a case of "too many options".  And I dare
say you need to understand a lot more about how the basic_* templates
work to customize them than you do policies in a typical policy-based
framework.  But I never hear people complain that it's too hard to
make a custom streambuf or ostream.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:3e10e9ff.43255703@news.earthlink.net...
> On Mon, 30 Dec 2002 20:33:59 +0000 (UTC), dheld@codelogicconsulting.com
> ("David B. Held") wrote:
>
> > [...]
> > Whatever would produce the "basic" hash container with five parameters,
> > I would expect.
>
> I guess that means accept Matt's proposal.

How does that follow?

> > I'd put them at the end, since people who need them better know what
> > they're doing.
>
> After Allocator?

Presumably, people who feel comfortable specifying a non-default policy
don't have a problem specifying std::allocator<>, or something appropriate.

> > Or, use named template parameters or a policy adaptor
> > which allows you to only specify non-default policies.  Are template
> > parameters still that scary to people?
>
> Not likely for readers of this group, but yes for people.

And yet somehow, we have containers with that peculiar Allocator
parameter, which is arguably even more obscure and less likely to be non-
default than a policy parameter.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

dheld@codelogicconsulting.com ("David B. Held") wrote in message news:<v12i1hno2si9e5@corp.supernews.com>...
> [...] So is it that problematic
> that you might have to specify 8 of them instead of 5, when the
> alternative is to rewrite an entire container?  I must be missing
> something.

When evaluating policy-based designs, it's important to understand the
meaning of providing/not providing a particular policy. An additional
degree of freedom means that the library author has tried several
design options, has been unable to determine a "winner", and is
passing judgement on to the user. The lack of a certain policy means
"trust me, I have done the experimenting for you, don't waste your
time exploring the design space, it is better spent elsewhere, as any
potential gains are typically not worth the effort."

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"David B. Held" wrote:
>
> "Pete Becker" <petebecker@acm.org> wrote in message
> news:3E11A87C.3024E244@acm.org...
> > [...]
> > It's not a matter of what you have to specify, but of what you have to
> > understand. Too many options make code hard to use.
>
> Only if you have to specify the options every time.  If the defaults are
> suitable, then more options don't increase the learning time or ease of
> use.

Huh? More options means more to learn.

> I dare say the average programmer would not be able to specify a
> useful alternative to std::allocator<>, but that doesn't stop him from using
> the standard containers.

There are add-on packages (including our CoreX library) that provide
useful allocators which "the average programmer" is perfectly capable of
using.

> How are extra policy parameters any different?

They're not. Too many options make code hard to use. You want hash
tables to require eight parameters. That's far more than any of the
current standard containers, and more than the present proposal calls
for.

> And if a programmer decides that a different policy might be appropriate
> for some situation, isn't it easier to learn about alternative policies than
> to hunt for alternative containers, or write his own?

Maybe. But the standard library doesn't have to solve every possible
problem.

> I don't see how a
> policy-based design is really harder to use than a non-policy design.

You're changing the subject. We were talking about eight template
parameters, not policy-based designs in general.

> > > I must be missing something.
> >
> > You're missing a concrete proposal, an implementation, and real world
> > experience with them.
>
> Maybe for the hash table.

Which is what we're discussing.

> But I wrote a policy-based map that more or
> less constitutes a concrete proposal and implementation.  However, I
> have no idea how many (if any) other people have used it, so I can't
> comment on "real world experience" other than my own.  And I'm not
> really interested in the hash table itself so much as the issue of policy-
> based design.

<shrug>

--

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Pete Becker" <petebecker@acm.org> wrote in message
news:3E148CBF.C077FB5E@acm.org...
> "David B. Held" wrote:
> > [...]
> > Only if you have to specify the options every time.  If the defaults are
> > suitable, then more options don't increase the learning time or ease of
> > use.
>
> Huh? More options means more to learn.

Only if you use the options.  Is there really anyone who carefully studied
char_traits<> before using std::string?

> [...]
> There are add-on packages (including our CoreX library) that provide
> useful allocators which "the average programmer" is perfectly capable
> of using.

Is the "average programmer" that is so scared of template parameters
actually using your library?  And if it's so easy for her to specify a
custom
allocator, why is it so hard for her to specify a non-default policy, or use
a class that has reasonable default policies?

> > How are extra policy parameters any different?
>
> They're not. Too many options make code hard to use. You want
> hash tables to require eight parameters. That's far more than any of
> the current standard containers, and more than the present proposal
> calls for.

Technically, I don't care how many parameters hash tables have.  But
I would like to see more policy parameterization in the standard
containers.  And I don't see the significance of how many parameters
the current containers have, except that they establish precedence.
Why is it so evil to have a few extra template parameters?  It's not like
anyone is asking for a new keyword. ;)

> > And if a programmer decides that a different policy might be
> > appropriate for some situation, isn't it easier to learn about
alternative
> > policies than to hunt for alternative containers, or write his own?
>
> Maybe. But the standard library doesn't have to solve every possible
> problem.

Then let's just provide non-template containers that only work for int.
They're simple.  They're easy to use.  Users don't need to specify any
template parameters at all (we'll fix the allocator).  And while they don't
solve every possible problem, they solve the one that we want to solve.
Policy-based design isn't about solving every possible problem.  It's
about increasing the flexibility of a design without having to reinvent a
wheel.  I thought that's what libraries and templates and the STL were
all about.

> > I don't see how a policy-based design is really harder to use than a
> > non-policy design.
>
> You're changing the subject. We were talking about eight template
> parameters, not policy-based designs in general.
> [...]

I think most people (yourself included) would offer the same kinds of
arguments if most other policy-based designs were substituted for the
hash table.  Correct me if I'm wrong.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <v17vftdeelbac1@corp.supernews.com>, David B. Held
<dheld@codelogicconsulting.com> writes
>I think iostreams are much harder to use than policy-based containers,
>not because of any template complexity, but because of the size of the
>interface.  You might call that a case of "too many options".

And not the ones we expect. Why does this not work:

std::string filename;
std::cout << "What file do you want to open? ";
std::cin >> filename;
std::ifstream input(filename);
std::string next_line;
input.getline(next_line);

???
Why are we forcing C++ programmers to use C-style strings and out of
class functions.

--
ACCU Spring Conference 2003 April 2-5
The Conference you cannot afford to miss
Check the details: http://www.accuconference.co.uk/
Francis Glassborow      ACCU

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Peter Dimov" <pdimov@mmltd.net> wrote in message
news:7dc3b1ea.0301020421.6f4e4436@posting.google.com...
> [...]
> When evaluating policy-based designs, it's important to understand
> the meaning of providing/not providing a particular policy. An
> additional degree of freedom means that the library author has tried
> several design options, has been unable to determine a "winner", and
> is passing judgement on to the user. The lack of a certain policy
> means "trust me, I have done the experimenting for you, don't waste
> your time exploring the design space, it is better spent elsewhere, as
> any potential gains are typically not worth the effort."

I agree that this is the meaning for some (perhaps even many) policies.
Perhaps in the context of the hash table proposal, that is the case.
But it seems to me that people are resistant to policy-based designs in
general, and I don't think this meaning is true of all policies.  For some
policies, a default might simply be "good enough", but alternatives are
common enough (and provide sufficiently compelling benefit) that more
than a few people would want to use them.  Take the Boost smart
pointers, for instance.  The lack of policies in boost::shared_ptr<> hardly
says: "don't waste your time exploring the design space", because the
other designs merely appear as other non-policy types, rather than
policy configurations.  Who would argue that everyone only needs
boost::shared_ptr<>?

I submit that A) for some types, there is no sensible notion of "policy
winner".  There may be completely complementary policies which are
equally useful in different situations.  And B) that the lack of a policy
does not imply that the design optimum has been found.  It could
simply be that the author did not feel the need to provide alternatives
via policies, for whatever reasons (including that she feels the library
has already achieved some kind of optimum, granted; or possibly
because the extra work simply didn't interest her).

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

In article <86el82y6of.fsf@Zorthluthik.foo>, llewelly
<llewelly.@@xmission.dot.com> wrote:

| template<typename T>
|   T median(std::list<T> const& c)
|   {
|     typename std::list<T>::const_iterator current= c.begin(),median;
|     median= current;
|     while(true) //Warning! Exit-in-the-middle loop.
|     {
|       if(++current == c.end())break;
|       if(++current == c.end())break;
|       ++median;
|     }
|     if(median != c.end())return *median;
|     else std::abort();
|   }
|
| is O(n) Does O(1) size() have some magic property that lets you do
|     better than O(n) ?

No it does not.  However it does allow for a significant performance
improvement imho.

| (Exercise for the reader: is the median above better than using
|     advance(c.begin(),c.size()/2) ? Why or why not?)

If you know the number of elements in the list, you only have to
iterate over half of them.  And the loop doing the iteration is
somewhat simpler.  This suggests that there could be a factor of two
performance advantage if you know you have a constant complexity size.

I put your code onto my platform and timed it against the obvious
algorithm if you have O(1) size.  Naturally timings are hard to nail
down.  With short list sizes (and using double as the T) the timings
varied anywhere from the two algorithms being about the same speed, to
yours being 6 times slower.  As I increased the list size, the
variations in the timing dropped and the constant leveled out very
close to a factor of 2 difference in speed (O(N) size version slower).

I also looked at code size, and the O(1) size version of median was 80%
the size of the O(N) size version.

Now I know that an O(1) size has some disadvantages.  This is not about
that argument.  I'm simply saying that if you know what kind of size
you have, this will dictate how you will want to code this algorithm.
If you know you have an O(1) size, you don't want to throw that factor
of 2 in performance away.  And the 20% code size savings is a nice
bonus, not to mention easier to read source.  But if you know you have
an O(N) size, the algorithm you proposed is superior to
advance(c.begin(),c.size()/2) (though both still have linear
complexity).

| I've yet to see a use of list::size() I can't avoid without changing
|     the time complexity of the algorithm. I'm not saying such examples
|     don't exist; I just haven't seen one.

I agree that the time complexity isn't changing with this example.  But
changing the constant multiplier on the complexity can still be
significant.  And finding the 50% point in a sorted list is the least
important case.  If you are instead trying to find the 10% point or the
90% point in a list, my argument gets even stronger.  You only have to
traverse 10% of the list in this case.  Potentially 10 times the speed
(I have not tested that theory!).  Still linear complexity though.

Getting back to Vahn's original point:  There are analagous issues in
the hash proposal.  And there is a tradeoff between how much freedom
you give to implementors versus how much specified behavior you give to
programmers.  Going too far one way or the other can have an adverse
impact, so a good compromise is important.

For example, at the Fall Santa Cruz meeting during the hash proposal
discussions, it was proposed that the number of buckets argument to
rehash be regarded as a complete hint.  Implementations would be
allowed to completely ignore this parameter.  This gives more freedom
to implementations, but takes away some guarantees from the user which
could effect performance.  As an implementor I have little problem with
this suggestion.  But I can well imagine that such a change would not
be accepted by the user community as it further reduces the performance
guarantees that clients of hash can rely on.

--
Howard Hinnant
Metrowerks

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon, 30 Dec 2002 23:12:36 +0000 (UTC), allan_w@my-dejanews.com (Allan
W) wrote:

> I just read the standard, and I think it IS possible to implement
> all the complexity guarantees shown there -- including making size()
> constant-time (which means that list needs to store size_).

You missed the point.  It is not possible to make both size and the
range splice constant time.  The standard requires nither to be constant
time but either may be important to a user.  If either is important,
there is no way to use list portably.

You might also note that making size linear and splice constant can be
worked around by the user who needs constant size.  There is no way to
work around constant size to get constant splice.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Pete Becker" <petebecker@acm.org> wrote in message
news:3E10C801.87364DFF@acm.org...
> "David B. Held" wrote:
> >
> > Are template parameters still that scary to people?
>
> Templates with eight parameters are. And they should be.

Why and why?

> Functions with eight parameters usually indicate a design problem.

I wouldn't pass judgement until I saw the parameters and their intent.

> Same for templates.

And my response would be the same.  Given that you don't have to
write all the parameters most of the time, I really don't see what the
issue is.  Since you have to specify all non-default function parameters
every time a function is called, I can see that an excessive number of
parameters could be a problem.  But one usually need only specify
template parameters once for any given type.  So is it that problematic
that you might have to specify 8 of them instead of 5, when the
alternative is to rewrite an entire container?  I must be missing
something.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

dheld@codelogicconsulting.com ("David B. Held") wrote in message news:<v12i1hno2si9e5@corp.supernews.com>...
> > Same for templates.
>
> And my response would be the same.  Given that you don't have to
> write all the parameters most of the time, I really don't see what the
> issue is.  Since you have to specify all non-default function parameters
> every time a function is called, I can see that an excessive number of
> parameters could be a problem.  But one usually need only specify
> template parameters once for any given type.  So is it that problematic
> that you might have to specify 8 of them instead of 5, when the
> alternative is to rewrite an entire container?  I must be missing
> something.

What you may be missing is grey hair.

I've had a number of unfortunate experiences with programmers who
rejected use of a standard library or other template because of
excessive parameterization.

Note that I'm characterizing "excessive parameterization" in terms of
their skill level, not yours! For a lot of programmers, much beyond
one parameter is just too much.  Only half joking, I use the
rule-of-thumb that you lose half the potential users for each
parameter beyond the first.

The really sad thing is that the alternative they chose often wasn't
to implement their own container, but to forgo some useful application
functionality altogether.

There are probably several reasons policy-based parameterization
hasn't become as common as some hoped, but one of those reasons is
surely the added perceived complexity of more template parameters. So
far, all the named-template-parameter solutions I've seen are way too
complex and esoteric. I personally think either the language needs
built-in named-template-parameters or a generally accepted way to wrap
the policies into a single parameter before policy-based templates
will really catch on.

--Beman

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

jpotter@falcon.lhup.edu (John Potter) writes:

> On Mon, 30 Dec 2002 23:12:36 +0000 (UTC), allan_w@my-dejanews.com (Allan
> W) wrote:
>
> > I just read the standard, and I think it IS possible to implement
> > all the complexity guarantees shown there -- including making size()
> > constant-time (which means that list needs to store size_).
>
> You missed the point.  It is not possible to make both size and the
> range splice constant time.  The standard requires nither to be constant
> time but either may be important to a user.  If either is important,
> there is no way to use list portably.
>
> You might also note that making size linear and splice constant can be
> worked around by the user who needs constant size.  There is no way to
> work around constant size to get constant splice.

This was a change in the standard, by the way: an earlier draft did
require size() to be constant time.  It was changed in the course of
changes for completely unrelated reasons.  (Allocators.)


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Beman Dawes wrote:
> There are probably several reasons policy-based parameterization
> hasn't become as common as some hoped, but one of those reasons is
> surely the added perceived complexity of more template parameters.

There is experience from Ada to be had here. Ada has no automatic
instantiation of generics the way C++ does. Instead, whenever you
need an instantiation, you must create one. There is a generic
class library created by Grady Booch for Ada, but it has not found
as wide use as it might have precisely because of the number of
generic instantiations and parameters it takes to use it.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Beman Dawes" <bdawes@acm.org> wrote in message
news:70fa0367.0212310758.1042c13a@posting.google.com...
> [...]
> I've had a number of unfortunate experiences with programmers
> who rejected use of a standard library or other template because
> of excessive parameterization.

And I know plenty of "programmers" who #include <iostream.h> just
so they don't have to write std:: everywhere.

> [...]
> Only half joking, I use the rule-of-thumb that you lose half the potential
> users for each parameter beyond the first.

Yes, I've heard this before; but should we really avoid useful techniques
because some people are uncomfortable with them?  Perhaps we
should abandon namespaces too, so people don't have to use those?

> The really sad thing is that the alternative they chose often wasn't
> to implement their own container, but to forgo some useful
> application functionality altogether.

That is unfortunate, but we can't babysit every programmer that is
unwilling to learn something new.  I think catering to their laziness
instead of pushing for more education is doing them a disservice.

> There are probably several reasons policy-based parameterization
> hasn't become as common as some hoped, but one of those
> reasons is surely the added perceived complexity of more template
> parameters.

I'm sure that's true.  But I'm more inclined to think that a bigger reason
is that many types do not have an obvious policy-based
decomposition, and so programmers are not exposed to the idea of
policy-based designs as much.  If there were more common instances
of policy-based usage, perhaps novice or intermediate programmers
would feel more comfortable with them.  If the STL were not part of the
standard library, how many people would use it?  I'd wager that far
fewer than use it now.  The standard containers can push the envelope
because of their ubiquity.  Why not try to raise the bar by introducing
policy-based containers?  When people are forced to learn something
new, they often find it's not as bad as they feared.  They just need a
little motivation.  The standard library seems to me the best place to
introduce this motivation, and it seems that it would improve the state
of the art for everybody.

> So far, all the named-template-parameter solutions I've seen are way
> too complex and esoteric.

Both in implementation and usage.  I agree.  I think policy adaptors
can make policy specification about as simple as theoretically
possible; but even then, people might be intimidated.  However, if
policy-based containers put the policy parameters at the end, it would
support the historical usage, yet allow users comfortable with
specifying non-default policies to take advantage of the increased
flexibility.  How many people who use std::basic_string<> worry about
the char_traits<>?

> I personally think either the language needs built-in named-template-
> parameters or a generally accepted way to wrap the policies into a
> single parameter

That would certainly be nice, I agree.

> before policy-based templates will really catch on.

But I hope we don't have to wait that long.

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

austern@well.com (Matt Austern) writes:

[...]

| > You might also note that making size linear and splice constant can be
| > worked around by the user who needs constant size.  There is no way to
| > work around constant size to get constant splice.
|
| This was a change in the standard, by the way: an earlier draft did
| require size() to be constant time.  It was changed in the course of
| changes for completely unrelated reasons.  (Allocators.)

Wow,  that is impressive!  What were the issues?

--
Gabriel Dos Reis, gdr@integrable-solutions.net

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

scottm@toast.net ("Scott Mayo") wrote
> The std library is for people who don't want to know details
> and don't care how things perform.

Have you ever met a professional programmer who never cares how
his/her program performs? (If so, what were they paid for?)

> If you need to know the
> mechanics, write your own. It's rarely difficult, unless you have
> really complex data structuring needs (in which case the
> standard classes are probably no fun either.)
> I've yet to use std::vector, list, hash, or any of the other containers
> of C++. I got used to writing my own, years before in C, and
> I never got out of the habit - and when it comes time to tune
> things, it's wonderfully freeing.

It's good to know that whenever the standard structures don't (or might
not, on a given platform) do what you need, you can define your own.

One problem with overusing this technique, is library code. We're
trying to encourage use of library containers rather than raw arrays.
That either means that library code must be distributed as templates,
or it has to pick some standard container type (i.e. std::vector) to
use. Obviously, then, library code can't use your custom 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://www.jamesd.demon.co.uk/csc/faq.html                       ]

eldiener@earthlink.net (Edward Diener) wrote in message news:<_PjO9.6040$b97.624266@newsread2.prod.itd.earthlink.net>...
> "Vahan Margaryan" <marg64@yahoo.com> wrote in message
> news:44d2ad1a.0212230733.2cd3256f@posting.google.com...
> > I suggest that hash containers be based on policies (with meaningful
> > default values) to regulate their various aspects. Let's not repeat
> > the mistake of std::list, which can't be used portably because of
> > different implementation strategies used by different vendors.
>
> Because a std::list has different internal implementations does not mean
> that it can't be used portably. As long as the external interface
> corresponds to the C++ standard, I as a programmer expect to be able to use
> it portably in my programs as long as I follow the external interface
> correctly.

On some implementations std::list::size takes constant time, on others
its linear, and the same is true for std::list::splice. If we define
'external interface' as signatures + complexity specifications, then
std::list's interface isn't the same across the implementations. By
portability I don't just mean the ability to compile the code, I mean
not having to do additional work (like rewriting the algorithms).

> That doesn't mean that new template-based libraries can't be more
> policy-based to provide greater compile time flexibility as part of its
> design, but only that attacking std::list, or any other std:: container,
> does not support any point about portability at all. Policy-based templates
> are not about portability but are really about flexibility. There is always
> a tradeoff of course between flexibility and simplicity which centers around
> ease of understanding and use. At some middle ground good design decisions
> are made.


I agree that policies are about flexibility, not about portability.
The issue is - there are several implementation strategies. If the
implementors are allowed to choose any strategy, portability is
reduced. If only one strategy is mandated - some good features are
lost. That's why I suggest to use policies to combine the good sides
of various implementations, while allowing the user to  specify
through policy arguments which strategy is desired (thus ensuring
portable performance).

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

NOSPAMsjhowe@dial.pipex.com ("Stephen Howe") wrote in message news:<3e0d11cc$0$230$cc9e4d1f@news.dial.pipex.com>...
> > But I do find the situation with std::list rather sad.
>
> Could you elaborate? I am not sure what you mean
>
> Stephen Howe
>

Please see Howard Hinnant's post to this thread, it explains the
issue. I've posted a reply there too, but it somehow didn't go reach
the newsgroup, so I reposted it today.

Details about the std::list issues can be found in Effective STL by
Meyers, Item 4.

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Fri, 27 Dec 2002 21:18:50 +0000 (UTC), hinnant@metrowerks.com (Howard
Hinnant) wrote:

> 23.1/5 has this to say about the complexity of size():

> | should have constant complexity

> Here, "should" does not mean "must".  It means "may or may not".  In
> practice, all of the std::containers have a constant complexity size,
> except for std::list.  On this container some implementations have a
> linear complexity size (implemented as if std::distance(c.begin(),
> c.end())), while other implementations (including Metrowerks) have a
> constant complexity size.

Here the time tradeoff is simple.  We get O(1) for either size() or
void list<T>::splice (iter i, list<T>& d, iter f, iter p)

Since I have found no use for either of them, I would need to decide in
total ignorance of usage.  If I make size constant time, there is no way
for the user to make splice constant time.  If I make splice constant
time, the user can keep track of size as well as the implementation.  It
seems a no brainer; however, Metrowerks and others made the other
choice.  I guess that it was based on the average user not using splice
and using size when it was not needed.  Having seen many search bound
applications use list, I guess that does make sense for the average
user.

The hash tradeoffs are not as simple.  The choices are specify it, let
the implementation decide, introduce policies.  List is the precident.
Others have asked for policy choice of associative implementation.  How
about a retrofit there also?

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon, 23 Dec 2002 23:29:24 +0000 (UTC),P.J. Plauger wrote:

>"Vahan Margaryan" wrote in message
>news:44d2ad1a.0212230733.2cd3256f@posting.google.com...

>> I suggest that hash containers be based on policies (with meaningful
>> default values) to regulate their various aspects. Let's not repeat
>> the mistake of std::list, which can't be used portably because of
>> different implementation strategies used by different vendors.
>
>Seems to me that similar mistakes were also made in deque. And vector.
>And map. And set. And ...

I would prefer that those collections were indeed also more tightly
specified - in particular in terms of memory usage:

As I understand it, there is no standard-guaranteed way to shrink a
vector to fit (the usual advice, involving swapping with a
newly-constructed copy has no space guarantees - though it tends to
work)

A deque is usually implemented with a number of fixed-size pages, but
there is no standard way to find or influence the size of the page, and
different implementations may make very different choices. I learned the
hard way not to include a typically nearly empty deque as a member of a
relatively small class used in large numbers, as the page-size chosen by
the implementation dominated the memory usage of the application.

Where possible, I want to choose the trade-offs when I am writing the
code (if it matters - and in most cases it won't matter), and not have
surprised when the program is subsequently ported by someone unfamiliar
with it to a new platform. I would be satisfied with the ability to
write compile-time asserts on the implementation choices, so that any
decisions I am relying on can be looked at in detail if the library has
changed sufficiently.

Yes, I could write my own containers - and for situations where I have
measured and found a performance hot-spot I will do so. The hard call is
when we are currently using an implementation with choices which match
our requirements, but might at some future date adopt a new platform.
I don't want to write my own containers "just in case", a future
implementation makes choice that are incompatible with my requirements.

Tim
--
Tim Sharrock   (tim@sharrock.org.uk)

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

> > This is true of many aspects of the compiler and library. One reason is
> > to allow the local implementor the chance to take advantage of platform-
> > dependant optimizations, without sacrificing portability for code that
> > uses it.
>
> I generally don't mind leaving some stuff for the implementor to
> decide. I just think that the current proposal is underspecified. I
> think that it defines several different data structures rather than
> one.

If that is the case, why don't you reword it and resubmit it?
Nobody will mind that. More food for thought.

> In short, some std::list implementations provide constant-time size()
> and linear splice(), some provide linear size() and constant-time
> splice(). That's because when you splice a range of elements into the
> list, you need to count them to modify the stored size_ member
> correctly. If you don't store size_, you can avoid counting them, but
> size() becomes linear.

I wondered if it was that. You could also update size_ for member functions
that change it, except splice() which would store something invalid. size()
would return the value if valid or do a count if invalid. That means if
splice() is never used, size() will be O(1) and if splice() is used then
splice is O(1) and size() O(N).

Stephen Howe


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

NOSPAMsjhowe@dial.pipex.com ("Stephen Howe") wrote in message news:<3e0d1519$0$229$cc9e4d1f@news.dial.pipex.com>...
>
> If that is the case, why don't you reword it and resubmit it?
> Nobody will mind that. More food for thought.

I might try doing that, if I find time. But generally, I don't think
that criticisms should necessarily be accompanied by alternative
proposals. Writing a decent proposal isn't easy and requires
understanding of the language and the standard that not everyone has.
By analogy, I don't have to (and can't) submit an alternative law
formulation every time I dislike something in the existing
legislation.

> I wondered if it was that. You could also update size_ for member functions
> that change it, except splice() which would store something invalid. size()
> would return the value if valid or do a count if invalid. That means if
> splice() is never used, size() will be O(1) and if splice() is used then
> splice is O(1) and size() O(N).
>

True, that's yet another possible solution (I haven't seen it
implemented anywhere). And this further reinforces my point: the
multitude of legal implementations that have different performance
characteristics takes away my control over the behavior of my code
across the platforms.

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

On Sat, 28 Dec 2002 19:58:26 +0000 (UTC), marg64@yahoo.com (Vahan
Margaryan) wrote:

> I agree that policies are about flexibility, not about portability.
> The issue is - there are several implementation strategies. If the
> implementors are allowed to choose any strategy, portability is
> reduced. If only one strategy is mandated - some good features are
> lost. That's why I suggest to use policies to combine the good sides
> of various implementations, while allowing the user to  specify
> through policy arguments which strategy is desired (thus ensuring
> portable performance).

The hash containers now require five template parameters and you want to
add three more.  What are the defaults for those extra three parameters
and in what order do they appear with respect to the current five?

For some reason, this reminds me of the articles around the time of the
STL being introduced where BS proded AS to remove extra template
parameters.  The rule at that time was standardize a useful version.
Those who need specialized versions are also those who know how to
implement the specializations.  A container which does everything will
be used by none.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

>
> In short, some std::list implementations provide constant-time size()
> and linear splice(), some provide linear size() and constant-time
> splice(). That's because when you splice a range of elements into the
> list, you need to count them to modify the stored size_ member
> correctly. If you don't store size_, you can avoid counting them, but
> size() becomes linear.
>
> Both choices are reasonable (although I lean towards the second). I
> consider this a portability issue. Please see Item 4 of Effective STL
> for a detailed discussion.
>
> Thank you,
> -Vahan
>

Maybe in that case the best thing would be to uses set the size to -1 when
splice is invoked and adding an extra pointer to the list head or list
information in each node... So it would be possible to have constant
complexity if only one of size or splice is used and otherwise the
complexity would be amortized...

I do think that the option to have constant-time splice is preferable
because this is one of the purpose of a list to be able to uses function
like splice, merge,...

In practice, I think that it is irrelevant which one is constant and which
one is linear for most applications and if matters maybe either another
container or another algorithm should be used.

Also if an algorithm is really slow with one container, it may be preferable
to create another container with the same content and apply the algorithm on
it. Or compute the size once at the beggining and adjusting it by hand...

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"John Potter" <jpotter@falcon.lhup.edu> wrote in message
news:3e0e0c77.107661015@news.earthlink.net...
> [...]
> The hash containers now require five template parameters and you
> want to add three more.  What are the defaults for those extra three
> parameters

Whatever would produce the "basic" hash container with five parameters,
I would expect.

> and in what order do they appear with respect to the current five?

I'd put them at the end, since people who need them better know what
they're doing.  Or, use named template parameters or a policy adaptor
which allows you to only specify non-default policies.  Are template
parameters still that scary to people?

> For some reason, this reminds me of the articles around the time of the
> STL being introduced where BS proded AS to remove extra template
> parameters.  The rule at that time was standardize a useful version.
> Those who need specialized versions are also those who know how to
> implement the specializations.  A container which does everything will
> be used by none.

What if it does everything, but looks like it only does one thing?  By
unifying potentially different implementations into a policy framework,
you save people the trouble of reimplementing the 40-80% of the
stuff that is basically the same.  Why should we have to rewrite a
standard container from scratch just because we need a 20%
difference in functionality that could be trivially obtained through an
alternate policy?

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

marg64@yahoo.com (Vahan Margaryan) wrote
> > > Let's not repeat
> > > the mistake of std::list, which can't be used portably because of
> > > different implementation strategies used by different vendors.

> allan_w@my-dejanews.com (Allan W) wrote
> > I haven't used std::list very much, so I'm ignorant of this mistake.
> > Are you talking about iterators becoming invalid, or something else?
> > Please explain why different implementatin strategies make it non-
> > portable.

> In short, some std::list implementations provide constant-time size()
> and linear splice(), some provide linear size() and constant-time
> splice(). That's because when you splice a range of elements into the
> list, you need to count them to modify the stored size_ member
> correctly. If you don't store size_, you can avoid counting them, but
> size() becomes linear.
>
> Both choices are reasonable (although I lean towards the second). I
> consider this a portability issue. Please see Item 4 of Effective STL
> for a detailed discussion.

I just read the standard, and I think it IS possible to implement
all the complexity guarantees shown there -- including making size()
constant-time (which means that list needs to store size_).

There are THREE versions of splice.

    splice(iter position, list x) 23.2.2.4/6 Constant time.
        Inserts ALL elements from X after position.
        Shouldn't be hard to make this one constant time...
        Insert all of X's elements into this, remove from x, then
        this.size_ += x.size_; x.size_ = 0;

    splice(iter position, list x, iter i) 23.2.2.4/10 Constant time.
        Inserts ONE element from X after position.
        Shouldn't be hard to make this one constant time...
        Add element i to this, remove from x, then
        ++this.size_; --x.size_;

    splice(iter position, list x, iter first, iter last)
            23.2.2.4/14 Constant time if this==&x; else linear time
        Inserts [first,last) after position.
        Very hard to make this linear time, because you don't know how
            many elements in the range... but this version of splice()
            is only required to be linear!
        If all else fails, this is guaranteed to be linear:
            for (iter z=first; z!=last; ++z) splice(position, x, z);
        Special case when this==&x, but I doubt you'll argue that the
        special case can't be made constant time...

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"David B. Held" wrote:
>
> Are template
> parameters still that scary to people?
>

Templates with eight parameters are. And they should be. Functions with
eight parameters usually indicate a design problem. Same for templates.

--

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

eldiener@earthlink.net (Edward Diener) wrote in message news:<_PjO9.6040$b97.624266@newsread2.prod.itd.earthlink.net>...
> Because a std::list has different internal implementations does not mean
> that it can't be used portably. As long as the external interface
> corresponds to the C++ standard, I as a programmer expect to be able to use
> it portably in my programs as long as I follow the external interface
> correctly.

On some implementations std::list::size takes constant time, on others
its linear, and the same is true for std::list::splice. If we define
'external interface' as signatures + complexity specifications, then
std::list's interface isn't the same across the implementations. By
portability I don't just mean the ability to compile the code, I mean
not having to do additional work (like rewriting the algorithms).

> That doesn't mean that new template-based libraries can't be more
> policy-based to provide greater compile time flexibility as part of its
> design, but only that attacking std::list, or any other std:: container,
> does not support any point about portability at all. Policy-based templates
> are not about portability but are really about flexibility. There is always
> a tradeoff of course between flexibility and simplicity which centers around
> ease of understanding and use. At some middle ground good design decisions
> are made.

I agree that policies are about flexibility, not about portability.
The issue is - there are several implementation strategies. If the
implementors are allowed to choose any strategy, portability is
reduced. If only one strategy is mandated - some good features are
lost. That's why I suggest to use policies to combine the good sides
of various implementations, while allowing the user to  specify
through policy arguments which strategy is desired (thus ensuring
portable performance).

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Vahan Margaryan wrote:
>
> I agree that policies are about flexibility, not about portability.
> The issue is - there are several implementation strategies. If the
> implementors are allowed to choose any strategy, portability is
> reduced. If only one strategy is mandated - some good features are
> lost. That's why I suggest to use policies to combine the good sides
> of various implementations, while allowing the user to  specify
> through policy arguments which strategy is desired (thus ensuring
> portable performance).
>

I look forward to seeing your proposal and its accompanying
implementation.

--

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://www.jamesd.demon.co.uk/csc/faq.html                       ]

On Mon, 30 Dec 2002 20:33:59 +0000 (UTC), dheld@codelogicconsulting.com
("David B. Held") wrote:

> "John Potter" <jpotter@falcon.lhup.edu> wrote in message
> news:3e0e0c77.107661015@news.earthlink.net...
> > [...]
> > The hash containers now require five template parameters and you
> > want to add three more.  What are the defaults for those extra three
> > parameters
>
> Whatever would produce the "basic" hash container with five parameters,
> I would expect.

I guess that means accept Matt's proposal.

> > and in what order do they appear with respect to the current five?

> I'd put them at the end, since people who need them better know what
> they're doing.

After Allocator?

> Or, use named template parameters or a policy adaptor
> which allows you to only specify non-default policies.  Are template
> parameters still that scary to people?

Not likely for readers of this group, but yes for people.

John

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Allan W" <allan_w@my-dejanews.com> wrote in message
news:7f2735a5.0212301416.2f0ff3b8@posting.google.com...
> marg64@yahoo.com (Vahan Margaryan) wrote
> I just read the standard, and I think it IS possible to implement
> all the complexity guarantees shown there -- including making size()
> constant-time (which means that list needs to store size_).
>
> There are THREE versions of splice.
>
>     splice(iter position, list x) 23.2.2.4/6 Constant time.
>         Inserts ALL elements from X after position.
>         Shouldn't be hard to make this one constant time...
>         Insert all of X's elements into this, remove from x, then
>         this.size_ += x.size_; x.size_ = 0;
>
>     splice(iter position, list x, iter i) 23.2.2.4/10 Constant time.
>         Inserts ONE element from X after position.
>         Shouldn't be hard to make this one constant time...
>         Add element i to this, remove from x, then
>         ++this.size_; --x.size_;
>
>     splice(iter position, list x, iter first, iter last)
>             23.2.2.4/14 Constant time if this==&x; else linear time
>         Inserts [first,last) after position.
>         Very hard to make this linear time, because you don't know how
>             many elements in the range... but this version of splice()
>             is only required to be linear!

It's trivial to make this constant time even when this != &x (the requirement
is instead that the allocators are the same) -- but it means making size
linear time at least some of the time.

Personally, I would much prefer the standard to require splicing for lists be
constant time; splicing is one of the special features a linked list has, so
it would make sense to make it fast.  The library I normally use (Dinkumware
w/VC++) does constant time splicing for this version of the function if you're
adding the entire list or if this == &x, but not for adding partial lists.


--
Now Playing:  Mike Oldfield - Punkadiddle (Live)


char a[99999],*p=a;main(int c,char**V){char* v=c>0?1[V]:V;if(c<0)for(c=1;c;c
+=!(91^*v)-!(93^*v),++v);else for(;(c=*v)&&93^c;p+=!(62^c)-!(60^c),*p+=!(43^
c)-!(45^c),44^c||read(0,p,1),46^c||putchar(*p),91^c||(v=*p?main(0,++v),v-2:\
main(-1,++v)-1),++v);return v;}/*bf prog as argv[1]. drpizza@battleaxe.net*/


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

In article <_PjO9.6040$b97.624266@newsread2.prod.itd.earthlink.net>,
Edward Diener <eldiener@earthlink.net> wrote:

| "Vahan Margaryan" <marg64@yahoo.com> wrote in message
| news:44d2ad1a.0212230733.2cd3256f@posting.google.com...
| > I suggest that hash containers be based on policies (with meaningful
| > default values) to regulate their various aspects. Let's not repeat
| > the mistake of std::list, which can't be used portably because of
| > different implementation strategies used by different vendors.
|
| Because a std::list has different internal implementations does not mean
| that it can't be used portably. As long as the external interface
| corresponds to the C++ standard, I as a programmer expect to be able to use
| it portably in my programs as long as I follow the external interface
| correctly.

While I don't agree with Vahan's suggestion of policy-based hash
containers, I very much sympathize with his motivation, and heartily
agree about std::list.

It is true that some portability is lost with std::list, and if you
want to get technical, with all of the std::containers.  I believe what
Vahan is referring to is the complexity guarantees (or lack thereof) on
the size() member function.

23.1/5 has this to say about the complexity of size():

| should have constant complexity

Here, "should" does not mean "must".  It means "may or may not".  In
practice, all of the std::containers have a constant complexity size,
except for std::list.  On this container some implementations have a
linear complexity size (implemented as if std::distance(c.begin(),
c.end())), while other implementations (including Metrowerks) have a
constant complexity size.

This is most definitely an impediment to writing portable code.  For
example, Koenig and Moo's excellent book "Accelerated C++" uses an
example function for educational purposes called "median".  This
function takes a vector as a parameter and returns the median of the
vector.  Try writing a portable /and/ efficient version of this
function, but taking a std::list as the parameter instead.

template <class T>
T median(std::list<T> c);

You can either be portable, or you can be efficient, but not both.  If
you know you have a constant complexity list::size, you will want to do
it one way.  If you know you have a linear complexity list::size, you
will want to code a different algorithm.

The analogy from list::size to the hash containers is a good one.  One
often needs to depend on the order of the complexity in either space or
time in order to write code with acceptable performance.  All three of
the issues Vahan brings up can have a "big O" impact in either space or
time.

Pretending that coders don't need to know such details will inevitably
introduce mediocrity at some level.  Yeah, list::size is portable.
Yeah, right. ;-(

--
Howard Hinnant
Metrowerks

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

allan_w@my-dejanews.com (Allan W) wrote in message news:<7f2735a5.0212241204.65a165a9@posting.google.com>...
> marg64@yahoo.com (Vahan Margaryan) wrote
>
> This is true of many aspects of the compiler and library. One reason is
> to allow the local implementor the chance to take advantage of platform-
> dependant optimizations, without sacrificing portability for code that
> uses it.

I generally don't mind leaving some stuff for the implementor to
decide. I just think that the current proposal is underspecified. I
think that it defines several different data structures rather than
one.

> Why?
> What would you do differently if the hash-table
>   * Stores hash codes, or does not? (Not a hash expert -- but don't they
>     all store their hash codes?)

The (few) ones I've seen don't store hash-codes. I sometimes store
them myself in my objects (or wrapper objects) to improve performance.
Then, if I port to a hash-code-storing implementation, my code becomes
meaningless. OTOH, storing hash-codes imposes storage overhead.

>   * Uses traditional, or incremental rehashing? (Seems to me that if
>     the initial size is good, rehashing isn't an issue anyway.)

Rehashing is a very important aspect of hash performance. I usually
prefer to use manual rehashing. For my purposes, incremental rehashing
has performed worse, and I don't want it to work in my code. But
someone might want rely on the incremental rehashing. When ported to a
platform that doesn't provide it, his code would become (very) slow.

>   * Uses bidirectional iterators, or not? (If your code requires
>     bidirectional iterators, it simply won't work without them... true?)

Most implementations provide bidirectional iterators, so it's a pity
that I can't use them because the standard doesn't guarantee their
presence. OTOH, implementations with forward-only iterators take less
space, which is often important. But I can't rely on that either,
because bidirectional iterators are allowed too. So I really won't
know how my code will perform in terms of space...

> Seems to me that you'd only have to re-profile your hash performance
> if your hash function changes. But the proposed version allows you to
> specify your own hash function anyway. Do so, and you no longer need
> to worry about hash charactaristics each time.

As shown above, variations in the implementation change aspects of the
operation of the hash-table.

> > I suggest that hash containers be based on policies (with meaningful
> > default values) to regulate their various aspects.
>
> Whether this proposal becomes part of the next standard or not, you
> can always write your own STL-like containers and use them with
> standard algorithms, etc. If you really need this fine control over
> the container, that's the way to go.

I realize that I can do it myself, but I'd sure like the standard
library vendor to do it for me :) And I'd like the std library to be
usable in real projects.

> I haven't used std::list very much, so I'm ignorant of this mistake.
> Are you talking about iterators becoming invalid, or something else?
> Please explain why different implementatin strategies make it non-
> portable.

In short, some std::list implementations provide constant-time size()
and linear splice(), some provide linear size() and constant-time
splice(). That's because when you splice a range of elements into the
list, you need to count them to modify the stored size_ member
correctly. If you don't store size_, you can avoid counting them, but
size() becomes linear.

Both choices are reasonable (although I lean towards the second). I
consider this a portability issue. Please see Item 4 of Effective STL
for a detailed discussion.

Thank you,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

> But I do find the situation with std::list rather sad.

Could you elaborate? I am not sure what you mean

Stephen Howe


---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

hinnant@metrowerks.com (Howard Hinnant) writes:

[snip]
> While I don't agree with Vahan's suggestion of policy-based hash
> containers, I very much sympathize with his motivation, and heartily
> agree about std::list.
>
> It is true that some portability is lost with std::list, and if you
> want to get technical, with all of the std::containers.  I believe what
> Vahan is referring to is the complexity guarantees (or lack thereof) on
> the size() member function.
>
> 23.1/5 has this to say about the complexity of size():
>
> | should have constant complexity
>
> Here, "should" does not mean "must".  It means "may or may not".  In
> practice, all of the std::containers have a constant complexity size,
> except for std::list.  On this container some implementations have a
> linear complexity size (implemented as if std::distance(c.begin(),
> c.end())), while other implementations (including Metrowerks) have a
> constant complexity size.
>
> This is most definitely an impediment to writing portable code.  For
> example, Koenig and Moo's excellent book "Accelerated C++" uses an
> example function for educational purposes called "median".  This
> function takes a vector as a parameter and returns the median of the
> vector.  Try writing a portable /and/ efficient version of this
> function, but taking a std::list as the parameter instead.
>
> template <class T>
> T median(std::list<T> c);
>
> You can either be portable, or you can be efficient, but not both.
[snip]

template<typename T>
  T median(std::list<T> const& c)
  {
    typename std::list<T>::const_iterator current= c.begin(),median;
    median= current;
    while(true) //Warning! Exit-in-the-middle loop.
    {
      if(++current == c.end())break;
      if(++current == c.end())break;
      ++median;
    }
    if(median != c.end())return *median;
    else std::abort();
  }

is O(n) Does O(1) size() have some magic property that lets you do
    better than O(n) ?

(Exercise for the reader: is the median above better than using
    advance(c.begin(),c.size()/2) ? Why or why not?)

I've yet to see a use of list::size() I can't avoid without changing
    the time complexity of the algorithm. I'm not saying such examples
    don't exist; I just haven't seen one.



---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

pjp@dinkumware.com ("P.J. Plauger") wrote in message news:<3e07641c$0$19521$4c41069e@reader0.ash.ops.us.uu.net>...
> "Vahan Margaryan" <marg64@yahoo.com> wrote in message
> news:44d2ad1a.0212230733.2cd3256f@posting.google.com...
>
> > It seems that the purpose of the proposal is to make
> > maximum number of existing hash implementations automatically
> > conforming, rather than to ensure real portability of the code that
> > uses hash-containers.
>
> You can't have both?

With the current proposal - no. Implementations differ, so the code
isn't
really portable, in the sense that it can't be ported without
additional
effort.


> Then pick up your marbles and go home. Put only slightly more
> politely, it sounds like your needs are so demanding that no
> standard library implementation is likely to fill your needs.

You are right in that sometimes a custom solution needs to be made.
But I disagree that my current requirements are too demanding. I just
want
to know more precisely what data structure I am actually using.

For example, I sometimes store hash-codes in my objects to ensure
faster
hash performance. If I port my code to an implementation that stores
hash
codes itself, it no longer makes sense. Rewrite?

If I can write a good algorithm using bidirectional iterators, should
I use a worse one instead because some implementation might not have
them?

If I store pointers in my hash containers (which is not uncommon),
should I
ignore the significant space overhead of doubly-linked list?

> Your stated requirements would certainly add sufficient cruft
> to a template hash container as to compromise its usability
> by most civilians.

If meaningful policies are provided as default template arguments, the
civilians that don't care won't see an interface any different from an
ordinary container. It's still hash_set<T, Hash> a;. OTOH, the same
civilians won't encounter surprises when porting that default-ed hash
to
a different platform.

> Seems to me that similar mistakes were also made in deque. And vector.
> And map. And set. And ...

I don't have enough experience porting all std containers to tell if
such
mistakes were made. I wonder if any non-standard vector implementation
methods
have ever been used. But I do find the situation with std::list rather
sad.

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Vahan Margaryan" <marg64@yahoo.com> wrote in message
news:44d2ad1a.0212230733.2cd3256f@posting.google.com...
> I suggest that hash containers be based on policies (with meaningful
> default values) to regulate their various aspects. Let's not repeat
> the mistake of std::list, which can't be used portably because of
> different implementation strategies used by different vendors.

Because a std::list has different internal implementations does not mean
that it can't be used portably. As long as the external interface
corresponds to the C++ standard, I as a programmer expect to be able to use
it portably in my programs as long as I follow the external interface
correctly.

That doesn't mean that new template-based libraries can't be more
policy-based to provide greater compile time flexibility as part of its
design, but only that attacking std::list, or any other std:: container,
does not support any point about portability at all. Policy-based templates
are not about portability but are really about flexibility. There is always
a tradeoff of course between flexibility and simplicity which centers around
ease of understanding and use. At some middle ground good design decisions
are made.

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

marg64@yahoo.com (Vahan Margaryan) wrote
> Hello,
> I've brought up this problem with the proposed hash containers before,
> but haven't observed any reaction.
>
> The proposal (its current version at
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1399.html)
> leaves many aspects of the operation of hash containers to the
> implementors.

This is true of many aspects of the compiler and library. One reason is
to allow the local implementor the chance to take advantage of platform-
dependant optimizations, without sacrificing portability for code that
uses it.

> It seems that the purpose of the proposal is to make
> maximum number of existing hash implementations automatically
> conforming, rather than to ensure real portability of the code that
> uses hash-containers.

Seems reasonable to me.

> When I use a hash-table in a real project, I need to know whether it
> stores hash codes, whether it uses incremental or traditional
> rehashing, whether its iterators are bidirectional or not.

Why? What would you do differently if the hash-table
  * Stores hash codes, or does not? (Not a hash expert -- but don't they
    all store their hash codes?)
  * Uses traditional, or incremental rehashing? (Seems to me that if
    the initial size is good, rehashing isn't an issue anyway.)
  * Uses bidirectional iterators, or not? (If your code requires
    bidirectional iterators, it simply won't work without them... true?)

> If these
> things change when porting the code from one implementation to
> another, I have to profile hash performance again, I need to rewrite
> code - that's not a portable container, that's a toy.

Seems to me that you'd only have to re-profile your hash performance
if your hash function changes. But the proposed version allows you to
specify your own hash function anyway. Do so, and you no longer need
to worry about hash charactaristics each time.

> I suggest that hash containers be based on policies (with meaningful
> default values) to regulate their various aspects.

Whether this proposal becomes part of the next standard or not, you
can always write your own STL-like containers and use them with
standard algorithms, etc. If you really need this fine control over
the container, that's the way to go.

> Let's not repeat
> the mistake of std::list, which can't be used portably because of
> different implementation strategies used by different vendors.

I haven't used std::list very much, so I'm ignorant of this mistake.
Are you talking about iterators becoming invalid, or something else?
Please explain why different implementatin strategies make it non-
portable.

Thanks!

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

Hello,
I've brought up this problem with the proposed hash containers before,
but haven't observed any reaction.

The proposal (its current version at
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1399.html)
leaves many aspects of the operation of hash containers to the
implementors. It seems that the purpose of the proposal is to make
maximum number of existing hash implementations automatically
conforming, rather than to ensure real portability of the code that
uses hash-containers.

When I use a hash-table in a real project, I need to know whether it
stores hash codes, whether it uses incremental or traditional
rehashing, whether its iterators are bidirectional or not. If these
things change when porting the code from one implementation to
another, I have to profile hash performance again, I need to rewrite
code - that's not a portable container, that's a toy.

I suggest that hash containers be based on policies (with meaningful
default values) to regulate their various aspects. Let's not repeat
the mistake of std::list, which can't be used portably because of
different implementation strategies used by different vendors.

Regards,
-Vahan

---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]

"Vahan Margaryan" <marg64@yahoo.com> wrote in message
news:44d2ad1a.0212230733.2cd3256f@posting.google.com...

> The proposal (its current version at
> http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2002/n1399.html)
> leaves many aspects of the operation of hash containers to the
> implementors. It seems that the purpose of the proposal is to make
> maximum number of existing hash implementations automatically
> conforming, rather than to ensure real portability of the code that
> uses hash-containers.

You can't have both?

> When I use a hash-table in a real project, I need to know whether it
> stores hash codes, whether it uses incremental or traditional
> rehashing, whether its iterators are bidirectional or not. If these
> things change when porting the code from one implementation to
> another, I have to profile hash performance again, I need to rewrite
> code - that's not a portable container, that's a toy.

Then pick up your marbles and go home. Put only slightly more
politely, it sounds like your needs are so demanding that no
standard library implementation is likely to fill your needs.
Your stated requirements would certainly add sufficient cruft
to a template hash container as to compromise its usability
by most civilians.

> I suggest that hash containers be based on policies (with meaningful
> default values) to regulate their various aspects. Let's not repeat
> the mistake of std::list, which can't be used portably because of
> different implementation strategies used by different vendors.

Seems to me that similar mistakes were also made in deque. And vector.
And map. And set. And ...

P.J. Plauger
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://www.jamesd.demon.co.uk/csc/faq.html                       ]

"Vahan Margaryan" <marg64@yahoo.com>:
> When I use a hash-table in a real project, I need to know whether it
> stores hash codes, whether it uses incremental or traditional
> rehashing, whether its iterators are bidirectional or not.

The std library is for people who don't want to know details
and don't care how things perform. If you need to know the
mechanics, write your own. It's rarely difficult, unless you have
really complex data structuring needs (in which case the
standard classes are probably no fun either.)

I've yet to use std::vector, list, hash, or any of the other containers
of C++. I got used to writing my own, years before in C, and
I never got out of the habit - and when it comes time to tune
things, it's wonderfully freeing.




---
[ 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.jamesd.demon.co.uk/csc/faq.html                       ]