Topic: New STL? (From C++0x.)
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 20:50:41 GMT Raw View
"Al Grant" <tnarga@arm.REVERSE-NAME.com> wrote in message news:<9e2k1k$f5f$1@cam-news1.cambridge.arm.com>...
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3B046F36.8C234F99@wizard.net...
> > Al Grant wrote:
> > > If the default allocator is an empty class and the container
> > > contains the allocator as a member (as in P.J. Plauger's STL)
> > > then a container without an allocator would be smaller.
> > Why? There's no need for a container to keep a copy of the the
> > allocator.
> I know, SGI's STL doesn't. But Plauger's does and there must be a
> reason for that.
I'm just guessing, but earlier drafts did require keeping a copy of
the allocator (although possibly as a base class). It may be that
Plauger's code dates from then, and that there have been more
important improvements to make since then.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Al Grant" <tnarga@arm.REVERSE-NAME.com>
Date: Mon, 11 Jun 2001 20:51:11 GMT Raw View
"James Kanze" <kanze@gabi-soft.de> wrote in message
news:d6651fb6.0106110611.354f3150@posting.google.com...
> brangdon@cix.co.uk (Dave Harris) wrote in message
news:<memo.20010516142615.38693D@brangdon.madasafish.com>...
> > OK... what do you use them for? My understanding is that allocators
> > were introduced for the sake of 16-bit Intel platforms with
> > segment-based pointers.
>
> This is my understanding as well, but I wasn't active in the library
> group at the time, so I really can't be sure.
You can use them to
- place objects in memory with different protection
regimes, performance characteristics etc.
- pre-allocate resources between different parts of the
program, preventing a global crash on out-of-memory
- reclaim storage by allocating all objects in a pool
and then freeing the pool
- monitor (reflectively or externally) resource consumption
Isn't the need for allocators obvious? What's less
obvious is the need for a default allocator and default
'new'. It just makes it easier to write bad software.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: news_comp.std.c++_expires-2001-09-01@nmhq.net (Niklas Matthies)
Date: Mon, 11 Jun 2001 20:53:35 GMT Raw View
On Mon, 11 Jun 2001 18:27:55 GMT, James Kanze <kanze@gabi-soft.de> wrote:
[=B7=B7=B7]
> I like the rule that all function names are verbs or verbal phrases.
> According to this, however, empty() must be the active verb, isEmpty()
> would be the function to access the state. And of course, setEmpty()
> really wouldn't mean anything. In this particular case, however, I
> don't have any problem with the fact that the clearly verbal clear()
> has a side effect that isEmpty() =3D=3D true.
Is it really so clear that clear() can only be verbal?
;)
-- Niklas Matthies
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Matthew Austern <austern@research.att.com>
Date: Mon, 11 Jun 2001 21:28:10 GMT Raw View
kanze@gabi-soft.de (James Kanze) writes:
> "Al Grant" <tnarga@arm.REVERSE-NAME.com> wrote in message news:<9e2k1k$f5f$1@cam-news1.cambridge.arm.com>...
> > "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> > news:3B046F36.8C234F99@wizard.net...
> > > Al Grant wrote:
> > > > If the default allocator is an empty class and the container
> > > > contains the allocator as a member (as in P.J. Plauger's STL)
> > > > then a container without an allocator would be smaller.
>
> > > Why? There's no need for a container to keep a copy of the the
> > > allocator.
>
> > I know, SGI's STL doesn't. But Plauger's does and there must be a
> > reason for that.
>
> I'm just guessing, but earlier drafts did require keeping a copy of
> the allocator (although possibly as a base class). It may be that
> Plauger's code dates from then, and that there have been more
> important improvements to make since then.
The standard says that an implementation "should" handle non-
equivalent allocators appropriately. This is normative encouragement.
That is: an implementation that doesn't do this is still conforming,
but an implementation that does is better than one that doesn't.
The Dinkumware implementation does handle non-equivalent allocators,
and so do recent versions of the SGI implementation.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: remove.haberg@matematik.su.se (Hans Aberg)
Date: Mon, 11 Jun 2001 21:41:13 GMT Raw View
In article <d6651fb6.0106110625.e8259d6@posting.google.com>,
kanze@gabi-soft.de (James Kanze) wrote:
>> > (5) Fix the method naming conventions, especially the verb/noun
>> > confusions.
>
>> Some of the member names are _adjectives_. I don't see a verb/noun
>> confusion.
>
>Which is, perhaps, a problem in itself. There is also the problem
>that some English words can be both adjectives and verbs. So empty()
>can be a shorthand for isEmpty(), or can be an imperitive verb,
>forcing the container to be empty.
>
>> > For example, is_empty() and set_empty() instead clear() and
>> > empty().
>
>> Please don't. Especially "set_empty" sounds as wrong as it can (it's
>> like allowing "c.size() = 0"): "set" implies setting a variable, at
>> least logically.
>
>I like the rule that all function names are verbs or verbal phrases.
>According to this, however, empty() must be the active verb, isEmpty()
>would be the function to access the state.
I think that will have to accept a certain degree of ambiguity here:
In math, symbols are from the beginning just linguistic shorthand. But as
a matter of practise, symbols are given names just enough for the context
to be understandable.
For example, the math symbol "=" might be called "equal" or "equal to",
but the math expression
if x = y, then ...
would be read as "if x _is_ equal to y, then ...". Thus, one reading a
formula into words, one will have to insert some obvious words.
So it is not necessarily so that more words into a name makes its usage
any simpler.
An analogue in C++ might be
list<A> ls;
...
if (ls.empty()) ...
Here, one will have insert the words "is", just as in math, in order to
arrive at the formulation "if ls is empty ...".
The main difference between programming and math is of course causality:
In math, logical entities just exist, whereas in a computer program,
things can be made to happen.
So one might try to work along the lines to catch this causality.
In linguistics, there are causative forms, for example the causative form
of the word "dark" is "darken", meaning "cause to be dark".
So with the example empty() above, the both forms (causative or not)
happen to coincide in English. The question is if one should bother to
capture this difference or not, and if one should do that, how should it
be done.
One method that comes to my mind is that the forms that are not causative
will be pure. So one can think of adding a word "pure" to C++ on functions
that are considered to be pure. In C++ this would apply to functions whose
all arguments are either const or by value, and which does not manipulate
any external state to the function. To the compiler it would mean that it
is allowed to rearrange the computational order in an optimization as if
pure.
Thus,
template<class T>
class list<T> {
public:
bool empty() const pure; // Pure version: checks for current state.
list<T>& empty(); // Causative version: causes to be empty.
};
Or something.
Hans Aberg * Anti-spam: remove "remove." from email address.
* Email: Hans Aberg <remove.haberg@member.ams.org>
* Home Page: <http://www.matematik.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: James Dennett <jdennett@acm.org>
Date: Mon, 11 Jun 2001 21:47:28 GMT Raw View
James Kanze wrote:
>
> rogero@howzatt.demon.co.uk wrote in message
> news:<9dvtnk$ehk$1@news.netmar.com>...
[snip]
> > I'd prefer having a standard way of selecting a
> > checking/non-checking version of the library (or of some
> > components?).
>
> The real problem is that there is no way to get guaranteed
> non-range-checked access. The current situation allows range checking
> for operator[], and there would be no problem in requiring this in the
> standard. But we need a guaranteed non-range-checked access for the
> rare occasions when it does become a bottleneck. (I propose an
> additional function unsafe_at. Which makes it very clear what is
> going on.)
The Standard doesn't even guarantee unchecked access for "raw"
arrays; access out-of-bounds gives undefined behaviour, so range
checking is allowed, and for in-bounds access the only effect of
range checking is slower performance (by a roughly constant factor)
and the Standard is not in the business of mandating performance
except in terms such as big-O.
Would you want unsafe_at for raw arrays too?
-- James Dennett
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: James Dennett <jdennett@acm.org>
Date: Mon, 11 Jun 2001 22:52:46 GMT Raw View
James Kanze wrote:
>
> "Dean Roddey" <droddey@charmedquark.com> wrote in message news:<3KIN6.282$BM1.249883@news.pacbell.net>...
>
> > > > (4) Separate string into mutable and immutable forms. Immutable
> > > > strings support efficient copying; they can share parts of their
> > > > representation without bothering with copy-on-write. Mutable
> > > > strings support efficient editing. They don't need to be
> > > > sharable.
>
> > I think that Java has proven that this is a false economy, and in
> > fact one of the biggest performance pigs in the Java world that a
> > lot of work has to be done to get around. Perhaps it could be
> > implemented a bit more intelligently, but otherwise I'd say its a
> > loss overall except in very specific circumstances (which are the
> > ones always used to argue for them.)
>
> I'd rather say that Java has proven that this is the way to go.
The Java design seems to be sound (at least, the basic idea of
having a StringBuffer separate from String) even if Sun's
implementation of it is absolutely awful.
-- James Dennett
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: dietmar_kuehl@yahoo.com (Dietmar Kuehl)
Date: Tue, 12 Jun 2001 19:11:32 GMT Raw View
Hi,
kanze@gabi-soft.de (James Kanze) wrote:
> > The STL is not STL-like enough!
>
> I doubt that you can change the basic idiom.
That's not what I'm really aiming at... It is more cleaning up underneath.
For starters, rather than using 'operator*()' I want to use property maps
for the implementation of algorithms. If there are no property maps used,
a default property map is used which just uses 'operator*()'. That is,
everything you have just works as before. But if you want to use eg. a
proxy container, the algorithms would still work because the distinguish
cleanly between reading and writing. There are other uses of property maps,
too, eg. selecting only a part of the actual type like the 'second' component
of a pair (see the thread on the map interface for an implementation of
'for_each()' using property maps for this purpose).
> The question in my mind isn't whether we could invent something better
> than STL; I'm sure we could. The question is whether it would be
> worth it. The STL won't go away. It can't.
I don't want to replace the STL. Actually, I just want a more precise
specification of how the STL is implemented which would expose an interface
underneath more or less as a side effect. Before I hear all those library
writers complaining about taking away chances for optimization: Nope, no plan
do anything like this! Basically, the plan is to explicitly say whether a
property is assigned or read and, en passent, also say which property,
allowing also other than just the default property, ie. 'operator*()'.
> So are the improvements we could
> make by creating a second library sufficient enough to justify having
> to learn two libraries?
There would still be just one library. The difference is that the current
concepts are split into finer grained entities, at least for those wanting
to look at them this way: The actual algorithms would use a separation between
position (iterator) and access (property map) while another interface just
lumps these orthogonal pieces into just one concept (the current iterator).
That is, rather than having to learn about two libraries, you would have one
library from which you can just ignore a part until you need a feature from it
in which case you learn a little bit more, just another small concept, and
get more flexibility.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Steven E. Harris" <seh@speakeasy.org>
Date: Tue, 12 Jun 2001 21:13:09 GMT Raw View
kanze@gabi-soft.de (James Kanze) writes:
> On the other hand, the two iterator idiom makes it unnecessarily
> difficult to define sequences that aren't based on a container.
I've found that while it's a little awkward, you can solve this
problem by including an extra boolean or state flag in each iterator
to indicate if it's at "the end," or if it's "done"
iterating. Default-constructed iterators get this flag set to true,
and any other iterator must be guaranteed to eventually get this flag
set to true through successive iteration. Of course, this approach is
just a rip-off of std::istream_iterator. It worked fine, for example,
for exposing instances constructed from rows of a cursor-managed
database query ("query as container" idiom).
--
Steven E. Harris :: seh@speakeasy.org
GnuPG :: 0x70248E67
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Tue, 12 Jun 2001 21:13:25 GMT Raw View
Matthew Austern wrote:
>
> kanze@gabi-soft.de (James Kanze) writes:
>
> > "Al Grant" <tnarga@arm.REVERSE-NAME.com> wrote in message news:<9e2k1k$f5f$1@cam-news1.cambridge.arm.com>...
> > > "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> > > news:3B046F36.8C234F99@wizard.net...
> > > > Al Grant wrote:
> > > > > If the default allocator is an empty class and the container
> > > > > contains the allocator as a member (as in P.J. Plauger's STL)
> > > > > then a container without an allocator would be smaller.
...
> The standard says that an implementation "should" handle non-
> equivalent allocators appropriately. This is normative encouragement.
> That is: an implementation that doesn't do this is still conforming,
> but an implementation that does is better than one that doesn't.
However, std::allocator<T> is known to not have inequivalent instances,
so even if a container generally keeps a copy, it should be partially
specialized, if necessary, to not waste space doing so in the case when
the default allocator is used. After all, the default allocator is by
far the most frequently used one; the specialization is well worth
whatever extra effort is needed.
Of course, this isn't particularly difficult - with a decent compiler
deriving the container class from the allocator class will result in
empty allocators taking up no extra space.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 16:25:10 GMT Raw View
brangdon@cix.co.uk (Dave Harris) wrote in message news:<memo.20010516142615.38693D@brangdon.madasafish.com>...
> daniel.frey@aixigo.de (Daniel Frey) wrote (abridged):
> > For large applications, allocators are a holy gift and a good
> > argument for the STL, as the allow you to rapidly create an
> > application and optimize it when needed.
> OK... what do you use them for? My understanding is that allocators
> were introduced for the sake of 16-bit Intel platforms with
> segment-based pointers. Microsoft added some keywords to their
> dialect of C++ to make that stuff easier, too. Since we didn't add
> __based to standard C++, I don't see why we should have added
> allocators.
This is my understanding as well, but I wasn't active in the library
group at the time, so I really can't be sure.
I do think that after they had been initially adopted, there was some
reflection on the issue. The 16-bit various pointer type problem was
recognized as no longer very important, but there were suggestions
that they could be used for managing things like shared memory.
Again, however, I don't know the exact details, and would be quite
happy to loose them.
> > I bet people will start to use immutable strings as parameters
> > whereever possible but as soon as you have a mutable string and
> > pass it to a function taking an immutable string, it will be
> > copied.
> I would have no implicit conversion from mutable to immutable. The
> conversion would be explicit, and would come in two forms. The first
> form would be a copy that left the source unchanged.
> The second form would transfer ownership of the underlying memory
> buffer. This would leave the source in an "empty" state. It should
> be possible to implement this in O(1) time, without any copying or
> memory allocation.
Two references from actual implementations:
- The Java String/StringBuffer uses a copy on write implementation;
when a String is created from a StringBuffer, the String acquires
the underlying memory, and sets a flag in StringBuffer. The next
write operation on the StringBuffer causes a reallocation and a
copy.
- My own StringBuilder class didn't allow modification within the
string; only extention through appending to the end. In practice,
at least in my code, this turned out to be largely sufficient.
Internally, StringBuilder maintained its data as a String and a
fixed array; when converted to a String, it first appended the
data in the fixed array, then just returned the String.
Copying was in practice limited because my String class used copy
on write. And because in my own work, practically all of the
strings built were smaller than the fixed buffer of
StringBuilder. I'm not sure that this is appropriate for
something standard. It definitly doesn't scale; it has O(n^2)
complexity, intentionally, in order to obtain a very small
constant factor for smaller strings. (Only one allocation in all
when building a String smaller than the fixed buffer size.)
I do believe that there should be two (or more) separate classes. One
for immutable values, and other(s) to create such values optimally.
In my case, the only situation I had where construction was a
performance problem was building up a string (normally a line of text)
character by character; my StringBuffer was optimized for this. I'm
not sure what the correct general solution should be.
Note that my classes were designed back in the days of pure ASCII
text. Judging from the little bit of JSP I've been doing lately,
there is a significant class of modern applications which built up
entire HTML pages as a String. On the other hand, perhaps the
"correct" solution for both this and what I was doing would be an
optimized ostringstream, and we don't need any additional class.
(For those who haven't realized it: I'm not yet to the point of
advocating one solution or the other. I'm just thinking out loud.)
> > Or you have to write all those functions twice, once for mutable
> > strings and once for immutable ones.
> I wouldn't do that. The idea is for one part of the code to build up
> a string using the mutating operations. As its final step, it
> converts to an immutable string for use by the rest of the code.
This corresponds to the way I usually use strings.
In practice, I'm not sure that there can be such a thing as a single
efficient string class. There are too many requirements. I'm not
extremely happy with the standard string class, but it handles most
everyday chores adequately. And I wonder if any string class which
handled some particular job efficiently would not be worse for other
jobs. Do we want to standardize a string class which could be
efficiently used as the buffer for an editor for example, or is it
better just to offer something adequate for everyday work, and say
that anyone doing intensive string handling should write their own,
optimized for what they are doing?
> > All in all this will lead to a lot of trouble and IMHO this isn't
> > justified by the benefits.
> Efficient and expressive string handling is important. C++ is
> currently rather weak in this area. Eg see the problems implementing
> "copy on write".
> > I personally dislike this naming convention. If you really want to
> > change the names to match, why not overload them?
> > const size_t capacity() const;
> > void capacity( const size_t newCapacity );
> Ah, well. These functions do very different things. One changes the
> state of the object, the other merely returns a result. They are not
> in any way polymorphically substitutable for each other. They are
> different. We should be able to tell what a function does from its
> name. Functions that do different things should have different
> names.
I agree in principle, but the above idiom is pretty well entrenched,
and seems to work well in practice.
> In particular, functions that change the state of objects should
> have "set" in their name, or otherwise make it clear what they are
> doing.
Please, let's not have get... and set...
> Your general rule, that we can tell what they are doing merely from
> counting the number of arguments, is not good. Eg:
> class Table {
> int entries[10];
> public:
> int entry( int i ) { return entries[i]; }
> void set_entry( int i, int e ) { entries[i] = e; }
>
> // Use default of 0 if the index is not specified.
> int entry() const { return entries[0]; }
> void set_entry( int e ) { entries[0] = e; }
> };
> This class would become most unclear if we replaced set_entry with
> entry. It would be unclear even if we didn't use 0 as a default
> index.
> Still, I appreciate this is the kind of semi-religious argument that
> the standards committee wanted to avoid. My feeling is that names
> matter, and that some names have objective benefits over others, and
> it is important for the standard to exhibit good style. So I think
> it is worth at least a little bit of argument.
Good style went out the window the day they opted for C compatibility.
> > > Likewise std::map would become stl::red_black_tree_map.
> > The name should tell me how I can _use_ a container, not how it is
> > implemented.
> I sort-of agree, but the STL does imply a lot about how containers
> are implemented.
> Here's the problem. The thing that I call a "map", or "dictionary",
> or "associative array", can be implemented in many ways, eg:
> (1) As a balanced tree, eg a red-black tree.
> (2) As a hash-table.
> (3) As a sorted array, using binary-search for lookup.
> All three of these should probably be in the standard library, and
> we should be able to switch between them easily. They should have
> the same general interface, at least in terms of function
> signatures. Of course, operations will vary in complexity between
> them. Eg lookup is O(1) on average for the hash-table and O(log N)
> for the tree and sorted array.
> So we need names that convey, not just a set of function signatures,
> but the set of complexities. And in my view, "map" doesn't do
> that. "Map" fails to distinguish between the 3 implementations.
> I accept that "red_black_tree_map" may convey a bit more than we
> really want. It should be read as specifying, not a red-black tree,
> but anything with the same complexities as a red-black
> tree. Red-black tree is merely a typical implementation, an
> exemplar. (That said, I don't believe it is possible to implement a
> conforming std::map with anything other than a red-black tree.)
> Anyway, I think "red_black_tree_map" is an improvement over
> "map". Do you have another suggestion? The problem is that how the
> container is used should include what complexity guarantees its
> users may rely on, and a congeries of complexities is a difficult
> thing to name well.
The name should be map. However, it should take an additional
template parameter to specify the implementation: balanced tree,
sorted array or hash table.
Globally, I think that all of the initial suggestions are nice. I'm
less convinced that they are worthwhile. The current library is far
from perfect, and there are things I would have done differently. But
the key is "would have done"; in general, they aren't so important as
to make the library significantly less useful.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Mon, 11 Jun 2001 17:03:15 GMT Raw View
On Fri, 8 Jun 2001 23:31:09 GMT, Dietmar Kuehl
<dietmar_kuehl@yahoo.com> wrote:
> John Potter wrote:
> > Let's narrow the discussion to binary search in the form
> > of lower_bound algorithm and a binary search tree data structure,
> > including rotation.
> I'm not sure what you are refering to because 'lower_bound()' will not
> use any rotation. The accessed data structure might do some rotations
> internally but this is actually transparent to the 'lower_bound()'
> algorithm.
Lower_bound is the reason for the existence of the binary search tree.
You have claimed, and I agree, that rotation is a fundamental operation
on a binary search tree. Yes, it will be used by insert and erase not
lower_bound. I claim that a binary search tree is a node based data
structure and algorithms which operate on it are specific to it. You
claim that a binary search tree is an abstraction and that the
algorithms will work regardless of the data structure. Taking only
lower_bound and rotate_left, we should be able to decide whether
either of these claims is correct.
> 'lower_bound()' is entirely implemented in terms of obtaining
> a value from an iterator, applying a binary predicate, checking whether
> there is a left or right child, and moving to the left or right child.
> Something like this:
> template <typename TreeIt, typename Value, typename Pred>
> TreeIt lower_bound(TreeIt root, Value const& val, Pred pred) {
> while (true)
> if (pred(val, *root))
> if (root.has_left_child())
> root.move_left();
> else
> return root;
> else if (pred(*root, val) && root.has_right_child())
> root.move_right();
> else
> return root;
> }
> This code is untested and might contain errors (since untested code is
> wrong, it will contain errors :-) To use this algorithm, a tree iterator
> is required which has the following operations
I think there is a fundamental problem with the concept which must be
fixed before any correct code can be written. The algorithm does not
work for an empty tree nor is there an answer when the target is
greater than all values in the tree. We need the concept of an iterator
to an empty tree. In keeping with the below, add a member has_value.
To solve the other problem, the too big answer must be supplied to the
algorithm.
template <typename TreeIt, typename Value, typename Pred>
TreeIt lower_bound(TreeIt root, TreeIt answer, Value const& val,
Pred pred) {
while (root.has_value())
if (pred(*root, val))
root.move_right();
else {
answer = root;
root.move_left();
}
return answer;
}
This code is untested, but correctness is obvious. It could be done
using the has_x functions possibly adding some efficiency with the cost
of added complexity.
We can even add a new iterator_category tree_iterator_tag and compile
time dispatch on it. Of course, this is a lie. Unlike the other
compile time dispatches, we have too totally different algorithms on
different abstractions which are not interchangable. In the standard
library, the algorithm is written to work with forward iterators and
the specializations of distance and advance produce a more efficient
version for random access iterators which are forward iterators.
> *it the value stored in this node
> it.has_left_child() tests whether the node has a left child
> it.has_right_child() tests whether the node has a right child
> it.move_left() moves to the left child (pre: has_left_child())
> it.move_right() moves to the right child (pre:
> has_right_child())
Add it.has_value() and that becomes the pre for all others.
> Here are a few data structures and their corresponding iterators (I'm
> concentrating only on the relevant part and I assume you can picture
> how the corresponding ctors, access functions, etc. might look like):
>
> - The textbook tree:
> struct node { T value; node* left; node* right; };
> struct iterator {
bool has_value() { return n; }
> T& value() { return n->value; }
> bool has_left_child() { return n->left; }
> bool has_right_child() { return n->right; }
> iterator& move_left() { return n = n->left; return *this; }
> iterator& move_right() { return n = n->right; return *this; }
> node* n;
> };
Ignoring the first return in the two moves.
> - Array based tree 1: parent of node 'n' is at 'n / 2'
> struct iterator {
bool has_value() { return n < last; }
> T& value() { return base[n]; }
> bool has_left_child() { return 2 * n < last; }
> bool has_right_child() { return 2 * n + 1 < last; }
> iterator& move_left() { n = 2 * n; return *this; }
> iterator& move_right() { n = 2 * n + 1; return *this; }
> T* base; // or in general an iterator with value_type 'T'
> int n, last;
> };
Ok. Changing base to current and using advance in the two moves would
generalize this for list and slist also. A test to prevent going past
last also.
Insert/erase involves a complete reorganization and rotate does not
make any sense. Yes, an iterator can be created to make the tree
based lower_bound algorithm work, but I can't accept this as a
binary search tree. Just creating the original contents is a mess.
This tree in an array makes a nice heap, but not a binary search tree.
> - Array based tree 2: parent is between the left and right subtree
> (I'm a little bit vague about the details of the implementation)
> struct iterator {
bool has_value() { return len; }
> T& value() { return *first + len / 2; }
> bool has_left_child() { return len > 1; }
> bool has_right_child() { return len > 1; }
When there is only one child, it is left. return len > 2;
> iterator& move_left() { len = len / 2; return *this; }
> iterator& move_right() {
> first = first + len / 2 + 1; len / 2; return *this; }
> T* first; // or in general an iterator with value_type 'T'
> };
Ok. Using advance would generalize this. It could be made more
efficient for list by using current in place of first.
Insert/erase is no problem, but rotate makes no sense. I can't accept
this as a binary search tree either.
I think that you have proven your point that an iterator may be created
to make an inappropriate lower_bound algorithm work on data structures
for which it was not designed. I think you have also proven my point
that algorithms need to be created with the data structure to be of
value.
The purpose of a binary search tree is, well, binary search. There
are no other algorithms on binary search trees. Since insert and erase
are tied to the container they will never be algorithms. Given enough
tree based algorithms of general interest, there could be a use for this
stuff. Thanks for your patience.
> - Since rotations were mentioned: a splay tree
A splay tree is a binary search tree. Note that the rotations done
in your implementation do not produce the statistical properties of
a splay tree. The order in which two adjacent rotations are performed
is important to get the desired properties. Some other minor problems
not important to the discussion.
> Of course, the 'lower_bound()' given above works with
> this infinite tree, too. However, it might not terminate because there
> are no leaf nodes. It only terminates when the value is found (which
> can, however, mean that predicate is not simply 'std::less<>()' but
> something taking an epsilon into account).
Not a problem, lower_bound always finds something. I think you are
talking about the bisection root finder.
struct iterator {
bool has_value() { return len > 0; }
double value() { return f(base()); }
bool has_left_child() { return base() != left; }
bool has_right_child() { return base() != base() + len / 2; }
iterator& move_left() { len /= 2; return *this; }
iterator& move_right() { left = base(); len /= 2; return *this; }
double base() { return left + len / 2; }
double left, len;
double(*f)(double);
};
For squareroot, f is x * x, val is the number, left is zero, and len is
max(1, val). There are better starting points and an epsilon could also
be used. Like all iterator adaptors, there is a base function to get
the adapted iterator. I see no way to make the sequence based
lower_bound in the library work for this.
In all of these cases, an iterator was created for the sole purpose of
performing a binary search. In each case, less code is required to
write the algorithm for the data structure. I maintain that a binary
search tree is a data structure and lower_bound is an algorithm which
is best implemented for each abstraction. One algorithm for sequences
worked, but it failed for associatives.
The tree iterator is interesting, but I wonder if it is really useful
for algorithms on trees. The rotate algorithm can't be used with trees
which maintain a balance data member. I guess a policy object would
solve that problem. There just do not seem to be that many general
algorithms on trees.
Thinking about it, many of the algorithms in the STL are used by sort.
Maybe they are not that interesting in themselves and that could
explain the general lack of interest in the algorithms by most 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.research.att.com/~austern/csc/faq.html ]
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 17:39:59 GMT Raw View
Peter Dimov <pdimov@MailAndNews.com> wrote in message
news:<3B0EF5C1@MailAndNews.com>...
> >(3) Add reified sequences. Drop the implicit 2-iterator convention.
> There's no proof of concept that this will work.
Sure there is: all of the other libraries that use it, and work as
well or better than the standard library.
On the other hand, the standard library seems to work well enough. Is
it worth having to learn two libraries just to get the somewhat
limited added benefits?
> >(5) Fix the method naming conventions, especially the verb/noun
> >confusions. For example, is_empty() and set_empty() instead clear() and
> >empty(). Set_capacity() and capacity() instead of reserve() and
> >capacity().
> Note that 'reserve' doesn't set the capacity.
No. The function should be called something like guaranteeCapacity.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 17:40:30 GMT Raw View
"Dean Roddey" <droddey@charmedquark.com> wrote in message news:<3KIN6.282$BM1.249883@news.pacbell.net>...
> > > (4) Separate string into mutable and immutable forms. Immutable
> > > strings support efficient copying; they can share parts of their
> > > representation without bothering with copy-on-write. Mutable
> > > strings support efficient editing. They don't need to be
> > > sharable.
> I think that Java has proven that this is a false economy, and in
> fact one of the biggest performance pigs in the Java world that a
> lot of work has to be done to get around. Perhaps it could be
> implemented a bit more intelligently, but otherwise I'd say its a
> loss overall except in very specific circumstances (which are the
> ones always used to argue for them.)
I'd rather say that Java has proven that this is the way to go. In
practice, you are either constructing a string, or you are passing it
around. Logically, one class can't be optimized for both.
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 17:40:50 GMT Raw View
kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl) wrote in message news:<9e1u6a$2bi$2@news.BelWue.DE>...
> Dave Harris (brangdon@cix.co.uk) wrote:
> > Suppose we were designing a template library from scratch, without
> > much concern for backwards compatibility. Suppose it was going in
> > a new namespace, say stl:: instead of std::. What would we do
> > differently?
I agree with the thrust of your comments, however...
> Whatever you consider, note that it is at the wrong level:
> Containers are the least important entities! Consider the standard
> containers as examples which might be a nice aid and even handy for
> some uses. If they aren't, just create your own container. That is
> the core idea of the whole stuff: If you want a new container, just
> create one and only consider the containment aspect of the
> container. This is made up of the capability to store and access the
> elements.
I appreciate the point you are making, but the containers are more
than that. Sure, I can write my own. I did, before there was a
standard. But I appreciate having the standard ones. It's less work
for me, and even more important, it means that a new programmer coming
on the project doesn't have to learn my custom containers (supposing
that he does know standard C++).
> What is more interesting is the concept of iterators: These are the
> entities whose interface is important to the standard library. The
> actual interface of the containers is more or less unimportant
> except, may be, for consistency sake. The interface of the iterators
> is important. Why is that?
The iterators are the key, I agree. But I think that part of his
motivation for a new library was changing the principles behind the
iterators.
(But as I said, I agree with most of what you said.)
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 18:27:00 GMT Raw View
Matthew Austern <austern@research.att.com> wrote in message news:<dilofsr97aj.fsf@isolde.research.att.com>...
> "Al Grant" <tnarga@arm.REVERSE-NAME.com> writes:
> > > And what method would the one defined without an allocator use
> > > to allocate and deallocate needed memory? If it uses 'new' and
> > > 'delete', how would such a container differ from
> > > Container<T,std::allocator<T> >, which is precisely what
> > > Container<T> defaults to?
> > If the default allocator is an empty class and the container
> > contains the allocator as a member (as in P.J. Plauger's STL) then
> > a container without an allocator would be smaller.
> But there are well known techniques for writing containers so that
> the default allocator doesn't take up space. (I don't think I
> should discuss those techniques here, because they're not really
> related to C++ standardization.) Allocators are unquestionably more
> work for implementors, but, if well implemented, I don't think they
> hurt users.
Except indirectly. Implementors have finite resources. The time they
spend getting allocators right, and then getting them to have 0 cost,
is time that they aren't spending doing other things I might want
(like a debug version of the library).
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 18:27:55 GMT Raw View
Christopher Eltschka <celtschk@dollywood.itp.tuwien.ac.at> wrote in
message news:<3B02A30D.C44ED3B4@dollywood.itp.tuwien.ac.at>...
> Dave Harris wrote:
[...]
> > (5) Fix the method naming conventions, especially the verb/noun
> > confusions.
> Some of the member names are _adjectives_. I don't see a verb/noun
> confusion.
Which is, perhaps, a problem in itself. There is also the problem
that some English words can be both adjectives and verbs. So empty()
can be a shorthand for isEmpty(), or can be an imperitive verb,
forcing the container to be empty.
> > For example, is_empty() and set_empty() instead clear() and
> > empty().
> Please don't. Especially "set_empty" sounds as wrong as it can (it's
> like allowing "c.size() = 0"): "set" implies setting a variable, at
> least logically.
I like the rule that all function names are verbs or verbal phrases.
According to this, however, empty() must be the active verb, isEmpty()
would be the function to access the state. And of course, setEmpty()
really wouldn't mean anything. In this particular case, however, I
don't have any problem with the fact that the clearly verbal clear()
has a side effect that isEmpty() == true.
> > Set_capacity() and capacity() instead of reserve() and capacity().
> No again. reserve() doesn't _set_ the capacity. set_capacity()
> would only appropriate if after the call we would have a guarantee
> that capacity() returns the value we supplied. But indeed, reserve
> only _increases_ the memory, i.e. reserves(!) memory for more
> elements.
The problem is the reserve is a transitive verb. Just calling the
function reserve is horribly ambiguous. What about reserveCapacity
(or guaranteeCapacity, or ensureCapacity)?
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 18:27:44 GMT Raw View
rogero@howzatt.demon.co.uk wrote in message
news:<9dvtnk$ehk$1@news.netmar.com>...
> In article <memo.20010515105511.43417C@brangdon.madasafish.com>, Dave Harris
> <brangdon@cix.co.uk> writes:
> >Suppose we were designing a template library from scratch, without
> >much concern for backwards compatibility.
> I'm sorry, I think it is too late for this! I wouldn't want C++ to
> go the way of "the various flavours of Unix".
I think that it is very useful to increase understanding to discuss
what could have been different, whether it would have better or not,
and why. The only problem I have is that this thread is apparently
derived from one discussing C++0x. And arguments to replace or add to
the standard library are a different question.
There are a number of things I'd have probably done different in the
standard library. (I was one of the first, I think, to question the
two iterator idiom.) But whatever its warts, it does work. So we
have to consider:
- Do we want to change the current library? My personal answer to
this is "over my dead body", at least with regards to incompatible
changes. Like most people here, I'm already using the existing
library. I've got enough problems without people coming along and
breaking all of my working code.
- Do we want to add an new library, probably in a different
namespace, with similar functionality to the old? I'm very
hesitant about this as well. It's already hard enough learning
all of the algorithms, all of the various restrictions on
iterators, etc. Adding a new library would just add to what I
have to know.
This is probably true for the first point as well, since
regardless of what the standard does, implementors will continue
to support existing code in their clients. I know that currently,
I have to "know" two iostream, because I have to deal with two
different "standards". At least the two iostream are very
similar; I can generally get by by knowing the standard iostream
and the deltas. I'd hate to have to learn twice as many classes
just to understand C++. (Unless, of course, the new classes gave
me some real new functionality, like a GUI, threading, etc.)
> What I want is a graceful way to migrate from where we are to where
> we would like to be. Something like the @deprecated keyword from
> Java for example - some way to mark methods/classes where a newer,
> improved, replacement was available but still providing a window of
> time in which the old method is available.
Have you ever actually used @deprecated in Java:-). It's more an
additional source of problems than anything else.
[...]
> >(4) Separate string into mutable and immutable forms.
> Yes please!! This is the one I feel we need most.
Since my own pre-standard String classes were designed like this, it's
obviously the one correct solution:-).
Seriously: before touching anything, let's decide what the goal of the
change is to be. There are a lot of things I don't particularly like
about the current string class, but it works. Before accepting an
alternative, you're going to have to show me why it is necessary to
break my working code, or for me to learn two string classes instead
of one. Unless there is a very high pay-off, it sounds like a lot of
extra work just to be politically correct.
[...]
> >(7) Make vector and string range-checked by default.
> I'd prefer having a standard way of selecting a
> checking/non-checking version of the library (or of some
> components?).
The real problem is that there is no way to get guaranteed
non-range-checked access. The current situation allows range checking
for operator[], and there would be no problem in requiring this in the
standard. But we need a guaranteed non-range-checked access for the
rare occasions when it does become a bottleneck. (I propose an
additional function unsafe_at. Which makes it very clear what is
going on.)
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kanze@gabi-soft.de (James Kanze)
Date: Mon, 11 Jun 2001 20:50:16 GMT Raw View
Dietmar Kuehl <dietmar_kuehl@yahoo.com> wrote in message news:<3B081B7A.3AE47F24@yahoo.com>...
> John Potter wrote:
> > I don't think so. Your generic algorithms do not work. See below.
> Hm, looks like you are in bad mood due to some problem or you are
> playing devils advocate... Anyway, here we go:
> > > In the context of an application, you are probably manipulating
> > > containers using algorithms for this. Although the containers
> > > are useful as packaged, you might want to use slightly modified
> > > containers providing additional capabilities. The key here is
> > > that you can just create them eg. by using one of the existing
> > > containers and providing a thin wrapper or by hacking up a new
> > > one.
> > Nope. Your containers have algorithms which are useless without
> > the container.
> Sure, the algorithms need a sequence (or whatever the underlying
> structure is) to work on. The point is, however, that you can easily
> create new containers and the algorithms ready operate on the new
> containers.
On the other hand, the two iterator idiom makes it unnecessarily
difficult to define sequences that aren't based on a container.
[...]
> No doubt, the STL is not at all perfect but many of the things which
> are wrong can be corrected. Actually, I think Valentines comment is
> right to the point: The STL is not STL-like enough!
I doubt that you can change the basic idiom.
The question in my mind isn't whether we could invent something better
than STL; I'm sure we could. The question is whether it would be
worth it. The STL won't go away. It can't. (To begin with, I've got
too much code which depends on it, and I'm very definitly against
anything which would break my code.) So are the improvements we could
make by creating a second library sufficient enough to justify having
to learn two libraries?
--
James Kanze mailto:kanze@gabi-soft.de
Conseils en informatique orient e objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelh ttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Matthew Austern <austern@research.att.com>
Date: Tue, 12 Jun 2001 21:49:19 GMT Raw View
"James Kuyper Jr." <kuyper@wizard.net> writes:
> Matthew Austern wrote:
> >
> > kanze@gabi-soft.de (James Kanze) writes:
> >
> > > "Al Grant" <tnarga@arm.REVERSE-NAME.com> wrote in message news:<9e2k1k$f5f$1@cam-news1.cambridge.arm.com>...
> > > > "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> > > > news:3B046F36.8C234F99@wizard.net...
> > > > > Al Grant wrote:
> > > > > > If the default allocator is an empty class and the container
> > > > > > contains the allocator as a member (as in P.J. Plauger's STL)
> > > > > > then a container without an allocator would be smaller.
> ...
> > The standard says that an implementation "should" handle non-
> > equivalent allocators appropriately. This is normative encouragement.
> > That is: an implementation that doesn't do this is still conforming,
> > but an implementation that does is better than one that doesn't.
>
> However, std::allocator<T> is known to not have inequivalent instances,
> so even if a container generally keeps a copy, it should be partially
> specialized, if necessary, to not waste space doing so in the case when
> the default allocator is used. After all, the default allocator is by
> far the most frequently used one; the specialization is well worth
> whatever extra effort is needed.
Oh, of course. Implementors ought to use a technique that will keep
instances of allocators without data members from taking up space.
Partial specialization on std::allocator<> is one technique of doing
that. There are also a number of techniques that rely on the empty-
base-class optimization.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Pete Becker <petebecker@acm.org>
Date: Tue, 12 Jun 2001 22:42:42 GMT Raw View
Matthew Austern wrote:
>
> Oh, of course. Implementors ought to use a technique that will keep
> instances of allocators without data members from taking up space.
> Partial specialization on std::allocator<> is one technique of doing
> that. There are also a number of techniques that rely on the empty-
> base-class optimization.
>
All this depends, of course, on having a compiler that handles these
advance language constructs correctly. Unfortunately, library
implementors must live in the real world, where compilers are imperfect.
--
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.research.att.com/~austern/csc/faq.html ]
Author: Dietmar Kuehl <dietmar_kuehl@yahoo.com>
Date: Fri, 8 Jun 2001 23:31:09 GMT Raw View
John Potter wrote:
> > Don't mix representation with abstraction!
>
> To quote Worth (calling him by value :) "algorithms + data structures
> == programs". Abstracting one away at the cost of the other produces
> garbage.
I'm not abstracting anything away at all! What I'm doing is abstracting
one, moving from the concrete representation to a conceptual view
accessed through appropriate functions. The data structure is still
there but not manipulated directly by the algorithm. Instead, methods
for accessing the data structure are used by the algorithm.
> Let's narrow the discussion to binary search in the form
> of lower_bound algorithm and a binary search tree data structure,
> including rotation.
I'm not sure what you are refering to because 'lower_bound()' will not
use any rotation. The accessed data structure might do some rotations
internally but this is actually transparent to the 'lower_bound()'
algorithm. 'lower_bound()' is entirely implemented in terms of obtaining
a value from an iterator, applying a binary predicate, checking whether
there is a left or right child, and moving to the left or right child.
Something like this:
template <typename TreeIt, typename Value, typename Pred>
TreeIt lower_bound(TreeIt root, Value const& val, Pred pred) {
while (true)
if (pred(val, *root))
if (root.has_left_child())
root.move_left();
else
return root;
else if (pred(*root, val) && root.has_right_child())
root.move_right();
else
return root;
}
This code is untested and might contain errors (since untested code is
wrong, it will contain errors :-) To use this algorithm, a tree iterator
is required which has the following operations
*it the value stored in this node
it.has_left_child() tests whether the node has a left child
it.has_right_child() tests whether the node has a right child
it.move_left() moves to the left child (pre: has_left_child())
it.move_right() moves to the right child (pre:
has_right_child())
Here are a few data structures and their corresponding iterators (I'm
concentrating only on the relevant part and I assume you can picture
how the corresponding ctors, access functions, etc. might look like):
- The textbook tree:
struct node { T value; node* left; node* right; };
struct iterator {
T& value() { return n->value; }
bool has_left_child() { return n->left; }
bool has_right_child() { return n->right; }
iterator& move_left() { return n = n->left; return *this; }
iterator& move_right() { return n = n->right; return *this; }
node* n;
};
- Array based tree 1: parent of node 'n' is at 'n / 2'
struct iterator {
T& value() { return base[n]; }
bool has_left_child() { return 2 * n < last; }
bool has_right_child() { return 2 * n + 1 < last; }
iterator& move_left() { n = 2 * n; return *this; }
iterator& move_right() { n = 2 * n + 1; return *this; }
T* base; // or in general an iterator with value_type 'T'
int n, last;
};
- Array based tree 2: parent is between the left and right subtree
(I'm a little bit vague about the details of the implementation)
struct iterator {
T& value() { return *first + len / 2; }
bool has_left_child() { return len > 1; }
bool has_right_child() { return len > 1; }
iterator& move_left() { len = len / 2; return *this; }
iterator& move_right() {
first = first + len / 2 + 1; len / 2; return *this; }
T* first; // or in general an iterator with value_type 'T'
};
- Since rotations were mentioned: a splay tree
struct node { T value; node* left; node* right; };
struct iterator {
T& value() { return n->value; }
bool has_left_child() { return left; }
bool has_right_child() { return right; }
iterator& move_left() { n = rotate_right(n); return *this; }
iterator& move_right() { n = rotate_left(n); return *this; }
void set_left(iterator it) { n->left = it.n; }
void set_right(iterator it) { n->right = it.n; }
node* n;
};
where 'rotate_right()' is implemented like this (making use of
additional tree iterator members which are not used by
'lower_bound()'):
template <typename TreeIt>
TreeIt rotate_right(TreeIt node) {
TreeIt rc(node);
rc.move_left();
node.set_left(TreeIt(rc).move_right());
rc.set_right(node);
return rc;
}
'rotate_left()' is implemented correspondingly.
> Can you show me the lower_bound algorithm which works on all three of
> these binary search trees? I don't want to see rotate_left for the
> two array forms, much less find it in any code used by a standard
> container.
I don't understand the last restriction on not using 'rotate_left()':
Clearly something like a red/black tree would use such rotation,
although
not when searching. Splay trees use these operations when traversing the
tree, that it, these operations are used implicitly be the algorithm
whenenver moving the iterator.
> That is a binary search algorithm on a different data structure. If you
> claim that it is a binary search tree, please show me rotate_left. Does
> your lower_bound from above work here?
I'm not claiming that all algorithms which can be applied to at least
one
tree data structure can be applied to all trees. Obviously, there are
immutuable trees to which only non-modifying algorithms can be applied.
'rotate_left()' is a modifying operation. It does not make sense to
apply 'rotate_left()' to an immutable tree. It does also not make any
sense to 'std::sort()' a 'std::set()' or 'std::random_shuffle()' an
input sequence. Of course, the 'lower_bound()' given above works with
this infinite tree, too. However, it might not terminate because there
are no leaf nodes. It only terminates when the value is found (which
can, however, mean that predicate is not simply 'std::less<>()' but
something taking an epsilon into account).
> Fine, but this is the binary search tree data structure. Of what use
> is an rb-tree, avl-tree, or splay-tree to an application programmer?
> All posts requesting an avl-tree have been satisfied by pointing out
> that the library contains associative containers. Nobody is interested
> in doing a tree walk based on a predicate. There is an interest in a
> find_if member of the associative containers.
I admit that I can't come up with an example which isn't effectively
a search algorithm. However, this doesn't mean that there are no
applications where these trees would be useful for something different
than search trees. But even if these data structures would only be
useful
to implement associative containers, I think it make sense to have them
available: There are enough design choices in encapsulating a tree into
an associative container that somebody will want a different trade off.
> I don't think so. None of these algorithms are of any use other than
> to create a binary search tree data structure to use in the
> implementation of useful application level containers for the library.
I actually agree with this: This stuff will almost certainly not make
it into the standard. A corresponding library might still be of use...
> That's nice. Have you been listening to all of the people telling you
> that they don't care about this stuff and are interested only in
> containers which do the required job?
If they don't care about this stuff, the don't care: They just use
the higher level interfaces, eg. the containers. However, just because
most people don't care, doesn't mean nobody cares and there is no harm
to people who don't care (well, if the committee would devote time to
standardize such stuff it would to harm because the time cannot be used
for other business; but, as I said above, it is indeed unlikely that
such stuff will make it into the standard).
> > Whether such abstractions make it into the standard is not at all clear
> > to me: This might be too much work for to few benefit. Still, I see
> > a place for tree abstractions and a corresponding library, eg. in the
> > context of the Boost library.
>
> Here we can agree. This stuff is cool (or Kuehl :) and useful. Maybe
> not worth being in the standard library.
At least something we can agree on :-)
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Thu, 7 Jun 2001 10:20:12 GMT Raw View
On Sat, 26 May 2001 18:16:05 GMT, Dietmar Kuehl
<dietmar_kuehl@yahoo.com> wrote:
> jpotter@falcon.lhup.edu (John Potter) wrote:
> > The real problem for me is tree. A tree may be a graph with structure
> > or it may be a simple data structure on a sequence. These are two
> > very different things.
>
> Don't mix representation with abstraction!
To quote Worth (calling him by value :) "algorithms + data structures
== programs". Abstracting one away at the cost of the other produces
garbage. Let's narrow the discussion to binary search in the form
of lower_bound algorithm and a binary search tree data structure,
including rotation.
> A sequence is a bad abstraction
> when operating on trees. Of course, an array can be seen as a fully
> balanced binary tree: Node 'int(n / 2)' is the parent of node 'n' and
> nodes '2 * n' and '2 * n + 1' are the children of node 'n' (this might
> contain an off-by-one error; the details are irrelevant here). However,
> eg. a search algorithm on a binary tree is probably best formulated in
> more abstract terms than this (ie. 'lower_bound()' is actually a tree
> algorithm which should be formulated as such!).
We can also consider a sorted array as a fully balanced binary tree
with the root at n / 2. Given n and pos we can find left, right and
parent.
Can you show me the lower_bound algorithm which works on all three of
these binary search trees? I don't want to see rotate_left for the
two array forms, much less find it in any code used by a standard
container.
> > A binary search tree has no interesting tree properties. It is a
> > container.
>
> A binary search tree is a container? Come on! Finding the root of a
> number given a start value can be seen as a binary tree: each node has
> the current value under investigation as value and whether you go left
> or right depends on whether it is too big or too small. The children of
> a single node are the current value plus/minus a suitable delta which
> is just split into halves on the next level. I forgot how this algorithm
> is called but it does not really matter. What matters is that there may
> be implicitly given binary search trees which can be investigated by
> suitable binary tree search algorithms! This example might be pretty
> useless but there are practical examples where eg. the path towards an
> element is of interest.
That is a binary search algorithm on a different data structure. If you
claim that it is a binary search tree, please show me rotate_left. Does
your lower_bound from above work here?
> > You see rebalance after add as a sequential algorithm
> > on a subsequence of the path to the root. Rotate is an algorithm
> > that operates on the nodes in this sequence. I see rotate as a
> > function that operates on a piece of a binary search tree. It is
> > not an algorithm on trees. You don't change the structure of a
> > tree.
>
> Maybe you are not changing the structure of the trees you are using
> but there may be other uses. I can imagine that some form of expression
> evaluator representing expressions as binary trees might very well
> change
> the structure of the tree, including rotations, to rewrite the original
> expression into an optimal form. ... and even if a rotation is only
> useful for binary search trees, the 'rotate()' function would be used in
> several different places, eg. the insertion and removal into an RB tree,
> an AVL tree, and whenever a splay tree is accessed. Why not provide it
> for the sake of at least these implementations and possibly other binary
> search tree implementations? Likewise for a tree walk algorithm which
> decides whether to go left or right on a given predicate.
Fine, but this is the binary search tree data structure. Of what use
is an rb-tree, avl-tree, or splay-tree to an application programmer?
All posts requesting an avl-tree have been satisfied by pointing out
that the library contains associative containers. Nobody is interested
in doing a tree walk based on a predicate. There is an interest in a
find_if member of the associative containers.
> > You may get some nice functional decomposition for operations which
> > are partially common to various forms of binary search tree. I don't
> > see any binary search tree algorithms for inclusion in the library.
>
> 'rotate()' (probably in several forms; this somewhat depends on the
> details of the interface design) and 'lower_bound()' (which actually
> *is*
> in the standard library: a tree algorithm without a tree abstraction!)
> are
> obvious candidates. 'find_leftmost_decendent()', 'find_root()' and
> 'depth()' are others. Probably it makes sense to provide insert
> operations
> using appropiate balancing mechanisms and so on. Whether these
> algorithms
> make it into the standard library or some add-on addressing tree
> specific
> stuff does not really matter: Binary trees are probably a reasonable
> abstraction on which a bunch of algorithms can be provided.
I don't think so. None of these algorithms are of any use other than
to create a binary search tree data structure to use in the
implementation of useful application level containers for the library.
> > The library has associative containers. I see them as wrappers of
> > a binary search tree container.
>
> That's just one use of binary search trees. Some form of encoding can
> also
> be done using binary search trees, providing the bit sequence according
> to the left/right choices needed to find an element.
Sure Huffman codes. A data structure, a binary tree which is not a
binary search tree to generate the codes which can also be used to
decode them. A container.
> The point is that
> it actually make life easier for the person creating eg. an associative
> container if corresponding lower level functions are available.
Yes! The implementer needs it. Does the standard library? Are any of
these algorithms on binary search tree data structures of general use?
> ... and it make the code more readable if functions like 'rotate()' are
> used rather than manipulating the pointers directly!
Agreed. But, when all is said and done, the library already has the
associative containers and nothing new is gained.
> I think that something like this allows implementation of most
> operations
> typically done on binary trees. Note, that this only defines access
> methods to the structure of the tree, not to any associated data. The
> tree algorithms don't care about the associated data, they are just
> interested in the structure. For some tree algorithms it is implicitly
> assumed that there is some data (eg. 'tree_find()') but there is no
> need to specify how this data is actually accessed.
That's nice. Have you been listening to all of the people telling you
that they don't care about this stuff and are interested only in
containers which do the required job?
> > Should the library provide these low level containers to match the
> > low level sequences or should it provide useful interfaces as it
> > now does?
>
> Fortunately "or" is inclusive: It is likely that both are provided :-)
Do you really think so? I have seen the hash containers and slist
mentioned as obvious additions to the library, but nothing about any
of this implementation detail stuff. In fact, there have been zero
suggestions for new algorithms.
> Whether such abstractions make it into the standard is not at all clear
> to me: This might be too much work for to few benefit. Still, I see
> a place for tree abstractions and a corresponding library, eg. in the
> context of the Boost library.
Here we can agree. This stuff is cool (or Kuehl :) and useful. Maybe
not worth being in the standard library.
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.research.att.com/~austern/csc/faq.html ]
Author: pdimov@mmltd.net (Peter Dimov)
Date: Tue, 29 May 2001 17:23:28 GMT Raw View
brangdon@cix.co.uk (Dave Harris) wrote in message news:<memo.20010528181304.65525D@brangdon.madasafish.com>...
> pdimov@mmltd.net (Peter Dimov) wrote (abridged):
> > When is the Containers level appropriate?
>
> When greater genericity is impossible, inconvenient, or otherwise not
> worth the effort. Sometimes it will make sense to start with a specific
> implementation and then generalise it later. Obviously these decisions
> may be made differently for applications developers and (non-std) library
> developers. Use your best judgement.
This is exactly the current status quo. Container-level algorithms are
member functions, because greater genericity is presumably not worth
the effort. :-)
--
Peter Dimov
Multi Media Ltd.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Tue, 29 May 2001 19:26:02 GMT Raw View
pdimov@mmltd.net (Peter Dimov) wrote (abridged):
> > > When is the Containers level appropriate?
> >
> > When greater genericity is impossible, inconvenient, or otherwise
> > not worth the effort. Sometimes it will make sense to start with a
> > specific implementation and then generalise it later.
>
> This is exactly the current status quo. Container-level algorithms are
> member functions, because greater genericity is presumably not worth
> the effort. :-)
They picked a syntax which failed to hide the decision, though. We cannot
switch to a more general implementation later without changing client
code. So that is not exactly what I am advocating at all.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Mon, 28 May 2001 22:59:54 GMT Raw View
pdimov@mmltd.net (Peter Dimov) wrote (abridged):
> When is the Containers level appropriate?
When greater genericity is impossible, inconvenient, or otherwise not
worth the effort. Sometimes it will make sense to start with a specific
implementation and then generalise it later. Obviously these decisions
may be made differently for applications developers and (non-std) library
developers. Use your best judgement.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Fri, 25 May 2001 10:41:25 GMT Raw View
pdimov@mmltd.net (Peter Dimov) wrote (abridged):
> I wondered how long will it take before we get to the A- word. :-)
It's not meant disparagingly. I do believe Stepanov and Lee's aims were
not exactly the aims we should have.
I think I've addressed your other points over in c.l.c++.m. Brief
summary: what I would actually advocate is 2 things:
(1) Open up the iterator category system, so that users can add new
iterator tags and specialise std algorithms upon them.
(2) Make sequences into explicit, single objects.
I suspect that explicit sequences would help deal with graph fragments
which are not represented well by iterator pairs.
> Again, hard work for whom? The user? The author of a new algorithm/new
> container? The Standard Library implementor?
The author of the new container or algorithm.
> Assuming that you don't use iterators as an abstraction layer, how are
> you going to manage the combinatorial explosion?
Work at whatever level is appropriate:
o Sequence categories.
o Sequences.
o Iterators.
o Containers.
At the container level I would deal with the combinatorial explosion by
only implementing the combinations I actually needed.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Fri, 25 May 2001 20:14:50 GMT Raw View
On Tue, 22 May 2001 20:29:21 GMT, dietmar_kuehl@yahoo.com (Dietmar
Kuehl) wrote:
> jpotter@falcon.lhup.edu (John Potter) wrote in message
> news:<3b09126a.14933584@news.csrlink.net>...
> > Neither, we are just not talking about the same thing.
> Apparently I didn't make my point as clear as it could have been... At
> least, your summary of what I'm talking does not really match what I'm
> saying and I'm indeed not that sure that we are talking about different
> things.
Maybe you are too general for me. At least we are learning something
and maybe others also.
> Basically, my position is that there is not much point to fiddle around
> with container details like whether container should be range checked,
> have allocators, std::vector<bool> being a specialization, etc. Neither
> is there much point to quibble much about the interface of the algorithm.
> When talking about a new STL it makes much more sense to discuss the
> foundation of STL rather than talking about the details of entities
> resulting from the details of the foundations.
I have no problem with that.
> That is, it is rather irrelevant to discuss whether a specific container
> should exhibit a certain access policy: If you want a container with
> specific policies, create one! There is a bunch of containers available
> as examples and to built upon in the standard library but these are not
> intended to solve everybodies problem. What the STL is about is making
> it viable for users to create their specific container which fits smoothly
> with other sequences.
I can agree with this, but I may not be reading what you are saying.
The STL provides basic low level sequence containers. Vector is an
array, deque is an argv, slist is a singly linked list, list is a
doubly linked list. These are sequence containers and we have about
exhausted the possibilities of sequence containers. It is trivial
to wrap them to present any of the different policies desired. I
agree with you there. Others want to play games with container
generators to get the desired policies. These are also building
blocks which can be used to create other abstractions. The algorithms
may be used to create these abstractions, but they will not be usable
on the resulting abstraction because it will no longer be a sequence.
> ... or, on the other side of the story, to create their functions which
> take arbitrary sequences fulfilling a minimum set of requirements as
> arguments. Note, that this is not at all just an academic goal:
> Different people in a project typically have different ideas with respect
> to what kind of container to use to store things in but it is common that
> you have to interface with them. Providing interfaces using iterators to
> specify sequences, whether as input or as output, provides a common basis.
Ok, sequence is the universal representation of information and makes an
interface for transfer of data from one place to another.
> A container for the same purpose does not suit well for at least two
> reasons:
>
> - If the container types don't match between components, it is necessary to
> copy them. Even if the containers are a generic arguments, this does not
> work out well because often it is necessary to change the view of each
> individual element, eg. by adding some data or selecting partial data. In
> fact, my view is that STL is not fine-grained enough! To make it more
> useful it would be necessary to split iterators into positioning and
> access, not to remove the iterator level.
Ok. Part of that is being debated elsewhere.
> - Iterators provide the possibility to produce the contents of the sequence
> on demand rather than computing it up front. For example, if the sequence
> is the result of a data base query, there is not much point copying the
> whole result into a container if all what is done with the result is
> finding the first element which does match a condition not easily
> formulated in a data base query (== any condition more complex than a
> wild card match of members - at least to me :-) Basically, iterators
> operate on sequences. [sequential] Containers are a subset of sequences.
The data base is a non-sequential container. The query just translates
part of it into a sequence so that it can be passed to a sequential
algorithm. If anything more complicated is needed, the sequence needs
to be placed in some kind of random access or special form container.
You can't sort a sequence on the fly, for example.
> Yes, you can go with containers in this context, too, but it is pretty
> unnatural. That said, I can imagine that there is also a container-level
> set of algorithms which is just implemented in terms of the
> iterator-level ones (which are, in turn, implemented in terms of the
> algorithms operating on property maps and iterators).
Did I miss something? Isn't a property map a parallel container?
> However, what is important is that when you
> create something like a sequence and you provide an iterator interface, it
> much more likely to interface well with other functions also taking a
> sequence than using some form of container interface.
I read this as providing a sequence access to the container for use by
simple sequential functions.
> That is, even if you never use any of the STL containers (eg. because all
I snipped this one which basically says that sequential problems can be
solved sequentially and the iterator pair is a useful abstraction.
> Just for the record: I'm using STL algorithms frequently in a commercial
> projects. No doubt, normally the algorithms used aren't the most complex
> ones: Typically, I'm using sort(), copy(), transform(), for_each(), and
> find(). All but sort() can be written with a simple loop.
Yes, and sort needs a container. I also use those algorithms with the
exception of for_each and use some others. My reasons agree with yours.
> Before you jump at me and tell me that it would be even easier to write and
> be more readable
>
> copy(source, dest);
No danger, that is someone elses pet project.
> please note that typically either the source or the destination is not a
> container! Often the source is input from a data base query, a file (which
> is just a special case of a data base), an IP stream, or something actually
> unspecified. The same applies to the output.
Sorry, I see it as a container anyway. Istream iterators provide
sequential read access to a file container.
> Also, I'm not at all against
> such a convenience layer but personally I'm more interested in getting the
> base right before discussing how to make it more convenient to use in
> special cases.
We are in agreement here.
> > The STL sales pitch: It is extensible. Just create a new algorithm
> > which operates on the existing iterator categories and it will work
> > with the existing containers. Just create a new container and provide
> > iterators in the existing categories and it will work with the
> > existing algorithms.
>
> It is more than just a sales pitch! It is what STL is about. Maybe I have
> not only become a [language] lawyer but also a sales person since this is
> what I'm busy saying. Well, I'm trying to sell a more flexible product but
> if people insist on the STL interface I will stick with this (... and use
> a more flexible approach underneath; that is what will happen anyway).
Maybe I see your point here. The STL does sequences and you are
claiming that all problems can solved using sequences. Since programs
are sequential, anything can be turned into a sequential solution.
> > Dietmar's pitch: The concepts behind the STL are reusable to create
> > new containers which do not work with the old algorithms, and new
> > algorithms which do not work with the old containers. The new
> > algorithms and containers work together using new iterators which
> > do not fit in the old categories.
>
> Although this resembles my position, it glosses over some important
> details:
>
> - I'm not suggesting anyone should use a different set of concepts for
> sequences (well, I am but in a more structured way which would not at
> all break compatibility with the current approach; however, I'm
> sticking to the concept of pairs of iterators and all I want to do is
> a different access to the elements than operator*(), mainly to
> distinguish between read and write accesses). Nor am I suggesting that
> people should create new algorithms for sequences which do not
> interoperate with the current STL iterators.
I thought you wanted other than sequential approaches.
> - I am suggesting new concepts for non-sequence structures and the
> corresponding algorithms! I am doing this for years and I actually
> started to work on new concepts for non-sequence structures a week
> or two after I read about STL in the Stepanov and Lee paper: It was
> for my diploma thesis where I describe the basic concepts use for
> graph algorithms. What I sketched in my previous article were the
> concepts for binary trees, as was pointed out in another article
> clearly a non-sequence, and the corresponding algorithms. ... and
> I also pointed out how to interface the tree concepts with the
> sequence concepts! Similarily, the graph concepts built upon the
> sequence concepts eg. to deal with incident edges, adjacent
> nodes, all edges, or all nodes.
This is where I am not seeing your point. A graph is a container. It
contains a structure which is much more important than the data values.
Yes it can be represented as a sequential edge list, but no problems
can be solved using that representation. That is a good way to transfer
information into and out of the graph container only.
The real problem for me is tree. A tree may be a graph with structure
or it may be a simple data structure on a sequence. These are two
very different things.
A binary search tree has no interesting tree properties. It is a
container. You see rebalance after add as a sequential algorithm
on a subsequence of the path to the root. Rotate is an algorithm
that operates on the nodes in this sequence. I see rotate as a
function that operates on a piece of a binary search tree. It is
not an algorithm on trees. You don't change the structure of a
tree.
You may get some nice functional decomposition for operations which
are partially common to various forms of binary search tree. I don't
see any binary search tree algorithms for inclusion in the library.
The library has associative containers. I see them as wrappers of
a binary search tree container. What abstraction do you see for the
many possible binary search tree structures? Do these abstractions
preserve the search tree properties? I don't think that belongs in
algorithms removed from the data structure. Do you see general
binary tree algorithms which if properly used may maintain a binary
search tree as useful in the library?
Should the library provide these low level containers to match the
low level sequences or should it provide useful interfaces as it
now does?
No arguement that iterators will be important in whatever is
provided. The question is what are the abstractions and at what
level should they be specified in the standard?
I am removing the remainder which is well said. Yes, the sequence is
the solution for moving information from one place to another. When
it gets there, the programmers will still have the problem of finding
a way to perform more complex operations than simple sequential
access. That requires a container.
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.research.att.com/~austern/csc/faq.html ]
Author: John G Harris <john@nospam.demon.co.uk>
Date: Fri, 25 May 2001 20:14:57 GMT Raw View
In article <memo.20010525041910.59825E@brangdon.madasafish.com>, Dave
Harris <brangdon@cix.co.uk> writes
<snip>
>(2) Make sequences into explicit, single objects.
I'm still not sure what you mean by a "sequence". Do you mean something
that provides a narrow access interface, with little more than a GetNext
method ?
>I suspect that explicit sequences would help deal with graph fragments
>which are not represented well by iterator pairs.
<snip>
By definition, when you linearise something it looks like anything else
that is linear. The problems, or lack of them, won't be any different.
John
--
John Harris
mailto:john@jgharris.demon.co.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.research.att.com/~austern/csc/faq.html ]
Author: Dietmar Kuehl <dietmar_kuehl@yahoo.com>
Date: Sat, 26 May 2001 18:16:05 GMT Raw View
jpotter@falcon.lhup.edu (John Potter) wrote:
> > That is, it is rather irrelevant to discuss whether a specific container
> > should exhibit a certain access policy: If you want a container with
> > specific policies, create one! There is a bunch of containers available
> > as examples and to built upon in the standard library but these are not
> > intended to solve everybodies problem. What the STL is about is making
> > it viable for users to create their specific container which fits smoothly
> > with other sequences.
>
> I can agree with this, but I may not be reading what you are saying.
> The STL provides basic low level sequence containers. Vector is an
> array, deque is an argv, slist is a singly linked list, list is a
> doubly linked list. These are sequence containers and we have about
> exhausted the possibilities of sequence containers.
Although conceptually, there are not many sequence containers (I could
only come up with "file" which is not in your list) there are many
implementation details in which these can vary. This starts with basic
things like whether range checking is used and the allocation style and
may go a far way before it covers everybodies favorite container. There
are many containers and it makes sense to implement algorithms
independent
from these because the containers might vary in subtle details.
> It is trivial
> to wrap them to present any of the different policies desired. I
> agree with you there. Others want to play games with container
> generators to get the desired policies. These are also building
> blocks which can be used to create other abstractions. The algorithms
> may be used to create these abstractions, but they will not be usable
> on the resulting abstraction because it will no longer be a sequence.
We seem to be in violent agreement: There are other abstractions
than just sequences. Trees and graphs are the entities in the world
I considered mostly (discrete mathematics). I know of at least the
domain of matrices where generic approaches are used. All of these are
no sequences and the use of the sequence algorithms is pretty limited
in these domains. However, STL did not try to address these domains:
Neither were/are suitable concepts available nor are these domains
common enough to make inclusion of corresponding algorithms into the
standard reasonable.
> > ... or, on the other side of the story, to create their functions which
> > take arbitrary sequences fulfilling a minimum set of requirements as
> > arguments. Note, that this is not at all just an academic goal:
> > Different people in a project typically have different ideas with respect
> > to what kind of container to use to store things in but it is common that
> > you have to interface with them. Providing interfaces using iterators to
> > specify sequences, whether as input or as output, provides a common basis.
>
> Ok, sequence is the universal representation of information and makes an
> interface for transfer of data from one place to another.
This is not what I'm saying here: If a graph is to be transferred, a
suitable graph abstraction should be used. Likewise for trees. ... or
for sequences. What is important is that the same concepts are used for
common abstractions. The hierarchy of iterator concepts defined in STL
is a good choice for sequences. The different kinds of iterators in the
Boost Graph Library provide a good choice for graphs. Eventually there
will be concepts for other domains, too.
> > - Iterators provide the possibility to produce the contents of the sequence
> > on demand rather than computing it up front. For example, if the sequence
> > is the result of a data base query, there is not much point copying the
> > whole result into a container if all what is done with the result is
> > finding the first element which does match a condition not easily
> > formulated in a data base query (== any condition more complex than a
> > wild card match of members - at least to me :-) Basically, iterators
> > operate on sequences. [sequential] Containers are a subset of sequences.
>
> The data base is a non-sequential container. The query just translates
> part of it into a sequence so that it can be passed to a sequential
> algorithm.
In general, the details of the data base are hidden behind the query
interface, at least for relation data bases. Thus, the interface to a
data base consists of sequences. It is true that internal to the data
base probably some form of balanaced trees is used (eg. for indices)
combined with some page structure for the actual data. I deliberately
concentrated on data base queries rather than on data bases :-)
> If anything more complicated is needed, the sequence needs
> to be placed in some kind of random access or special form container.
> You can't sort a sequence on the fly, for example.
To the algorithms it does not matter whether there is indeed a
container.
Yes, swapping elements somewhat assumes that there is a container
underneath but this detail is completely irrelevant to the algorithms.
The algorithms just assume that the elements are swapped. How this is
done does not matter.
> > Yes, you can go with containers in this context, too, but it is pretty
> > unnatural. That said, I can imagine that there is also a container-level
> > set of algorithms which is just implemented in terms of the
> > iterator-level ones (which are, in turn, implemented in terms of the
> > algorithms operating on property maps and iterators).
>
> Did I miss something? Isn't a property map a parallel container?
Depends on what a "parallel container" is for you... Basically, a
property
map is something mapping a position identified by an iterator to a
value.
Using different property maps the same position can be mapped to
different
values. However, this mapping does not at all require a container
although
some property maps are indeed containers. Here are a few examples I
have used (although typically in the context of graph algorithms where
I have originally delevoped the concept, at that time under the name
"data accessor"):
- A constant: For all positions the same constant value is returned when
reading a property. This is eg. useful for algorithms which can cope
with some concept of "length" (eg. a shortest path algorithm) but the
structure always uses the same distance. Obviously, this property map
is not really a container (well, there is one value stored for the
map).
- A computed value: Taking two (or more) property maps the value changed
or read is actually computed. An example for this is free capacity in
a flow algorithm: Depending on the direction you are looking, the free
capacity is the either the difference between the maximum capacity and
the current flow (looking in the direction of the flow) or the current
flow (looking in the opposite direction of the flow). Augmenting flow
changes the current flow correspondingly, implicitly adjusting the
capacities. Strictly speaking, this is also not a container by itself:
The actually containers are used in the property maps for the flow
and the capacity.
- Of course, there are also containers for values, eg. a vector indexed
by a suitable ID obtained from an iterator or a struct associated with
each iterator position.
In some sense, a property map is indeed something like a parallel
sequence or whatever structure is considered underneath: Logically, the
set of associated property maps makes up the columns of a table and the
elements of the sequence make up the rows. An iterator specifies the
row,
a property map specifies the column. The representation of the columns
may vary, of course. What the current STL gives us is basically a table
with exactly one column...
> > However, what is important is that when you
> > create something like a sequence and you provide an iterator interface, it
> > much more likely to interface well with other functions also taking a
> > sequence than using some form of container interface.
>
> I read this as providing a sequence access to the container for use by
> simple sequential functions.
Yes, that's about it.
> > > The STL sales pitch: It is extensible. Just create a new algorithm
> > > which operates on the existing iterator categories and it will work
> > > with the existing containers. Just create a new container and provide
> > > iterators in the existing categories and it will work with the
> > > existing algorithms.
> >
> > It is more than just a sales pitch! It is what STL is about. Maybe I have
> > not only become a [language] lawyer but also a sales person since this is
> > what I'm busy saying. Well, I'm trying to sell a more flexible product but
> > if people insist on the STL interface I will stick with this (... and use
> > a more flexible approach underneath; that is what will happen anyway).
>
> Maybe I see your point here. The STL does sequences and you are
> claiming that all problems can solved using sequences. Since programs
> are sequential, anything can be turned into a sequential solution.
No! Not all problems are reasonably viewed as sequences! STL is only
about sequences. For the domain of sequences, the concepts in STL
(ie. iterators, possibly with the addition of property maps) are well
suited. For graph problems you will need suitable graph concepts (in a
nutshell: adjacency and incidence iterators coupled with property maps
and, possible, iterators for all nodes and edges; this works well at
least for network flow algorithms). For trees, you will need tree
concepts.
For matrices, you will need matrice concepts. And so on...
There is a certain tendency that existing concepts show up again,
embedded
into a different concept: The adjacent nodes used in a graph abstraction
just form a sequence and should use the sequence abstraction. The
children
of a node in a general tree abstraction form a sequence and should also
use a sequence abstraction. Likewise for the columns and rows of a
matrix.
However, this does not mean that everything is a sequence! There is
more structure in a graph than just a sequence (although a graph can,
obviously, be represented as a sequence).
> > - I am suggesting new concepts for non-sequence structures and the
> > corresponding algorithms! I am doing this for years and I actually
> > started to work on new concepts for non-sequence structures a week
> > or two after I read about STL in the Stepanov and Lee paper: It was
> > for my diploma thesis where I describe the basic concepts use for
> > graph algorithms. What I sketched in my previous article were the
> > concepts for binary trees, as was pointed out in another article
> > clearly a non-sequence, and the corresponding algorithms. ... and
> > I also pointed out how to interface the tree concepts with the
> > sequence concepts! Similarily, the graph concepts built upon the
> > sequence concepts eg. to deal with incident edges, adjacent
> > nodes, all edges, or all nodes.
>
> This is where I am not seeing your point. A graph is a container. It
> contains a structure which is much more important than the data values.
> Yes it can be represented as a sequential edge list, but no problems
> can be solved using that representation. That is a good way to transfer
> information into and out of the graph container only.
I'm not saying that a graph is supposed to be forced into a sequence.
This would be pretty useless. What I'm saying is that the graph concepts
will use sequences as subparts. For example, given a graph and some node
identification, there are sequences of adjacent nodes and incident edges
(and for planar graph also a sequence of associated facets). A graph is
not a sequence but, in some sense, can be viewed as sequence of
sequences:
There is a sequence of nodes and for each node there is an individual
sequence of incident edges, form which the sequence of adjancent nodes
can be computed. That is, the graph concepts use sequences but a graph
is much more than just a sequence.
> The real problem for me is tree. A tree may be a graph with structure
> or it may be a simple data structure on a sequence. These are two
> very different things.
Don't mix representation with abstraction! A sequence is a bad
abstraction
when operating on trees. Of course, an array can be seen as a fully
balanced binary tree: Node 'int(n / 2)' is the parent of node 'n' and
nodes '2 * n' and '2 * n + 1' are the children of node 'n' (this might
contain an off-by-one error; the details are irrelevant here). However,
eg. a search algorithm on a binary tree is probably best formulated in
more abstract terms than this (ie. 'lower_bound()' is actually a tree
algorithm which should be formulated as such!).
> A binary search tree has no interesting tree properties. It is a
> container.
A binary search tree is a container? Come on! Finding the root of a
number given a start value can be seen as a binary tree: each node has
the current value under investigation as value and whether you go left
or right depends on whether it is too big or too small. The children of
a single node are the current value plus/minus a suitable delta which
is just split into halves on the next level. I forgot how this algorithm
is called but it does not really matter. What matters is that there may
be implicitly given binary search trees which can be investigated by
suitable binary tree search algorithms! This example might be pretty
useless but there are practical examples where eg. the path towards an
element is of interest.
> You see rebalance after add as a sequential algorithm
> on a subsequence of the path to the root. Rotate is an algorithm
> that operates on the nodes in this sequence. I see rotate as a
> function that operates on a piece of a binary search tree. It is
> not an algorithm on trees. You don't change the structure of a
> tree.
Maybe you are not changing the structure of the trees you are using
but there may be other uses. I can imagine that some form of expression
evaluator representing expressions as binary trees might very well
change
the structure of the tree, including rotations, to rewrite the original
expression into an optimal form. ... and even if a rotation is only
useful for binary search trees, the 'rotate()' function would be used in
several different places, eg. the insertion and removal into an RB tree,
an AVL tree, and whenever a splay tree is accessed. Why not provide it
for the sake of at least these implementations and possibly other binary
search tree implementations? Likewise for a tree walk algorithm which
decides whether to go left or right on a given predicate.
> You may get some nice functional decomposition for operations which
> are partially common to various forms of binary search tree. I don't
> see any binary search tree algorithms for inclusion in the library.
'rotate()' (probably in several forms; this somewhat depends on the
details of the interface design) and 'lower_bound()' (which actually
*is*
in the standard library: a tree algorithm without a tree abstraction!)
are
obvious candidates. 'find_leftmost_decendent()', 'find_root()' and
'depth()' are others. Probably it makes sense to provide insert
operations
using appropiate balancing mechanisms and so on. Whether these
algorithms
make it into the standard library or some add-on addressing tree
specific
stuff does not really matter: Binary trees are probably a reasonable
abstraction on which a bunch of algorithms can be provided.
I briefly thought about things like 'tree_count()' which does the same
as
'std::count()' just for the tree abstraction but this does not make much
sense: For this counting stuff no structure is required and it makes
more
sense to view the tree as a sequence using some appropriate iterator and
use 'std::count()' on such a sequence. On the other hand, tree
equivalents
of 'std::adjacent_find()' might be reasonable, maybe something like
"family_find()" which takes the parent and its two children, passing
them
to a tenary predicate.
> The library has associative containers. I see them as wrappers of
> a binary search tree container.
That's just one use of binary search trees. Some form of encoding can
also
be done using binary search trees, providing the bit sequence according
to the left/right choices needed to find an element. The point is that
it actually make life easier for the person creating eg. an associative
container if corresponding lower level functions are available. Sure,
'rotate()' is probably implemented in 10 minutes plus 10 minutes for
the test cases and, if I'm implementing it, half an hour until I finally
spot the subtle error due to an accidental use of a negated condition...
Still, less than an hour. The user looking at the documentation for a
total of five minutes (reading it ten times or whatever reason there is
to take that long) and applying it taking another 5 minutes saved 20%
of the time necessary.
... and it make the code more readable if functions like 'rotate()' are
used rather than manipulating the pointers directly!
> What abstraction do you see for the
> many possible binary search tree structures? Do these abstractions
> preserve the search tree properties?
The abstraction I'm seen is something like a "tree node iterator" which
has methods to move the left or the right child and, as a more advanced
category, also move to the parent. It probably makes sense to use a
different approach to determine whether the iterator can move to the
left, to the right, or to the parent. Also, there should probably be
some
approach to change the left and right children. Maybe something like
this:
nit, nit1, nit2 are node iterators (I was tempted to call them tree
iterators but people might consider the resulting iterator names as
offensive :-) of type NIt, left, right, and parent are property
maps. The following expression should be valid:
expression type meaning
------------------------------------------------------------------
NIt nit1(nit2) n/a copy ctor (dtor implied!)
nit1 = nit2 NIt copy assignment iterators
has(left) bool has left child?
get(left, nit) NIt get left child
set(left, nit1, nit2) void set left child
has(right) bool has right child?
get(right, nit) NIt get right child
set(right, nit1, nit2) void set right child
has(parent) bool has parent?
get(right, nit) NIt get parent
set(right, nit1, nit2) void set parent
I think that something like this allows implementation of most
operations
typically done on binary trees. Note, that this only defines access
methods to the structure of the tree, not to any associated data. The
tree algorithms don't care about the associated data, they are just
interested in the structure. For some tree algorithms it is implicitly
assumed that there is some data (eg. 'tree_find()') but there is no
need to specify how this data is actually accessed.
Obviously, the abstraction does not preserve anything like search tree
properties. Some algorithms on this tree, eg. the various rotations,
will,
however, preserve the search tree properties. Some algorithms preserve
some balance properties. There might be other interesting algorithms
on binary trees which preserve neither and which are used for different
applications than binary search trees...
> I don't think that belongs in
> algorithms removed from the data structure. Do you see general
> binary tree algorithms which if properly used may maintain a binary
> search tree as useful in the library?
I don't want to overemphasize the binary tree example: Yes, I think
there
can be a useful tree library and when dealing with trees I would
probably
implement operations according to a suitable abstraction like the one
above (possibly augmented with stuff I have just forgotten). But I think
there are other libraries and abstractions which are more useful :-)
It is worth noting that I found it easier to write generic graph
algorithms than writing algorithms for a concrete graph data structure
(Jeremy Siek said something similar when I mentioned this observation):
Implementing in terms of general abstractions removes the need to also
maintain the specific data structures properties! This becomes business
of probably auxiliary entities like iterators and property maps. Thus,
whenever accessing a non-trivial data structure it makes sense to use an
appropriate abstraction, especially if this abstraction does not imply
any runtime cost.
> Should the library provide these low level containers to match the
> low level sequences or should it provide useful interfaces as it
> now does?
Fortunately "or" is inclusive: It is likely that both are provided :-)
> No arguement that iterators will be important in whatever is
> provided. The question is what are the abstractions and at what
> level should they be specified in the standard?
Whether such abstractions make it into the standard is not at all clear
to me: This might be too much work for to few benefit. Still, I see
a place for tree abstractions and a corresponding library, eg. in the
context of the Boost library.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: pdimov@mmltd.net (Peter Dimov)
Date: Sat, 26 May 2001 18:18:15 GMT Raw View
brangdon@cix.co.uk (Dave Harris) wrote in message news:<memo.20010525041910.59825E@brangdon.madasafish.com>...
> pdimov@mmltd.net (Peter Dimov) wrote (abridged):
> > I wondered how long will it take before we get to the A- word. :-)
>
> It's not meant disparagingly. I do believe Stepanov and Lee's aims were
> not exactly the aims we should have.
Yes, this is the fundamental conflict between designing an infinite
algorithm/container framework and a finite Standard Library collection
of algorithms and containers.
Stepanov and Lee tried to design an infinite framework. I happen to
think that this is the right approach, even when the Standard Library
has to pick a finite subset of it, but this view is not universally
shared. :-)
> I think I've addressed your other points over in c.l.c++.m. Brief
> summary: what I would actually advocate is 2 things:
>
> (1) Open up the iterator category system, so that users can add new
> iterator tags and specialise std algorithms upon them.
Open up - yes; specialise their own algorithms upon them - yes.
Specialise std algorithms upon them - I don't know.
> (2) Make sequences into explicit, single objects.
>
> I suspect that explicit sequences would help deal with graph fragments
> which are not represented well by iterator pairs.
I admit that I can't grasp all implications of this refactoring to be
able to form an opinion. I think few people can without evaluating a
reference implementation in real world conditions.
> > Assuming that you don't use iterators as an abstraction layer, how are
> > you going to manage the combinatorial explosion?
>
> Work at whatever level is appropriate:
>
> o Sequence categories.
> o Sequences.
> o Iterators.
> o Containers.
>
> At the container level I would deal with the combinatorial explosion by
> only implementing the combinations I actually needed.
... and knew about.
The questions that arise are:
When is the Iterators level not appropriate?
When is the Containers level appropriate?
--
Peter Dimov
Multi Media Ltd.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Sun, 27 May 2001 03:03:45 GMT Raw View
john@nospam.demon.co.uk (John G Harris) wrote (abridged):
> I'm still not sure what you mean by a "sequence". Do you mean something
> that provides a narrow access interface, with little more than a
> GetNext method ?
I mean something that offers roughly what is available from a pair of
(forward) iterators. The 3 core operations are Next, Get, and AtEnd (I
wouldn't conflate Get and Next into GetNext). Probably we should also
have methods to convert into an iterator pair, for compatibility.
For example, using more STL-like names:
template <typename iterator>
class iterator_sequence {
public:
typedef iterator_traits<iterator>::value_type value_type;
typedef iterator_sequence<iterator> sequence_type;
// Constructor.
iterator_sequence( iterator first, iterator last ) :
myFirst(first), myLast(last) {}
// Conversion to iterator pair.
iterator first() const { return myFirst; };
iterator last() const { return myLast; };
// Core operations.
bool empty() const { return myFirst == myLast; }
value_type &operator*() { return *myFirst; }
sequence_type operator++() { ++myFirst; return *this; }
private:
iterator myFirst, myLast;
}
This is just an outline - add "typename", more typedefs and traits etc as
needed.
Clearly we can implement for_each() for a sequence in terms of for_each()
for an iterator pair, by using the first() and last() methods.
Alternatively, we can implement it like:
template <typename sequence, typename fun>
fun for_each( sequence s, fun f ) {
for ( ; !s.empty(); ++s)
f( *s );
return f;
}
This uses only what I called the 3 core operations. As such it is more
general. We can provide other implementations of sequence. For example,
we can have a sequence which uses a terminating value instead of a second
iterator. This would suit strings terminated by '\0', file streams
terminated by EOF, etc. Or we can have a sequence which stores a
reference to its container, and uses container.end() instead of myLast.
> > I suspect that explicit sequences would help deal with graph
> > fragments which are not represented well by iterator pairs.
>
> By definition, when you linearise something it looks like anything else
> that is linear. The problems, or lack of them, won't be any different.
Well, no, but it is easier to deal with a single object, that has all the
info, then with two objects with half the info each. Having access to the
container can help a lot.
Obviously we can put all the info into one iterator, duplicate it in the
second (since it must have the same type), and then ignore the redundant
copy, but that seems kinda silly. It is inefficient and it also makes it
conceptually harder to think about problems. The second iterator is a
distraction. It also creates opportunities for mis-matched iterators and
bugs.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: =?iso-8859-1?Q?Andr=E9_P=F6nitz?= <poenitz@htwm.de>
Date: Wed, 23 May 2001 15:05:39 GMT Raw View
Dave Harris <brangdon@cix.co.uk> wrote:
> I don't see what can be done with an implicit pair that couldn't be don=
e=20
> with an explicit pair, so I don't follow your point about being more=20
> general and composable.
I wonder why this "sequence" concept meets such an opposition:
Yes, sequences can be implemented as a pair of iterators, containers coul=
d
be viewed as sequences with certain properties so we "have" sequences
already - "real" sequences might be "only" "syntactic sugar". But so is
most of the Standard Library.
Sequences clearly form a concept of its own "between" iterators and
containers. We can give it a name and understand what is meant by it. Thi=
s
concept is pretty general. It is useful for encapsulation and can save
typing. We can use it to express ideas more directly without resorting to
the idiomatic use of iterator pairs. Sometimes they even can be used more
efficiently then iterator pairs.=20
So why this opposition? Is it the fear of bloat in the library and/or
standrad?=20
Andre'
PS:
> I agree the old approach must be kept, even if a new approach is better=
.=20
Undoubtedly.
--=20
Andr=E9 P=F6nitz ............................................. poenitz@ht=
wm.de
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: =?iso-8859-1?Q?Andr=E9_P=F6nitz?= <poenitz@htwm.de>
Date: Wed, 23 May 2001 15:05:54 GMT Raw View
Eugene Karpachov <jk@steel.orel.ru> wrote:
> Yes, that's it. I'm surprized that (almost) nobody is talking about
> closures in this brain-storming; for me, it's the most important possib=
le
> change.
I thought it was clear that closures (with a convenient syntax) are
needed desperately ;-}
But then I got the impression that different people use different subsets
of the languange and do not care much about the others. So those in need =
of
closures might inhabitate some niche not represented by those currently
involved in the brain storming and later in the Stadards body...
Would be bad, wouldn't it?
Andre'
--=20
Andr=E9 P=F6nitz ............................................. poenitz@ht=
wm.de
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Radoslav Getov" <nospam@mai.com>
Date: Wed, 23 May 2001 16:51:56 GMT Raw View
"Bjarne Stroustrup" <bs@research.att.com> wrote in message
news:GDFMJH.JLz@research.att.com...
:
:
: I happen to disagree. Not everyone hates allocators and they are not just
: unnecessary complexity. They are a useful concept. For example, they allow
: easy use of allocators specialized for a particular type.
:
I happen to disagree.
Allocators effectively prevent, at least for me, e.g. forward declaring
of std containers e.g.:
namespace std
{
template <class T> class vector;
}
One has to use probably something like this:
namespace std
{
template <class T> class allocator;
template <class T, class Alocator = std::allocator> class vector;
}
Writing an allocator is far than a simple task. If nothing else, it has
several
typedefs and several functions. It is too complicated a thing. I believe
that's
the main reason the people get discouraged to make an allocator of their own
in the rare cases in which they think they need one.
Type-specific allocators are kind of illusion. I have the impression that
none of
the allocators used in container<T> allocates objects of type T. Rather than
that,
continuous chunks of memory (like in vector) and "nodes" of unspecified size
and
structure (in set, list, etc) are allocated. So what if my allocator knows
how to
allocate objects of type T? It will not be used for this purpose anyway; the
reality
is that it has to be an "universal" allocator.
Using an allocator, one can bind specific container's allocations to
particular
"heap" or whatever if one has - and that's all about it. How often does it
happen?
And why? I suspect in most such cases the reason is that the programmer
believes
that HIS allocator is better than the standard library heap manager. I also
believe
that in most such cases the programmer is wrong.
In another post I proposed having two versions of the containers: one
with allocator (for the very few that will need it AND for backwards
compatibility)
and one without (for the overwhelming majority). It does not only look that
this change will preserve the existing code, but will even improve it by
making
it faster and smaller.
Actually, I will not be surprized if some STL implementors try this even
if it is a non-standard feature. At the end, from the user's point of view,
there is
no difference.
Radoslav Getov
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: =?iso-8859-1?Q?Andr=E9_P=F6nitz?= <poenitz@htwm.de>
Date: Wed, 23 May 2001 18:29:00 GMT Raw View
Hans Bos <hans.bos@xelion.nl> wrote:
> I don't see an obvious way to view a graph (where a node can have zero
> or more connections to other nodes) as a sequence. But I may want to ca=
ll
> functions like for_each and find_if to iterate over the graph, but I
> don't care much about the order (and you can't describe a subgraph with=
a
> begin-node and an en-node).
This is not as bad as you describe since you can have as many
different iterators as you want. So you could have
=20
nbegin() and nend() for iterating over nodes
ebegin() and eend() for iterating over edges
ibegin(node v) and iend() for iterating over edges incident to some
given node
etc.
The "obvious way" is the way that is easiest (or possibly fastest) given
your data structure for a given task. This means of course that you need
more then the usual begin/end (rbegin/rend) iterator pair, but I doubt
you would need more than six or seven of them.
You are going to perform sequential computation in the end anyway, so
you have to pick an order sooner or later, even if there are conceptually
"unimportant".
I agree it would be nice to be able to say "do something with each elemen=
t
of this collection, and I don't care in which order you are doing it" (as
in "for_each(all_nodes(G), func);") since this would map the real
task better to the language.
[This is btw a nice example where "native" sequences can perform better
than iterator pairs: complex iterators usually have some kind of
backreference to the container as well as some description of the actual
position. With two iterators representing a sequence in a container both
refer two the same container, and one of the backreferences is overhead]
Andre'
--=20
Andr=E9 P=F6nitz ............................................. poenitz@ht=
wm.de
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Wed, 23 May 2001 23:17:50 GMT Raw View
Radoslav Getov wrote:
...
> Allocators effectively prevent, at least for me, e.g. forward declaring
> of std containers e.g.:
>
> namespace std
> {
> template <class T> class vector;
> }
>
> One has to use probably something like this:
> namespace std
> {
> template <class T> class allocator;
> template <class T, class Alocator = std::allocator> class vector;
^
Correction: <T>
> }
...
> Type-specific allocators are kind of illusion. I have the impression that
> none of
> the allocators used in container<T> allocates objects of type T. Rather than
> that,
> continuous chunks of memory (like in vector) and "nodes" of unspecified size
> and
> structure (in set, list, etc) are allocated. So what if my allocator knows
> how to
> allocate objects of type T? It will not be used for this purpose anyway; the
> reality
> is that it has to be an "universal" allocator.
Not true. Footnote 214 indicates that allocators are intended to provide
efficient allocation of single objects, even when they're very small. A
universal allocator can't do that. Stroustrup shows in his book "The C++
Programming Language" one way to make very quick single-object
allocations, but it's essential to the algorithm that they be
fixed-size. A simple way to do this would be to have Allocator<T>
forward to SizedAllocator<sizeof(T)>, where SizedAllocator<N> uses
different approaches and possibly different memory pools for different
values of N.
> In another post I proposed having two versions of the containers: one
> with allocator (for the very few that will need it AND for backwards
> compatibility)
> and one without (for the overwhelming majority). It does not only look that
> this change will preserve the existing code, but will even improve it by
> making
> it faster and smaller.
With a decent implementation of the standard containers and
std::allocator<T>, using a decent compiler, there shouldn't be any
improvement in speed or size by using the no-allocator version you
propose, rather than using the default allocator with the current STL.
It should compile to essentially the same code, unless you're proposing
that the no-allocator version use something other than new and delete.
The only significant difference is likely to be in
typeid(std::Container<T>).name().
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: dietmar_kuehl@yahoo.com (Dietmar Kuehl)
Date: Tue, 22 May 2001 20:29:21 GMT Raw View
Hi,
jpotter@falcon.lhup.edu (John Potter) wrote in message news:<3b09126a.14933584@news.csrlink.net>...
> > Hm, looks like you are in bad mood due to some problem or you are
> > playing devils advocate... Anyway, here we go:
>
> Neither, we are just not talking about the same thing.
Apparently I didn't make my point as clear as it could have been... At least,
your summary of what I'm talking does not really match what I'm saying and
I'm indeed not that sure that we are talking about different things.
Basically, my position is that there is not much point to fiddle around with
container details like whether container should be range checked, have
allocators, std::vector<bool> being a specialization, etc. Neither is there
much point to quibble much about the interface of the algorithm. When talking
about a new STL it makes much more sense to discuss the foundation of STL
rather than talking about the details of entities resulting from the details
of the foundations.
That is, it is rather irrelevant to discuss whether a specific container
should exhibit a certain access policy: If you want a container with specific
policies, create one! There is a bunch of containers available as examples
and to built upon in the standard library but these are not intended to solve
everybodies problem. What the STL is about is making it viable for users to
create their specific container which fits smoothly with other sequences.
... or, on the other side of the story, to create their functions which take
arbitrary sequences fulfilling a minimum set of requirements as arguments.
Note, that this is not at all just an academic goal: Different people in a
project typically have different ideas with respect to what kind of container
to use to store things in but it is common that you have to interface with
them. Providing interfaces using iterators to specify sequences, whether as
input or as output, provides a common basis.
A container for the same purpose does not suit well for at least two reasons:
- If the container types don't match between components, it is necessary to
copy them. Even if the containers are a generic arguments, this does not
work out well because often it is necessary to change the view of each
individual element, eg. by adding some data or selecting partial data. In
fact, my view is that STL is not fine-grained enough! To make it more
useful it would be necessary to split iterators into positioning and access,
not to remove the iterator level.
- Iterators provide the possibility to produce the contents of the sequence
on demand rather than computing it up front. For example, if the sequence
is the result of a data base query, there is not much point copying the
whole result into a container if all what is done with the result is
finding the first element which does match a condition not easily
formulated in a data base query (== any condition more complex than a wild
card match of members - at least to me :-) Basically, iterators operate on
sequences. [sequential] Containers are a subset of sequences.
Yes, you can go with containers in this context, too, but it is pretty
unnatural. That said, I can imagine that there is also a container-level set
of algorithms which is just implemented in terms of the iterator-level ones
(which are, in turn, implemented in terms of the algorithms operating on
property maps and iterators). However, what is important is that when you
create something like a sequence and you provide an iterator interface, it
much more likely to interface well with other functions also taking a
sequence than using some form of container interface.
That is, even if you never use any of the STL containers (eg. because all
sequences you are interested in are the results or inputs of data base
queries) and you never use any of the STL algorithms (eg. because there is
no algorithm suitable to deal with your data base queries; actually, this is
somewhat unusual because eg. 'std::transform()' just does the right thing),
the underlying concept, namely the iterators, are very useful! This provides
a common interface, making the use, interface design, and implementation of
algorithms/functions operating on sequences more simpler. For the user it is
obvious how to specify an input sequence or how to use an output sequence:
It is a sequence like all other sequences and there is no need to learn about
a new approach. For the interface designer, there is no need to determine how
a sequence should be passed in (as a begin and end iterator) or out (well,
there really should be more consensus here: looking closely at the standard
library, eg. 'std::equal_range()' suggests that a 'std::pair<>' of the begin
and end is used but this is not that obvious). ... and the implementer also
works on familiar ground and is even given a standard interface to lazy
evaluation of sequences (again, data base queries come to mind).
Just for the record: I'm using STL algorithms frequently in a commercial
projects. No doubt, normally the algorithms used aren't the most complex
ones: Typically, I'm using sort(), copy(), transform(), for_each(), and
find(). All but sort() can be written with a simple loop. I found it useful
to use the algorithms for two major reasons:
- Often it is easier to use the algorithm than to write the loop:
std::copy(source.begin(), source.end(), std::back_inserter(dest))
vs.
for (Source::const_iterator beg = source.begin(), end = source.end();
beg != end; ++beg)
dest.push_back(*beg);
Yes, just a simple loop, possibly in both cases.
- The algorithms explicitly says what I'm doing there. The loop does not.
Ultimatively, both constructs tell the reader what is going on, however,
the algorithm is documenting the intention, especially in the simple cases.
I noted in previous articles that the former version might be significantly
more efficient but this is, in fact, non of the reasons why I'm really using
the algorithms. It is an accepted side effect that the algorithms version is
also more efficient.
Before you jump at me and tell me that it would be even easier to write and
be more readable
copy(source, dest);
please note that typically either the source or the destination is not a
container! Often the source is input from a data base query, a file (which
is just a special case of a data base), an IP stream, or something actually
unspecified. The same applies to the output. Also, I'm not at all against
such a convenience layer but personally I'm more interested in getting the
base right before discussing how to make it more convenient to use in special
cases.
> The STL sales pitch: It is extensible. Just create a new algorithm
> which operates on the existing iterator categories and it will work
> with the existing containers. Just create a new container and provide
> iterators in the existing categories and it will work with the
> existing algorithms.
It is more than just a sales pitch! It is what STL is about. Maybe I have not
only become a [language] lawyer but also a sales person since this is what
I'm busy saying. Well, I'm trying to sell a more flexible product but if
people insist on the STL interface I will stick with this (... and use a more
flexible approach underneath; that is what will happen anyway).
> Dietmar's pitch: The concepts behind the STL are reusable to create
> new containers which do not work with the old algorithms, and new
> algorithms which do not work with the old containers. The new
> algorithms and containers work together using new iterators which
> do not fit in the old categories.
Although this resembles my position, it glosses over some important details:
- I'm not suggesting anyone should use a different set of concepts for
sequences (well, I am but in a more structured way which would not at all
break compatibility with the current approach; however, I'm sticking to the
concept of pairs of iterators and all I want to do is a different access to
the elements than operator*(), mainly to distinguish between read and write
accesses). Nor am I suggesting that people should create new algorithms
for sequences which do not interoperate with the current STL iterators.
- I am suggesting new concepts for non-sequence structures and the
corresponding algorithms! I am doing this for years and I actually started
to work on new concepts for non-sequence structures a week or two after I
read about STL in the Stepanov and Lee paper: It was for my diploma thesis
where I describe the basic concepts use for graph algorithms. What I
sketched in my previous article were the concepts for binary trees, as was
pointed out in another article clearly a non-sequence, and the
corresponding algorithms. ... and I also pointed out how to interface the
tree concepts with the sequence concepts! Similarily, the graph concepts
built upon the sequence concepts eg. to deal with incident edges, adjacent
nodes, all edges, or all nodes.
> The beauty of STL is gone. Maybe because it was only skin deep.
STL is just the start. It is the next layer building up fundamental types and
structures: It provides the concepts how to deal with sequences. That's
actually pretty useful since most of the stuff I have seen in the projects I
was involved with deals with sequences like results of data base queries,
stream, etc. When we managed to get over this one we are hopefully moving our
attentiation to more interesting stuff than moving back and forth sequences:
There is demand beyond mere data maintaince eg. for optimization stuff. The
management involved in deciding whether this stuff should be implemented just
"learned" that things beyond data maintaince seems to be intractable because
programmers get bogged down with gazillions of different techniques to pass
back and forth sequences. If nothing else, STL set a standard for passing
around sequences. That is the real heart of it! The concepts to access
sequences. All sequences. Everywhere. The beauty of it is not gone at all!
STL is not just "skin deep": It does not do much but what it does solves a
very real problem! The STL concepts tell us how to deal with sequences and it
does so in anefficient, convenient, and highly flexibily fashion.
No doubt, the actual STL algorithms would benefit from additional language
support (most notably "lambdas", ie. anonymous functions probably with a
closure which can just be created on the fly). The containers would also
benefit from some change here and there but can probably go without a
language change. Still, I consider it more important to make the fundamental
concepts even more flexible.
PS: Don't think that what I hope expressed pretty clearly towards the end of
this article was clear to me at all when I started writing this article!
Even if this discussion has no other effect, it at least brought an
important aspect of STL to my attentition just by writing this article :-)
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: pdimov@mmltd.net (Peter Dimov)
Date: Wed, 23 May 2001 09:24:04 GMT Raw View
brangdon@cix.co.uk (Dave Harris) wrote in message news:<memo.20010521152927.58931B@brangdon.madasafish.com>...
[...]
> There's a difference between producing a "generic" library as an academic
> exercise, and producing a base standard library for a language.
I wondered how long will it take before we get to the A- word. :-)
> So far this has been more theory than practice. We cannot just
> specialise:
>
> template <typename T>
> deque<T>::iterator find( deque<T>::iterator,
> deque<T>::iterator, const T& );
>
> as easily as we can specialise:
>
> template <typename T>
> deque<T>::iterator find( deque<T> &, const T & );
>
> I know the former is possible, but it's a bit like a dog walking on its
> hind legs.
It's barely possible, and only because of the "T const &" argument;
but the relevant thing is what do you mean by "we" in the sentence
above.
Are "we" the authors of std::deque? If yes, we can specialize find:
template <typename T, typename U>
_Deque_iterator<T> find( _Deque_iterator<T>,
_Deque_iterator<T>, const U& );
... although I'm not convinced that this is the way to enhance 'find'.
The goal should be to make 'find' understand all paged structures, not
merely std::deque; that is, if I make a deque-like container, MyDeque,
find should recognize it as being a paged structure and act
accordingly. Assuming that making 'find' understand paged structures
is essential.
> Iterators place a layer of abstraction between containers and
> algorithms, which just gets in the way when one wants an algorithm
> specialised on a container.
As I said in clc++m, iterators decouple algorithms from containers.
Suppose that you have N algorithms and M containers. Are you going to
write N*M implementations?
Assuming that you don't use iterators as an abstraction layer, how are
you going to manage the combinatorial explosion?
What if N and M are unbounded?
> Yes, the barrier can be circumvented, but
> it's hard work. Endless opportunities to demonstrate one's cleverness.
Again, hard work for whom? The user? The author of a new algorithm/new
container? The Standard Library implementor?
> The upshot is that we rarely bother with specialised algorithms, and so
> don't get much benefit from using algorithms at all.
Same question.
--
Peter Dimov
Multi Media Ltd.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Dennis Yelle <dennis51@jps.net>
Date: Sat, 19 May 2001 18:44:48 GMT Raw View
Dietmar Kuehl wrote:
>
> Hi,
> Dave Harris (brangdon@cix.co.uk) wrote:
> : Suppose we were designing a template library from scratch, without much
> : concern for backwards compatibility. Suppose it was going in a new
> : namespace, say stl:: instead of std::. What would we do differently?
>
> Whatever you consider, note that it is at the wrong level: Containers
> are the least important entities! Consider the standard containers as
> examples which might be a nice aid and even handy for some uses. If
> they aren't, just create your own container. That is the core idea of
> the whole stuff: If you want a new container, just create one and only
> consider the containment aspect of the container. This is made up of
> the capability to store and access the elements.
>
> What is more interesting is the concept of iterators: These are the
> entities whose interface is important to the standard library. The
> actual interface of the containers is more or less unimportant except,
> may be, for consistency sake. The interface of the iterators is
> important. Why is that?
>
> The heart of the whole thing are the algorithm (which should better be
> named "solvers" because strictly the algorithms aren't specified), the
> entities which are "hard" to create in the first place: These are
> already done and applicable to the containers written by the user -
> without even knowing how these containers look like!
Wow! You sure have a different view of the STL than I do.
>From my perspective, the containers are central.
vector is useful because it is so easy to use, and
map is even simpler to use than vector.
And the best part, is that I can combine them:
map< My_type, map< My_type, int> >
and then later, if I want to, I can change to this:
map< My_type, vector< pair<My_type, int> > >
And the impact on my code is small.
You must be a much better programmer than I am if you
can write map in 1/2 of a day.
On the other hand, most of the std:: algorithms are so simple
that it is easier and faster for me to write my own
than it is for me to find the one I want in the documentation.
The only exceptions to this that I can think of right now
are sort and next_permutation. And I can and have written
each of those myself in less than 1/2 day, but I find using
the std versions easier and faster.
Not counting sort and next_permutation, can you give
an example of a std:: algorithm that would take you more
than 1/2 day to write?
Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Sat, 19 May 2001 18:49:50 GMT Raw View
daniel.frey@aixigo.de (Daniel Frey) wrote (abridged):
> class Table
> {
> int& entry( int i = 0 ) { return &v[i]; }
> int entry( int i = 0 ) const { return v[i]; }
> };
This over-exposes the implementation. For example, with the set() API we
can do things like:
void Table::set_entry( int i, int value ) {
// Verify pre-conditions
assert( 0 <= value & value < 100 );
// Maintain running totals and other invariants.
sum += value - v[i];
// Store offset by 50 for some internal reason.
v[i] = value - 50;
}
int Table::entry( int i ) const {
return v[i] + 50;
}
Or consider vector::size(). It has no underlying instance variable which
can be assigned to.
Basically, if we hand out the address of our private instance variables
we lose encapsulation. We might as well make the variable "public" and be
done with it.
> It seems to me that your naming convention (using 'set') makes sense in
> the kind of code you write, probably depending on the requirements. I
> tend to avoid code that requires to call functions 'set_xyz'. I believe
> (but cannot prove :) that this helps me to produce better interfaces,
> but this is only my personal opinion.
Well, I think I have shown significant drawbacks with your schemes, and I
don't think you have shown any comparable advantages.
> I don't think there is one correct way of naming functions, but the STL
> was designed in a way not requiring function names to contain 'set' to
> be understandable.
My claim is that the STL names are not very understandable. Words like
"clear", "empty" are both verbs and adjectives. "Reserve" is both a verb
and a noun. These are bad examples to put before students.
That said, I prefer "reserve(int)" and "capacity()" to "capacity(int)"
and "capacity()". I just think "ensure_capacity(int)" would be better
still. It is more clearly an action, and it expresses the link with
capacity() better.
> Your example is nothing I found in the STL,
Never-the-less, it is an ambiguity we must bear in mind while reading
code from any source. This is the thing about naming conventions - if
they are to be standard they need to cope with a wide variety of
situations.
> The only thing I see is a potential mix-up of clear() and empty() -
> but would you call it set_clear() instead?
I'd use set_empty() or make_empty() or similar. And is_empty().
> To summarize it: As long as you don't show me how you argument relates
> to the STL and provides some real benefits, I don't see any reason to
> change the existing naming scheme. If you want to improve the STL, some
> of the other point you mentioned are definitely a good idea - but
> renaming the interfaces IMHO isn't.
I believe I have shown benefits. However, I can see I am not going to
persuade you.
Anyway, we cannot remove the current names without breaking backwards
compatibility. Possibly we could add new names and eventually depreciate
the old ones, but even though I feel strongly about this I suspect it is
not worth keeping 2 sets of names in the interim. I just hope people
proposing *new* containers and algorithms think carefully about how they
name them so that the situation does not get any worse.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Sat, 19 May 2001 19:46:41 GMT Raw View
nickt@kipling.aus.deuba.com (Nick Thurn) wrote (abridged):
> > typedef map<string, int, hash_table> MyMap;
>
> Agree with your comment on map however a nit: map and hash_table are
> not equivalent. I'm thinking equal_range, upper_bound and such.
Indeed. If map were the higher-level abstraction its name implies, such
methods would not belong in it. They would belong in rb_tree.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: remove.haberg@matematik.su.se (Hans Aberg)
Date: Sat, 19 May 2001 19:48:35 GMT Raw View
In article <memo.20010518104841.24285A@brangdon.madasafish.com>,
brangdon@cix.co.uk wrote:
> It's important to distinguish functions which change logical
>state from those which don't. "Set" (or similar) suffices; we don't need
>"get" or "do" also.
Functions that do not alter a state are called "pure", whereas functions
that are known to alter a state may be called "mutative". There is a
grey-zone: If one has an expression of functions that where some are
mutative, it is possible that their state altering cancel out; so the
resulting combination might be pure.
Further, one may want that some state-altering should be neglected in
determining what is pure and mutable: For example, a class may make use of
a ref count that alters in a copy constructor, even though one normally
would want that copy constructor to be regarded as pure.
It appears to be more important to know that a function is pure than that
it is to know that it is mutative, as in the former case the compiler may
be able to improve its static analysis: For example, in functional
languages, if one knows an expression is made up of pure components, one
can rearrange the computational order like in Church's (mathematical)
lambda calculus, and this can be used to do optimizations.
So it may happen that one should add a keyword or property "pure" to C++,
which can be used for compiler optimizations. The ideal would be that this
would a property somehow automatically inferred, but this may not be
possible, so it may end up as a keyword instead that can be entered by
hand.
Or a combination of this: Some functions can be automatically inferred to
be pure, but in some opther cases that may not be possible. So one is
allowed to add the keyword "pure" so that the compiler knows that it is Ok
to rearrange its computation order relative other pure functions (if it
does not alter the logical dependencies).
Hans Aberg * Anti-spam: remove "remove." from email address.
* Email: Hans Aberg <remove.haberg@member.ams.org>
* Home Page: <http://www.matematik.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Dietmar Kuehl <dietmar_kuehl@yahoo.com>
Date: Sat, 19 May 2001 20:33:16 GMT Raw View
Hi,
Dennis Yelle wrote:
> Wow! You sure have a different view of the STL than I do.
That's likely. Apparently, I'm one of a fairly small bunch
considering the containers to be only examples. However, from
a generic programming point of view that's about what they are:
Just examples to which the generic algorithms can be applied and
which can be implemented in terms of those algorithms.
> From my perspective, the containers are central.
In the context of an application, you are probably manipulating
containers using algorithms for this. Although the containers are
useful as packaged, you might want to use slightly modified
containers providing additional capabilities. The key here is that
you can just create them eg. by using one of the existing
containers and providing a thin wrapper or by hacking up a new one.
> You must be a much better programmer than I am if you
> can write map in 1/2 of a day.
I haven't claimed that I can do so with the current standard
template library! All I said that it is possible to hack up a map
in half a day with the right algorithms being in place: Given
algorithms operating on trees (however the underlying concepts look
like), it is pretty simple to create a map because all what is to
be done is to bundle up those algorithms to do the right thing.
Coming up with the right concepts eg. for trees is the actual hard
part but this is probably not the business of application
programmers as it is not to hack up the corresponding algorithms.
However, once you have algorithms to traverse a tree, insert or
remove elements from a tree, etc. something like a map is pretty
easy to be done.
> On the other hand, most of the std:: algorithms are so simple
> that it is easier and faster for me to write my own
> than it is for me to find the one I want in the documentation.
... and you will end up with a rather inferior application compared
to one which would have used all those algorithms! Yes, 'std::find()'
looks pretty simple but is it really? ... or can it be improved? You
might be surprised how much even such a simple algorithm can be
improved! Inside this trivial algorithm you might find loop unrolling
(can give a factor of two or more for certain types assuming the
comparison is pretty cheap), dealing of segmented containers (can
give an even bigger factor eg. on 'std::deque'), bypassing of
unneeded operations (eg. directly accessing a stream buffer's buffer
rather than going through the "official" interfaces), and so on.
Yes, a trivial implementation of these algorithms is, well, trivial.
A good one is more involved!
... and, BTW, once you got used to these algorithms it is also easier
and less error-prone to apply them. Sure, you need to learn about the
interfaces of these algorithms but it isn't that hard that it isn't
really usable. Also, I find it easier to use the algorithms than to
write even the desclarations of the iterators (note that you cannot
assume that an index works for typical containers because what is
currently a 'std::vector' might become a 'std::list' later).
> Not counting sort and next_permutation, can you give
> an example of a std:: algorithm that would take you more
> than 1/2 day to write?
A serious implementation of any algorithm in the standard library,
at least when implemented from scratch, takes more than half a day!
A trivial implementation normally takes just a few minutes or one
just delegating to an appropriate other algorithm like eg.:
template <typename InIt, typename OutIt>
OutIt copy(InIt beg, InIt end, OutIt to) {
return transform(beg, end, to,
identity<typename iterator_traits<OutIt>::value_type>());
}
Implementations of algorithms like "balanced_tree_insert()" would
probably also be more than trivial, not only due to the algorithmic
complexity but also due to the interface... Their use to create eg.
a map would be pretty simple...
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Sun, 20 May 2001 05:31:43 GMT Raw View
On Fri, 18 May 2001 14:16:55 GMT, brangdon@cix.co.uk (Dave Harris)
wrote:
> kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl) wrote (abridged):
> > Whatever you consider, note that it is at the wrong level: Containers
> > are the least important entities!
Of the concept called STL.
> I wasn't intending to restrict comments to the containers.
>
> That said, containers are the parts of the STL that I personally use
> most, so they are the most important to me.
And, likely, most users.
> Most algorithms are either
> so trivial they are hardly worth using, like for_each(), or else so
> esoteric that I rarely have occasion to use them, like
> next_permutation().
Yep. They just never do what I want. Or, did I not spend enough time
looking for the algorithm that does what I want?
> I am much more likely to write my own algorithms than
> my own containers.
I doubt it. I think you are unlikely to write any generic algorithm
which I would find useful. You are likely to write a little code that
solves your immediate problem.
It is usually much easier to write the solution than to adapt an
algorithm.
> > What is more interesting is the concept of iterators: These are the
> > entities whose interface is important to the standard library.
>
> Agreed. I have occasionally written my own iterators, too. I found it
> fairly awkward because what I really wanted was not an iterator, but a
> sequence. Hence my suggestion to make sequences more explicit.
What you wanted was a solution to an application problem. You did not
want an iterator that fit into the framework of the STL.
Two different views. Maybe STL is dead because all of the semi-useful
algorithms have been written and most of us have no use for most of
them. Almost all of the algorithms are really just implementation
details of the few really useful algorithms. The most commonly
requested algorithm is erase_if and it can not be implemented in the
framework of the STL.
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.research.att.com/~austern/csc/faq.html ]
Author: "Dean Roddey" <droddey@charmedquark.com>
Date: Sun, 20 May 2001 10:45:27 GMT Raw View
> > (4) Separate string into mutable and immutable forms. Immutable strings
> > support efficient copying; they can share parts of their representation
> > without bothering with copy-on-write. Mutable strings support efficient
> > editing. They don't need to be sharable.
>
I think that Java has proven that this is a false economy, and in fact one
of the biggest performance pigs in the Java world that a lot of work has to
be done to get around. Perhaps it could be implemented a bit more
intelligently, but otherwise I'd say its a loss overall except in very
specific circumstances (which are the ones always used to argue for them.)
-------------------------
Dean Roddey
The CIDLib C++ Frameworks
Charmed Quark Software
droddey@charmedquark.com
http://www.charmedquark.com
"Why put off until tomorrow what you can
put off until the day after tomorrow?"
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Sun, 20 May 2001 10:52:06 GMT Raw View
On Sat, 19 May 2001 20:33:16 GMT, Dietmar Kuehl
<dietmar_kuehl@yahoo.com> wrote:
> Dennis Yelle wrote:
> > Wow! You sure have a different view of the STL than I do.
>
> That's likely. Apparently, I'm one of a fairly small bunch
> considering the containers to be only examples. However, from
> a generic programming point of view that's about what they are:
> Just examples to which the generic algorithms can be applied and
> which can be implemented in terms of those algorithms.
I don't think so. Your generic algorithms do not work. See below.
> > From my perspective, the containers are central.
>
> In the context of an application, you are probably manipulating
> containers using algorithms for this. Although the containers are
> useful as packaged, you might want to use slightly modified
> containers providing additional capabilities. The key here is that
> you can just create them eg. by using one of the existing
> containers and providing a thin wrapper or by hacking up a new one.
Nope. Your containers have algorithms which are useless without the
container.
> > You must be a much better programmer than I am if you
> > can write map in 1/2 of a day.
>
> I haven't claimed that I can do so with the current standard
> template library! All I said that it is possible to hack up a map
> in half a day with the right algorithms being in place: Given
> algorithms operating on trees (however the underlying concepts look
> like), it is pretty simple to create a map because all what is to
> be done is to bundle up those algorithms to do the right thing.
Here is the problem. An rb-tree is not a tree. It is a low level
container with a bunch of algorithms (member functions) defined on
it to do the job of being an associative container. Given a
container needed to implement map, it is trivial.
> Coming up with the right concepts eg. for trees is the actual hard
> part but this is probably not the business of application
> programmers as it is not to hack up the corresponding algorithms.
That kind of low level container is useless without algorithms and
the algorithms can not exist without the container.
> However, once you have algorithms to traverse a tree, insert or
> remove elements from a tree, etc. something like a map is pretty
> easy to be done.
Not at all. A tree is almost useless. A binary search tree comes
closer. It is still a non-trivial exercise to convert a binary
search tree to a balanced binary search tree. Then there is a
container which can be used to implement a map. There are no
algorithms which operate on binary search trees in the library.
> > On the other hand, most of the std:: algorithms are so simple
> > that it is easier and faster for me to write my own
> > than it is for me to find the one I want in the documentation.
>
> ... and you will end up with a rather inferior application compared
> to one which would have used all those algorithms! Yes, 'std::find()'
> looks pretty simple but is it really? ... or can it be improved? You
> might be surprised how much even such a simple algorithm can be
> improved! Inside this trivial algorithm you might find loop unrolling
> (can give a factor of two or more for certain types assuming the
> comparison is pretty cheap), dealing of segmented containers (can
> give an even bigger factor eg. on 'std::deque'), bypassing of
> unneeded operations (eg. directly accessing a stream buffer's buffer
> rather than going through the "official" interfaces), and so on.
> Yes, a trivial implementation of these algorithms is, well, trivial.
> A good one is more involved!
That's nice for an implementer trying to sell a product. Of little
use to a programmer trying to solve a problem. Optimization is the
last step.
> ... and, BTW, once you got used to these algorithms it is also easier
> and less error-prone to apply them. Sure, you need to learn about the
> interfaces of these algorithms but it isn't that hard that it isn't
> really usable. Also, I find it easier to use the algorithms than to
> write even the desclarations of the iterators (note that you cannot
> assume that an index works for typical containers because what is
> currently a 'std::vector' might become a 'std::list' later).
Agreed. Now you are talking about algorithms. Most are trivial.
> > Not counting sort and next_permutation, can you give
> > an example of a std:: algorithm that would take you more
> > than 1/2 day to write?
Try rotate specialized for each of the forward+ iterators. No fair
peeking. ;)
> A serious implementation of any algorithm in the standard library,
> at least when implemented from scratch, takes more than half a day!
> A trivial implementation normally takes just a few minutes or one
> just delegating to an appropriate other algorithm like eg.:
>
> template <typename InIt, typename OutIt>
> OutIt copy(InIt beg, InIt end, OutIt to) {
> return transform(beg, end, to,
> identity<typename iterator_traits<OutIt>::value_type>());
> }
Sorry, identity is not part of the standard library. But, transform
was trivial anyway.
> Implementations of algorithms like "balanced_tree_insert()" would
> probably also be more than trivial, not only due to the algorithmic
> complexity but also due to the interface... Their use to create eg.
> a map would be pretty simple...
Yep! Balanced tree is a container not an algorithm.
It took me less than a day (I get slower with age) to convert the SGI
rb-tree to an AVL-tree. All of the petty stuff was reusable, but none
of it is part of the standard library, and it is all related to the
container. Morphing a container is easy. Writing a generic algorithm
is much harder.
Almost everything that you said supports containers being the central
part of STL with the algorithms being nothing more than a failed
attempt at genericity.
Please try again as an STL user, not implementer. What good are the
algorithms? They don't work on map and they do not help implement map.
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.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Sun, 20 May 2001 20:06:34 GMT Raw View
jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> > I am much more likely to write my own algorithms than
> > my own containers.
>
> I doubt it. I think you are unlikely to write any generic algorithm
> which I would find useful. You are likely to write a little code that
> solves your immediate problem.
Well, I'm unlikely to make it more generic than it needs to be. I'd call
it an algorithm even if it wasn't a generic algorithm, and a container
even if it wasn't a generic container.
> > Agreed. I have occasionally written my own iterators, too. I found
> > it fairly awkward because what I really wanted was not an iterator,
> > but a sequence. Hence my suggestion to make sequences more explicit.
>
> What you wanted was a solution to an application problem. You did not
> want an iterator that fit into the framework of the STL.
Actually, I did. I didn't want my iterators to be gratuitously different
from STL ones. I felt maintenance programmers would be surprised if they
couldn't use my iterators with std::find() etc. This meant I tried to use
STL conventions, such as the [first, last) half-open range, even though
it wasn't really appropriate.
> Two different views. Maybe STL is dead because all of the semi-useful
> algorithms have been written and most of us have no use for most of
> them.
I think the problem is the cost/benefit ratio. The costs of algorithms
are high because C++ doesn't support closures/functors well. It is
simpler to write a for-loop than to use find().
The benefits are low because iterators are usually at the wrong level of
granularity. Sequences would often be better, and containers would
sometimes be better still. Using find() on iterators does not gain me
very much over using a for-loop on iterators. Using map::find() does gain
me a lot.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Dietmar Kuehl <dietmar_kuehl@yahoo.com>
Date: Sun, 20 May 2001 23:36:58 CST Raw View
Hi,
John Potter wrote:
> I don't think so. Your generic algorithms do not work. See below.
Hm, looks like you are in bad mood due to some problem or you are
playing devils advocate... Anyway, here we go:
> > In the context of an application, you are probably manipulating
> > containers using algorithms for this. Although the containers are
> > useful as packaged, you might want to use slightly modified
> > containers providing additional capabilities. The key here is that
> > you can just create them eg. by using one of the existing
> > containers and providing a thin wrapper or by hacking up a new one.
>
> Nope. Your containers have algorithms which are useless without the
> container.
Sure, the algorithms need a sequence (or whatever the underlying
structure is) to work on. The point is, however, that you can easily
create new containers and the algorithms ready operate on the new
containers. If the user's algorithm operate on a reasonable abstracted
data structure in a generic fashion, this also applies to the users
code. That is, you can easily exchange containers and, what is
equally important, all you have to create for your containers is the
containment stuff and element access but no algorithms. The latter are
readily there which makes it viable to just hack up a new container.
> Here is the problem. An rb-tree is not a tree. It is a low level
> container with a bunch of algorithms (member functions) defined on
> it to do the job of being an associative container. Given a
> container needed to implement map, it is trivial.
I disagree. The entities on which tree algorithms (which are, that is
obvious, not part of the standard C++ library but probably should be
available) are nodes and, possibly, subtrees. A node for a binary tree
(for general it is probably somewhat different) is probably something
providing access to a left child and a right child including an
indication whether there is such a child and the possibility to
change these nodes. Probably, the algorithms would not operate on nodes
directly but rather on corresponding iterators and something like
property accessor to avoid prescribed names. Also, some algorithms
might need a parent of a node, also with the indication on whether it
is set. Other can probably go without.
Now, given such a basic abstraction, we can create a "tree_find()"
algorithm which, given a node and a binary predicate, searches the
tree for an element, assuming that the nodes are inserted into this
tree such that a typical search tree property is fulfilled. The
interesting part is probably the return from this function: If the
element is there, it should provide the position of the element.That's
the easy part. The interesting part is the failure case because in this
case the failure has to be indicated and but probably the position has
to be retained to allow usage of the position for an insertion
operation. A possible approach is a 'std::pair<state, iterator>' where
the state indicates 'found', 'left', or 'right' with the latter two
indicating on which side of the node pointed to by the iterator a new
element would have to be added.
A "tree_insert()" function would just take a parent and a child node
plus an indication on which side of the parent the child is to be
added. No balancing so far. If balancing is desired, I can imagine
basically two different appraoches:
- There is a set of function corresponding to the balancing mechanism,
like eg. "rb_tree_insert()", "avl_tree_insert()",
"splay_tree_insert()" and likewise for other balancing approaches.
- The node might have a trait which indicates the balancing approach.
That is, depending on the traits defined, "tree_insert()" does
different things.
However, "tree_insert()" does not search for an insert position
because in general it has no idea that the tree is a search tree or
something like this. This is what "tree_find()" is for. The insertion
methods would, however, retain an important property, namely that
even if some balancing is done, an in-order traversal of the nodes
does not change (that's the important property for balancing trees
which is taken advantage of by search trees). Of course, to balance
the tree would use appropriate "rotate()" functions which in turn get
the corresponding nodes as arguments.
There are probably more algorithms operating on trees, eg.
"tree_remove()". Also, there are probably certain iterators which
provide a sequence view of the tree, eg. an in-order iterator, a
pre-order iterator, a post-order iterator, and a level-by-level
iterator.
However, so far I haven't seen any container! There are nodes, that's
true, but these are not containers. These are more the elements which
make into a "tree container" or which are the entities in a map. The
tree algorithms do not care about the container. They just deal with
nodes...
> Not at all. A tree is almost useless. A binary search tree comes
> closer. It is still a non-trivial exercise to convert a binary
> search tree to a balanced binary search tree. Then there is a
> container which can be used to implement a map. There are no
> algorithms which operate on binary search trees in the library.
Note that we are talking about a "new STL" here! Yes, there are
neither tree algorithms nor the concepts defined in the current
STL. Maybe a "new STL" should have them: I think this could be
useful. How useful I'm not sure but obviously it can be used to
implement things like the current map, set, etc. If that's about
it, there is not much use in trees but I have sometimes seen request
for trees to be in the library...
[paragraph on optimizing algorithms removed]
> That's nice for an implementer trying to sell a product. Of little
> use to a programmer trying to solve a problem. Optimization is the
> last step.
However, if all you have to do to get an optimized version is to apply
an algorithm which is possibly even easier used than a hand crafted
version (I personally dislike to write terms like
'typename Container::const_iterator it = my_container.begin()'), then
there is nothing wrong with using the optimized version. ... or at
least getting the optimized version when turning on optimization for
the compiler.
> > ... and, BTW, once you got used to these algorithms it is also easier
> > and less error-prone to apply them. Sure, you need to learn about the
> > interfaces of these algorithms but it isn't that hard that it isn't
> > really usable. Also, I find it easier to use the algorithms than to
> > write even the desclarations of the iterators (note that you cannot
> > assume that an index works for typical containers because what is
> > currently a 'std::vector' might become a 'std::list' later).
>
> Agreed. Now you are talking about algorithms. Most are trivial.
Which I haven't disputed. However, good implementation of even these
trivial algorithms is non-trivial. That's what the paragraph on
optimization was all about...
> > A serious implementation of any algorithm in the standard library,
> > at least when implemented from scratch, takes more than half a day!
> > A trivial implementation normally takes just a few minutes or one
> > just delegating to an appropriate other algorithm like eg.:
> >
> > template <typename InIt, typename OutIt>
> > OutIt copy(InIt beg, InIt end, OutIt to) {
> > return transform(beg, end, to,
> > identity<typename iterator_traits<OutIt>::value_type>());
> > }
>
> Sorry, identity is not part of the standard library. But, transform
> was trivial anyway.
Again, we are talking about a "new STL" and I figure that 'identity'
as well as some forms of compose and some other useful functors will
almost certainly make it into such a library...
> > Implementations of algorithms like "balanced_tree_insert()" would
> > probably also be more than trivial, not only due to the algorithmic
> > complexity but also due to the interface... Their use to create eg.
> > a map would be pretty simple...
>
> Yep! Balanced tree is a container not an algorithm.
A balanced tree is, indeed, a container. The operations used to
maintain the nodes of such a container are, IMO, algorithms. ... and
with something like the sketches concepts above, these can be
implemented
in a generic fashion.
> Almost everything that you said supports containers being the central
> part of STL with the algorithms being nothing more than a failed
> attempt at genericity.
I don't think so: Indeed, the current STL algorithms need a sequence to
operate on and things like the tree algorithms need linked nodes to
operate on. That doesn't make the algorithms useless. Also, even if you
just take the few not-so-trivial algorithms (like 'sort()' and maybe
'lower_bound()') it is an advantage to have the applicable to basically
any container supporting random access, not just those available from
some particular library.
> Please try again as an STL user, not implementer. What good are the
> algorithms? They don't work on map and they do not help implement map.
It took me quite a while to really start using the STL algorithms all
over and, indeed, lots parts of my implementation don't use them at
all. That is an error which I want to correct! ... and even in my day
to day application code I'm using the algorithms, eg. because I like
the possibility to switch to a different container wihtout rewriting
my code and I really dislike to get at the underlying types: This makes
the lines so long... :-)
No doubt, the STL is not at all perfect but many of the things which
are wrong can be corrected. Actually, I think Valentines comment is
right to the point: The STL is not STL-like enough!
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Dennis Yelle <dennis51@jps.net>
Date: Sun, 20 May 2001 23:37:38 CST Raw View
John Potter wrote:
[...]
[I wrote:]
> > > Not counting sort and next_permutation, can you give
> > > an example of a std:: algorithm that would take you more
> > > than 1/2 day to write?
>
> Try rotate specialized for each of the forward+ iterators. No fair
> peeking. ;)
It turns out that I rarely use rotate. I do seem to remember
using it once, but I cannot now recall why.
I am not sure exactly what you mean by "forward+ iterators".
I will assume that you mean: forward, bidirectional, and random
iterators.
Well, I looked a long time ago and saw that rotate is just
(in pseudo code) this:
rotate( x, y, z)
{
reverse( x, y);
reverse( y, z);
reverse( x, z);
}
But, of course, that only works for bidirectional and random access
iterators. Which is strange in a way, because it is easy to
reverse a singly linked list, like this (pseudo code):
reverse_slist( x )
{
y = 0;
for(;;) {
if ( x == 0 )
return y;
swap( y, x->next);
if ( y == 0)
return x;
swap( x, y->next);
}
}
But, then, slist is not part of the standard.
So why does the standard have forward iterator?????
Anyway, to complete the answer to your question:
My instinct, for forward iterators, would be to "just do it",
which would lead to:
// d1 and d2 are zero on the initial call, but are
// nonzero for the (tail) recursive calls.
template< class It>
void rotate_fwd_iterator( It x, It y, It z, size_t d1 = 0, size_t d2 = 0)
{
if ( x == y || y == z )
return;
It y0 = y;
if ( ! d1 )
d1 = distance( x, y);
if ( ! d2 )
d2 = distance( y, z);
while( y!=z) {
swap( *x, *y);
++x;
++y;
}
size_t nd1, nd2;
if ( d2 < d1) {
y = y0;
nd1 = d1 - d2;
nd2 = d1;
} else {
size_t d = d2 % d1;
if ( 0 == d )
return;
y = x;
advance( y, d1 - d);
nd1 = d1 - d;
nd2 = d;
}
rotate_fwd_iterator( x, y, z, nd1, nd2); // tail recursion.
}
I don't really like that advance() in there.
It is OK if complexity is only concerned with the
number of swap() calls, but using advance like that seems
to be cheating the complexity guarantee.
So, I would probably specialize it for slist as follows:
template< class Fi>
void rotate_slist( Fi x, Fi y, Fi z)
{
if ( x == y || y == z )
return;
Fi pre_z = y;
for(;;) {
Fi t = pre_z;
if ( ++t == z)
break;
pre_z = t;
}
Fi x0 = x;
while( x != y ) {
swap( *x, *y);
++x;
}
//typedef typeof( *x) junk; // gcc does not like
//slist< junk > temp; // these two lines?!?!?
// An implementer would have a legal way to do what
// the following two lines actually do.
slist< int > temp;
temp.splice_after( x0, y, pre_z);
}
See http://www.sgi.com/tech/stl/Slist.html
for an explanation of the constant time splice_after.
Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Mon, 21 May 2001 14:57:31 GMT Raw View
dietmar_kuehl@yahoo.com (Dietmar Kuehl) wrote (abridged):
> Apparently, I'm one of a fairly small bunch considering the
> containers to be only examples. However, from a generic
> programming point of view that's about what they are:
> Just examples to which the generic algorithms can be applied and
> which can be implemented in terms of those algorithms.
There's a difference between producing a "generic" library as an academic
exercise, and producing a base standard library for a language. From the
former point of view, containers may not be interesting. From the latter,
it is surely important that C++ have a good set of containers.
> Yes, 'std::find()'
> looks pretty simple but is it really? ... or can it be improved? You
> might be surprised how much even such a simple algorithm can be
> improved! Inside this trivial algorithm you might find loop unrolling
> (can give a factor of two or more for certain types assuming the
> comparison is pretty cheap), dealing of segmented containers (can
> give an even bigger factor eg. on 'std::deque'), bypassing of
> unneeded operations (eg. directly accessing a stream buffer's buffer
> rather than going through the "official" interfaces), and so on.
So far this has been more theory than practice. We cannot just
specialise:
template <typename T>
deque<T>::iterator find( deque<T>::iterator,
deque<T>::iterator, const T& );
as easily as we can specialise:
template <typename T>
deque<T>::iterator find( deque<T> &, const T & );
I know the former is possible, but it's a bit like a dog walking on its
hind legs. Iterators place a layer of abstraction between containers and
algorithms, which just gets in the way when one wants an algorithm
specialised on a container. Yes, the barrier can be circumvented, but
it's hard work. Endless opportunities to demonstrate one's cleverness.
The upshot is that we rarely bother with specialised algorithms, and so
don't get much benefit from using algorithms at all.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: jk@steel.orel.ru (Eugene Karpachov)
Date: Mon, 21 May 2001 18:41:48 GMT Raw View
Sun, 20 May 2001 20:06:34 GMT Dave Harris =CE=C1=D0=C9=D3=C1=CC:
>I think the problem is the cost/benefit ratio. The costs of algorithms=20
>are high because C++ doesn't support closures/functors well. It is=20
Yes, that's it. I'm surprized that (almost) nobody is talking about
closures in this brain-storming; for me, it's the most important possible
change.
--=20
jk
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Hans Bos" <hans.bos@xelion.nl>
Date: Mon, 21 May 2001 19:11:29 GMT Raw View
Hello,
Dietmar Kuehl <dietmar_kuehl@yahoo.com> wrote in message news:3B081B7A.3AE47F24@yahoo.com...
> Hi,
> ....
> Sure, the algorithms need a sequence (or whatever the underlying
> structure is) to work on. The point is, however, that you can easily
> create new containers and the algorithms ready operate on the new
> containers. If the user's algorithm operate on a reasonable abstracted
> data structure in a generic fashion, this also applies to the users
> code. That is, you can easily exchange containers and, what is
> equally important, all you have to create for your containers is the
> containment stuff and element access but no algorithms. The latter are
> readily there which makes it viable to just hack up a new container.
But how generic is STL? It requires that the underlying data structure behaves like a sequence.
Trees are no sequences, but because a map must behave like a sequence it is more complicated then it needs to be (e.g. a map object must keep a reference to the lowest and highest value in the tree and to implement operations like delete in constant time, every node must be in a linked list).
I don't see an obvious way to view a graph (where a node can have zero or more connections to other nodes) as a sequence. But I may want to call functions like for_each and find_if to iterate over the graph, but I don't care much about the order (and you can't describe a subgraph with a begin-node and an en-node).
>
> > Here is the problem. An rb-tree is not a tree. It is a low level
> > container with a bunch of algorithms (member functions) defined on
> > it to do the job of being an associative container. Given a
> > container needed to implement map, it is trivial.
>
> I disagree. The entities on which tree algorithms (which are, that is
> obvious, not part of the standard C++ library but probably should be
> available) are nodes and, possibly, subtrees. A node for a binary tree
> (for general it is probably somewhat different) is probably something
> providing access to a left child and a right child including an
> indication whether there is such a child and the possibility to
> change these nodes. Probably, the algorithms would not operate on nodes
> directly but rather on corresponding iterators and something like
> property accessor to avoid prescribed names. Also, some algorithms
> might need a parent of a node, also with the indication on whether it
> is set. Other can probably go without.
>
> ...
You describe here some kind of tree_iterator, that is incompatible with the standard (sequence) iterators.
You can't use the standard algorithms on tree_iterator, but you can define new versions of functions like for_each that operate on tree_iterators.
I think this is better than forcing everything into sequences.
But it is not easy to replace (sequence) iterators with tree iterators (e.g. when you replace a sequence with a tree in your code).
When you have functions (like for_each) that also work on the containter type in stead of the iterators it will become easier to replace a sequence with a tree.
Greetings,
Hans Bos.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Mon, 21 May 2001 19:30:42 GMT Raw View
On Sun, 20 May 2001 23:37:38 CST, Dennis Yelle <dennis51@jps.net> wrote:
> John Potter wrote:
> [...]
> [I wrote:]
> > > > Not counting sort and next_permutation, can you give
> > > > an example of a std:: algorithm that would take you more
> > > > than 1/2 day to write?
> >
> > Try rotate specialized for each of the forward+ iterators. No fair
> > peeking. ;)
>
> It turns out that I rarely use rotate. I do seem to remember
> using it once, but I cannot now recall why.
Which supports your point that it is the containers not the algorithms
which are important.
> I am not sure exactly what you mean by "forward+ iterators".
> I will assume that you mean: forward, bidirectional, and random
> iterators.
Yes, exactly.
> Well, I looked a long time ago and saw that rotate is just
> (in pseudo code) this:
>
> rotate( x, y, z)
> {
> reverse( x, y);
> reverse( y, z);
> reverse( x, z);
> }
>
> But, of course, that only works for bidirectional and random access
> iterators. Which is strange in a way, because it is easy to
> reverse a singly linked list, like this (pseudo code):
>
> reverse_slist( x )
> {
> y = 0;
> for(;;) {
> if ( x == 0 )
> return y;
> swap( y, x->next);
> if ( y == 0)
> return x;
> swap( x, y->next);
> }
> }
>
> But, then, slist is not part of the standard.
> So why does the standard have forward iterator?????
Because the STL is algorithms. Forward iterator is a concept used to
specify the requirements of an algorithm. Slist::iterator is an
example of a forward iterator, but forward iterator is not just an
slist iterator.
Rotate is my favorite example of a true STL algorithm. It is O(N) for
forward iterators. It is specialized for bidirectional iterators to
save some time by reducing the housekeeping overhead. If swap is
considered three assignments, it may be specialized for random access
iterators to reduce the number of assignments at the expense of some
added housekeeping overhead.
Your forward iterator implementation was not bad. With a little
housekeeping, it can be done as a single loop. Whether that is
better or not may depend on the platform. The assumption is that
some added iterator compares and assignments will be cheaper than
the pointer chases in advance and distance.
It could have been made a list member where it would be a simple
O(1) splice, but was not. Like you said, nobody uses it. :)
Could it be overloaded for list<T>::iterator?
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.research.att.com/~austern/csc/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Mon, 21 May 2001 19:31:52 GMT Raw View
On Sun, 20 May 2001 23:36:58 CST, Dietmar Kuehl
<dietmar_kuehl@yahoo.com> wrote:
> Hi,
> John Potter wrote:
> > I don't think so. Your generic algorithms do not work. See below.
>
> Hm, looks like you are in bad mood due to some problem or you are
> playing devils advocate... Anyway, here we go:
Neither, we are just not talking about the same thing.
> > > In the context of an application, you are probably manipulating
> > > containers using algorithms for this. Although the containers are
> > > useful as packaged, you might want to use slightly modified
> > > containers providing additional capabilities. The key here is that
> > > you can just create them eg. by using one of the existing
> > > containers and providing a thin wrapper or by hacking up a new one.
> >
> > Nope. Your containers have algorithms which are useless without the
> > container.
>
> Sure, the algorithms need a sequence (or whatever the underlying
> structure is) to work on. The point is, however, that you can easily
> create new containers and the algorithms ready operate on the new
> containers. If the user's algorithm operate on a reasonable abstracted
> data structure in a generic fashion, this also applies to the users
> code. That is, you can easily exchange containers and, what is
> equally important, all you have to create for your containers is the
> containment stuff and element access but no algorithms. The latter are
> readily there which makes it viable to just hack up a new container.
The STL sales pitch: It is extensible. Just create a new algorithm
which operates on the existing iterator categories and it will work
with the existing containers. Just create a new container and provide
iterators in the existing categories and it will work with the
existing algorithms.
Dietmar's pitch: The concepts behind the STL are reusable to create
new containers which do not work with the old algorithms, and new
algorithms which do not work with the old containers. The new
algorithms and containers work together using new iterators which
do not fit in the old categories.
The beauty of STL is gone. Maybe because it was only skin deep.
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.research.att.com/~austern/csc/faq.html ]
Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Fri, 18 May 2001 05:46:39 GMT Raw View
Marcin 'Qrczak' Kowalczyk wrote:
>
> Wed, 16 May 2001 17:06:20 GMT, Daniel Frey <daniel.frey@aixigo.de> pisze:
>
> > Hm, how about:
> >
> > int entry( int i = 0 ) const { return entries[i]; }
> >
> > void entry( int i, int e ) { entries[i] = e; }
> > void entry( int e ) { entries[0] = e; }
>
> How would you get 5th entry of a non-const object?
By calling entry(5), the same as for a const object. You can call const
methods using non-const objects. What's not allowed is calling non-const
methods on const objects.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Fri, 18 May 2001 05:46:59 GMT Raw View
Heinz Huber wrote:
>
> Daniel Frey wrote:
...
> > Hm, how about:
> >
> > int entry( int i = 0 ) const { return entries[i]; }
> >
> > void entry( int i, int e ) { entries[i] = e; }
> > void entry( int e ) { entries[0] = e; }
> >
> > But I anyway consider it bad style (personal opinion) to provide a
> > default parameter that way...
>
> I wouldn't do that. I'm not even sure whether it's legal to overload on return
> type when using different const qualifications. Furthermore, you wouldn't be
> able to call the getter on a non-const object without casting it.
It's not legal to overload on return type, regardless of const
qualification. It is legal, however, to overload on const qualification.
For purposes of overload resolution, "a member function is considered to
have an extra parameter, call the _implicit object parameter_, which
represents the object for which the member function has been called."
(13.3.1p2) When a member function is cv-qualified, what that really
means is that the implicit object parameter has that qualification.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl)
Date: Fri, 18 May 2001 05:49:41 GMT Raw View
Hi,
Dave Harris (brangdon@cix.co.uk) wrote:
: Suppose we were designing a template library from scratch, without much
: concern for backwards compatibility. Suppose it was going in a new
: namespace, say stl:: instead of std::. What would we do differently?
Whatever you consider, note that it is at the wrong level: Containers
are the least important entities! Consider the standard containers as
examples which might be a nice aid and even handy for some uses. If
they aren't, just create your own container. That is the core idea of
the whole stuff: If you want a new container, just create one and only
consider the containment aspect of the container. This is made up of
the capability to store and access the elements.
What is more interesting is the concept of iterators: These are the
entities whose interface is important to the standard library. The
actual interface of the containers is more or less unimportant except,
may be, for consistency sake. The interface of the iterators is
important. Why is that?
The heart of the whole thing are the algorithm (which should better be
named "solvers" because strictly the algorithms aren't specified), the
entities which are "hard" to create in the first place: These are
already done and applicable to the containers written by the user -
without even knowing how these containers look like! This is because
the fundamental basis of the standard library:
The overall basis of the standard library, the single most important
entities in the standard library, are the "concepts" or "requirements"
(the standard uses the latter term but the former describes more
precisely what this stuff is all about) - actually, these entities
aren't [necessarily] represented explicitly at all! They are just
implicit in how the algorithms are implemented: An algorithm is
applicable to all data structures/entities/{whatever you want to call
them} which follow the necessary concepts.
If you want containers without allocators, create them! An average
container takes maybe half a day work. Even complex containers don't
take much longer, at least not if the appropriate algorithms are
available. See eg. the thread on trees: if there are algorithms coping
with balanced trees readily available, something like "map" is easy to
create.
To me, the real problem of the standard library is the use of the
course grained abstractions. For example, iterators are used for two
purposes at the same time, namely for position access and for
data/property access. This should, well IMO has to, be split up into
two separate concepts - solving a whole bundle of problems with the
current definition (eg. const_iterator vs. iterator and proxied
containers). ... but then, I'm often doing low-level work.
This leads to another observation: The standard library tries to unify
the view and the corresponding interfaces at a not too complex level
while still retaining maximum flexibility. The effect is that the
interfaces are too complex for certain uses while being to restrictive
for others. For example, on the side of "unnecessary" complexity people
generally refer to the separation of iterators into a pair describing a
sequence - while often overly complex, it is very convenient when
dealing with subranges as is the case eg. in the internals of the STL.
Using just a dereference operator to access elements is overly
restrictive: It basically "unnecessarily prohibits the use of proxied
containers.
Actually, this somewhat points into the definition of different
interfaces, suitable for different tasks:
- An "application level" interface which operates eg. on whole
containers. At this level "solvers" are used to achieve a specific
task like copying or sorting a container. It is implemented in terms
of
- An "advanced" interface which is basically more or less the current
interface. It might be reasonable to augment the current interface by
"algorithms" in addition to the "solvers": 'sort()' is a "solver" to
a specific problem ("sort this sequence"); 'mergesort()',
'quicksort(), 'bubblesort()' are [implementations of] "algorithms".
This in turn is implemented in terms of
- A "low level" interface which operates on fine grained concepts,
splitting all othogonal aspects like position and element access
into separate entities (eg. iterators and "property maps"; see the
Boost Graph Library or the article on "Data Access Templates" in C++
Report 9/7 (1997) for more details). At this level, only "algorithms"
are available.
At the application level, manipulations normally are in terms of
"containers" or, a little bit more general, "sequences" (there are
other application areas which operate in complete other terms not at
all covered by the standard library). This should be reflected by an
easy to use interface operating on containers. Where things are too
restrictive or turn out to be ineffecient, a user can fallback to the
next level, the "advanced" level: There is a specific problem with the
easy to use interface and thus more than just a basic fit all approach
is necessary. For fine tuning or implementation of higher level
facilities, eg. to supply a convenient interface, the "low level"
interface can be used.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl)
Date: Fri, 18 May 2001 05:52:07 GMT Raw View
Hi,
Andrei Alexandrescu (andrewalex@hotmail.com) wrote:
: I like your suggestions, they all make sense.
No doubt about that one: The all make sense in a specific context. They
don't make much sense in other contexts. However, IMO these are just
details which don't really affect the overall picture: The concepts on
which the algorithms are based are the important entities. The
containers? They are there, they are often handy but they are subject
of replacement by application specific, special tailored drop-ins.
: I'd make all member functions of all STL classes nonmember :oO.
Yes, I'm in favour of this one, too. There are, however, some problems
still to be resolved (... and others would just disappear), most
notably the "swap()" problem (how to provide a replacement version).
... and then, does it actually really matter? Yes, it would be nice to
have them as non-members but who case about the interface to containers
anyway? Don't shout "me!" - hopefully the moderators sort this out
anyway - yes, there are people who care about containers but my point
is really that containers are not really that important: Containers
were important to us for far too long and in all other languages I'm
aware of they are still pretty important. This does not change that the
details of containers don't matter at all in C++.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>
Date: Fri, 18 May 2001 07:45:04 GMT Raw View
Fri, 18 May 2001 05:46:39 GMT, James Kuyper Jr. <kuyper@wizard.net> pisze=
:
>> > int entry( int i =3D 0 ) const { return entries[i]; }
>> >
>> > void entry( int i, int e ) { entries[i] =3D e; }
>> > void entry( int e ) { entries[0] =3D e; }
>>=20
>> How would you get 5th entry of a non-const object?
>=20
> By calling entry(5), the same as for a const object.
This will call the non-const version (sorry, I'm not sure according
to which rule). And if it called the const version, you couldn't call
the non-const version. I should have asked: how would you distinguish
between getting and setting on a non-const object.
--=20
__("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
\__/
^^ SYGNATURA ZAST=CAPCZA
QRCZAK
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Al Grant" <tnarga@arm.REVERSE-NAME.com>
Date: Fri, 18 May 2001 07:50:55 GMT Raw View
"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3B046F36.8C234F99@wizard.net...
> Al Grant wrote:
> > If the default allocator is an empty class and the
> > container contains the allocator as a member (as in
> > P.J. Plauger's STL) then a container without an
> > allocator would be smaller.
>
> Why? There's no need for a container to keep a copy of the the
> allocator.
I know, SGI's STL doesn't. But Plauger's does and there
must be a reason for that. If it's not forbidden by the
standard then I can't be sure the container is not using
that technique, so in a portable program written to use
whatever STL is available, I save resources on average
by writing my own container or using the proposed
allocator-less container.
So the standard should either have allocator-less containers
or forbid implementers from making the allocator a member of
the container.
The same applies to O(1) size(). If you need it, you have
to write your own because STL doesn't guarantee it, and if
you don't need it, the overhead is just wasted. Surely you
don't want a situation where every substantial portable
program where performance is an issue ships with its own
"tuned" STL? Perhaps where benchmarks show runtimes of
O(n) or O(n**2) depending on which STL they use? Seems to
defeat the whole idea of STL.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: pdimov@mmltd.net (Peter Dimov)
Date: Fri, 18 May 2001 11:57:01 GMT Raw View
kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl) wrote in message news:<9e1umm$2bi$3@news.BelWue.DE>...
> Hi,
> Andrei Alexandrescu (andrewalex@hotmail.com) wrote:
>
> : I'd make all member functions of all STL classes nonmember :oO.
>
> Yes, I'm in favour of this one, too. There are, however, some problems
> still to be resolved (... and others would just disappear), most
> notably the "swap()" problem (how to provide a replacement version).
> ... and then, does it actually really matter? Yes, it would be nice to
> have them as non-members but who case about the interface to containers
> anyway? Don't shout "me!" - hopefully the moderators sort this out
> anyway - yes, there are people who care about containers but my point
> is really that containers are not really that important: Containers
> were important to us for far too long and in all other languages I'm
> aware of they are still pretty important. This does not change that the
> details of containers don't matter at all in C++.
They should not matter, but they currently do. Example: You have a
container of ints. Does it contain zero? [Efficiency is important.]
--
Peter Dimov
Multi Media Ltd.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Fri, 18 May 2001 12:14:40 GMT Raw View
Marcin 'Qrczak' Kowalczyk wrote:
>
> Fri, 18 May 2001 05:46:39 GMT, James Kuyper Jr. <kuyper@wizard.net> pisze:
>
> >> > int entry( int i = 0 ) const { return entries[i]; }
> >> >
> >> > void entry( int i, int e ) { entries[i] = e; }
> >> > void entry( int e ) { entries[0] = e; }
> >>
> >> How would you get 5th entry of a non-const object?
> >
> > By calling entry(5), the same as for a const object.
>
> This will call the non-const version (sorry, I'm not sure according
> to which rule). And if it called the const version, you couldn't call
> the non-const version. I should have asked: how would you distinguish
> between getting and setting on a non-const object.
You're right. I missed that point. That problem occurs because the
stored object has the same type as the index; in most cases, that
wouldn't be a problem, but a design like this would be unsuitable if the
stored type were a template parameter that could be set to 'int'.
That's one of the nasty things about template design; when you overload
you have to check for the possibility that some particular (possibly
obscure) choice of template parameters renders some of your overloads
ambiguous, or even worse, allows the wrong overload to be chosen.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Fri, 18 May 2001 12:14:34 GMT Raw View
Al Grant wrote:
>
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3B046F36.8C234F99@wizard.net...
> > Al Grant wrote:
> > > If the default allocator is an empty class and the
> > > container contains the allocator as a member (as in
> > > P.J. Plauger's STL) then a container without an
> > > allocator would be smaller.
> >
> > Why? There's no need for a container to keep a copy of the the
> > allocator.
>
> I know, SGI's STL doesn't. But Plauger's does and there
> must be a reason for that. If it's not forbidden by the
> standard then I can't be sure the container is not using
> that technique, so in a portable program written to use
> whatever STL is available, I save resources on average
> by writing my own container or using the proposed
> allocator-less container.
By that same logic, you should write your own version of virtually every
single library class and function. Every single one has an infinite
number of ways that implementors could implement it poorly, while still
conforming to the standard. By your logic, that means that portable code
must protect itself against that possibility by writing its own version.
Of course, that's not really adequate protection. An implementation
could also choose to insert a sleep(1) call into every assignment. The
only library functions you shouldn't override are the ones like
std::signal() that provide facilities that aren't available through the
C++ language (chs 1-16 of the standard) itself.
I can't say that you're wrong, but I've better uses for my own time. If
an implementation uses up extra space in the standard containers to
store the default allocator, that implementation is defective, in
precisely the same way that an implementation is defective if it inserts
unnecessary padding into a structure. If that defect is serious enough
that I notice it, I complain.
The standard should not dictate that level of detail about an
implementation. If you want tight control, write it yourself. The loose
way that the C++ standard is currently written gives implementors the
freedom to create quick-and-dirty, yet fully conforming, implementations
for a new platform, while allowing them to mature into highly optimized
implementations when time permits refinement. Excessively detailed
specification would prevent both ends of that spectrum; it would rule
out the quick approach. However, it would also often rule out the highly
optimized version, by specifying things that didn't need to be
specified, which happen to interfere with the optimization. The only
optimizations that you can guarantee aren't accidentally prohibited are
the ones that have already been thought of, and that's only a tiny
fraction of the possible optimizations.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Fri, 18 May 2001 14:16:55 GMT Raw View
kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl) wrote (abridged):
> Whatever you consider, note that it is at the wrong level: Containers
> are the least important entities!
I wasn't intending to restrict comments to the containers.
That said, containers are the parts of the STL that I personally use
most, so they are the most important to me. Most algorithms are either
so trivial they are hardly worth using, like for_each(), or else so
esoteric that I rarely have occasion to use them, like
next_permutation(). I am much more likely to write my own algorithms than
my own containers.
> What is more interesting is the concept of iterators: These are the
> entities whose interface is important to the standard library.
Agreed. I have occasionally written my own iterators, too. I found it
fairly awkward because what I really wanted was not an iterator, but a
sequence. Hence my suggestion to make sequences more explicit.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Pete Becker <petebecker@acm.org>
Date: Fri, 18 May 2001 14:28:08 GMT Raw View
"James Kuyper Jr." wrote:
>
> Al Grant wrote:
> >
> > If the default allocator is an empty class and the
> > container contains the allocator as a member (as in
> > P.J. Plauger's STL) then a container without an
> > allocator would be smaller.
>
> Why? There's no need for a container to keep a copy of the the
> allocator. The standard appears to say that it must, but all instances
> of std::allocator<> are equivalent, and there's not a single thing a
> program can do to detect the fact that each
> Container<T,std::allocator<T> > does not contain it's own copy of the
> allocator used to initialize it.
>
Library implementations are permitted to treat all allocators of the
same type as equivalent. They are not required to. Respecting
differences in instances makes containers more flexible, permitting
user-defined allocators with richer semantics.
--
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.research.att.com/~austern/csc/faq.html ]
Author: "TiTi" <titi_@skynet.be>
Date: Fri, 18 May 2001 16:42:17 GMT Raw View
Al Grant <tnarga@arm.REVERSE-NAME.com> schreef in berichtnieuws
9e0eoj$gjh$1@cam-news1.cambridge.arm.com...
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3B031A21.A5636386@wizard.net...
> > Radoslav Getov wrote:
> > > How about having 2 versions of the containers - one with allocators
and
> one
> > > without, instead one version with default allocator? This shouldn't
> break
> > > any existing code, I believe, and will be in the spirit of C/C++
(don't
> pay
> > > for what you don't need ;-).
> > And what method would the one defined without an allocator use to
> > allocate and deallocate needed memory? If it uses 'new' and 'delete',
> > how would such a container differ from Container<T,std::allocator<T> >,
> > which is precisely what Container<T> defaults to?
> If the default allocator is an empty class and the
> container contains the allocator as a member (as in
> P.J. Plauger's STL) then a container without an
> allocator would be smaller.
What to say to that; you're right *and* wrong.
> Of course, we could instead throw out the rule that
> says empty members must take up space.
You can always let your container class derive from the allocator class. If
it's an empty subobject, it will be optimized away (empty base class
optimization) and it won't take up any space.
TiTi
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Anthony Williams" <anthwil@nortelnetworks.com>
Date: Fri, 18 May 2001 16:42:02 GMT Raw View
"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3B04705E.93B9405E@wizard.net...
> Marcin 'Qrczak' Kowalczyk wrote:
> >
> > Wed, 16 May 2001 17:06:20 GMT, Daniel Frey <daniel.frey@aixigo.de>
pisze:
> >
> > > Hm, how about:
> > >
> > > int entry( int i = 0 ) const { return entries[i]; }
> > >
> > > void entry( int i, int e ) { entries[i] = e; }
> > > void entry( int e ) { entries[0] = e; }
> >
> > How would you get 5th entry of a non-const object?
>
> By calling entry(5), the same as for a const object. You can call const
> methods using non-const objects. What's not allowed is calling non-const
> methods on const objects.
But in the proposed signatures, "void entry(int e)" is used for non-const
objects instead of "int entry(int i) const", and "void entry(int e)" is not
an accessor.
Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Fri, 18 May 2001 16:44:50 GMT Raw View
jpotter@falcon.lhup.edu (John Potter) wrote (abridged):
> The associative containers are at a higher level than the sequences
> as are stack and queue.
>
> template <class Key, class Value, class Container = rb_tree> class map;
>
> However, that would require adding low level things like rb_tree,
> avl_tree, skip_list, and others to the standard.
That would be OK, if I can write:
typedef map<string, int, hash_table> MyMap;
My point here is that "map" is a general name which should be used for a
more general concept than the specific complexities of std::map.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Fri, 18 May 2001 16:44:18 GMT Raw View
daniel.frey@aixigo.de (Daniel Frey) wrote (abridged):
> I'm NOT counting the arguments!! I agree with you that this would be a
> very stupid idea. I indeed use a const and a non-const function to
> indicate what's the setter and what's the getter.
That doesn't work well because the "const" isn't visible at the point of
call. Also because it makes sense to call getters on both const and
non-const objects.
> Following your argumentation a function should not just have 'set'
> in its name if a value (or state?) is set, it should consequently
> have 'get' or 'do' in it's name for the other cases.
Not at all. It's important to distinguish functions which change logical
state from those which don't. "Set" (or similar) suffices; we don't need
"get" or "do" also.
> I have some experience with naming schemes and using
> 'set' isn't a good idea, really! :)
I have some experience with naming conventions, too.
> int entry( int i = 0 ) const { return entries[i]; }
> void entry( int e ) { entries[0] = e; }
Here we have 2 functions with the same names and argument lists. The
const/non-const difference is subtle:
Table table;
int x = table.entry( 0 );
does not do what it appears to do. In this case it is a compiler error,
but if the setter returned the old value, or a success/failure status, or
if the code was in a template, then the error would not be detected.
Also,
const Table &table;
// Much code.
table.entry( 0 );
If there is a large separation between the declaration and the use - for
example, if table is an instance variable declared in a header, and the
use is in an implementation file - it can be hard to remember exactly
what the declaration was. This code looks like it is setting something
called "entry" to 0, but it actually has no effect at all.
Imagine table was initially non-const, but, after writing a lot of code,
we thought a read-only version might be sufficient. So we change the
declaration. The compiler should warn about setters, not silently turn
them into getters!
These error situations may seem esoteric, but they highlight the real
problem, which is that the code does not make its intent clear. Humans
will get confused more often than the compiler.
> As long as you count arguments. Look at the 'const' instead and it'll
> become clearer!
But the "const" is not apparent at the point of call.
> It even helps to express what you mean by code (that can be checked
> by the compiler) instead of documentation (by adding set_ to
> an identifier). Even your example above shows how it works: You forgot
> the 'const' for the first function! :)
Of course, one should use "const" as well. That I did not do so for one
of the functions was merely an oversight, not part of my argument.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Al Grant" <tnarga@arm.REVERSE-NAME.com>
Date: Fri, 18 May 2001 16:48:13 GMT Raw View
"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3B050F6A.E120D1DA@wizard.net...
> > I know, SGI's STL doesn't. But Plauger's does and there
> > must be a reason for that. If it's not forbidden by the
> > standard then I can't be sure the container is not using
> > that technique, so in a portable program written to use
> > whatever STL is available, I save resources on average
> > by writing my own container or using the proposed
> > allocator-less container.
>
> By that same logic, you should write your own version of virtually every
> single library class and function.
It's not quite the same logic for functions. They
factor code so you get a code-size win (even more so
with dynamic linking). The price you pay is that they
may be over-general for a given application. Templates
don't do that. They should generate whatever code is
necessary to implement the specification and no more.
I take the point about different levels of optimisation,
but having an O(1) size is not an optimised way of
implementing a given specification, it's implementing
a different specification from the one in the Standard.
And while your argument about quick-and-dirty STLs may
mean you shouldn't forbid an allocator list class being
implemented with an allocator member if that's the only
way it can be gotten to work, it's not an argument
against providing an allocator-less list class.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Fri, 18 May 2001 16:48:56 GMT Raw View
bs@research.att.com (Bjarne Stroustrup) wrote (abridged):
> I happen to disagree. Not everyone hates allocators and they are not
> just unnecessary complexity. They are a useful concept. For
> example, they allow easy use of allocators specialized for a
> particular type.
The concept of allocators is useful, but it seems very closely related to
the concept of operator new(). For example, we can make a specialised
allocator which uses an arena or shared pool, and we can write a
specialised new, like:
void *operator new( size_t, pool_t );
which does the same.
I am learning from the responses on this point, but I am not yet assured
that C++ has found the ideal solution here. Maybe it is operator new()
that I really want to get rid of :-)
> I might be in favor of adding "reified sequences" (especially if they
> were called something less pretentious :-). But there is no chance
> of the 2-iterator versions disappearing. The iterator versions are
> more general, compose better, and there is a huge amount of code
> out there depending on it.
I don't see what can be done with an implicit pair that couldn't be done
with an explicit pair, so I don't follow your point about being more
general and composable.
I agree the old approach must be kept, even if a new approach is better.
Probably any new algorithms added should also support the old approach,
for consistency, even though no old code can rely on them.
> Let me make a general point: You don't "just get rid of facilities from
> an ISO standard".
I appreciate that. I am not suggesting we actually start a new stl::
namespace. I did try to make that clear in the original message; it's
just a brain-storming exercise.
I certainly never suggested removing stuff from the std:: namespace.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Daniel Frey <daniel.frey@aixigo.de>
Date: Sat, 19 May 2001 00:42:59 GMT Raw View
Dave Harris wrote:
> daniel.frey@aixigo.de (Daniel Frey) wrote (abridged):
> > int entry( int i =3D 0 ) const { return entries[i]; }
> > void entry( int e ) { entries[0] =3D e; }
>=20
> Here we have 2 functions with the same names and argument lists. The
> const/non-const difference is subtle:
You are right, my example wasn't correct. This results from the fact
that I wouldn't have written such code :) In my original answer, I said
that I consider it bad style anyway. Let's have a look at the next
example:
> Table table;
> int x =3D table.entry( 0 );
table.entry( 1, 5 );
should set the second entry to 5, right? IMHO this is not very readable,
even if you call it set_entry().
An alternative interface could look like this:
class Table
{
int& entry( int i =3D 0 ) { return &v[i]; }
int entry( int i =3D 0 ) const { return v[i]; }
};
Table table;
int x =3D table.entry();
table.entry() =3D 4;
showing clearly where a value is set and where it's retrieved. What I
utilitize is the fact that const- and non-const-versions of a function
can have different return types.
> Imagine table was initially non-const, but, after writing a lot of code=
,
> we thought a read-only version might be sufficient. So we change the
> declaration. The compiler should warn about setters, not silently turn
> them into getters!
It seems to me that your naming convention (using 'set') makes sense in
the kind of code you write, probably depending on the requirements. I
tend to avoid code that requires to call functions 'set_xyz'. I believe
(but cannot prove :) that this helps me to produce better interfaces,
but this is only my personal opinion. For you, this may not be practical
/ possible and it's perfectly OK to use 'set'...
I don't think there is one correct way of naming functions, but the STL
was designed in a way not requiring function names to contain 'set' to
be understandable. Your example is nothing I found in the STL, therefore
I consider renaming the STL-interface as not useful. The only thing I
see is a potential mix-up of clear() and empty() - but would you call it
set_clear() instead? Would it be better if they use is_empty() or
do_clear()? Nothing I would like to see :)
This doesn't mean you cannot use your own conventions in your projects
(I do and it doesn't match the STL in other situations) but this
shouldn't be seen as the holy grail and make the STL use this convention
too (as this is where this discussion emerged from, right?).
To summarize it: As long as you don't show me how you argument relates
to the STL and provides some real benefits, I don't see any reason to
change the existing naming scheme. If you want to improve the STL, some
of the other point you mentioned are definitely a good idea - but
renaming the interfaces IMHO isn't.
With regards, Daniel
--
Daniel Frey
aixigo AG - financial training, research and technology
Schlo=DF-Rahe-Stra=DFe 15, 52072 Aachen, Germany
fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: nickt@kipling.aus.deuba.com (Nick Thurn)
Date: Sat, 19 May 2001 08:54:00 GMT Raw View
Dave Harris wrote:
> That would be OK, if I can write:
>
> typedef map<string, int, hash_table> MyMap;
>
> My point here is that "map" is a general name which should be used for a
> more general concept than the specific complexities of std::map.
>
Agree with your comment on map however a nit: map and hash_table are
not equivalent. I'm thinking equal_range, upper_bound and such.
cheers
Nick
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: news/comp.std.c++@nmhq.net (Niklas Matthies)
Date: Sat, 19 May 2001 09:04:17 GMT Raw View
On Sat, 19 May 2001 00:42:59 GMT, Daniel Frey <daniel.frey@aixigo.de> wro=
te:
> Dave Harris wrote:
[=B7=B7=B7]
> It seems to me that your naming convention (using 'set') makes sense in
> the kind of code you write, probably depending on the requirements. I
> tend to avoid code that requires to call functions 'set_xyz'. I believe
> (but cannot prove :) that this helps me to produce better interfaces,
> but this is only my personal opinion. For you, this may not be practica=
l
> / possible and it's perfectly OK to use 'set'...
>=20
> I don't think there is one correct way of naming functions, but the STL
> was designed in a way not requiring function names to contain 'set' to
> be understandable. Your example is nothing I found in the STL, therefor=
e
> I consider renaming the STL-interface as not useful. The only thing I
> see is a potential mix-up of clear() and empty() - but would you call i=
t
> set_clear() instead? Would it be better if they use is_empty() or
> do_clear()? Nothing I would like to see :)
`is_empty()' would certainly be an improvement, because plain "empty"
can be both a verb and an adjective. Such ambiguities should have been
avoided. Furthermore, code like `if (container.is_empty())' reads most
naturally.
`clear()' doesn't have quite the same ambiguity, since "clear" as an
adjective doesn't make that much sense for a container (less than e.g.
"cleared"), so it's more obvious that it is meant as a verb.
Personally, I'd find `erase_all()' preferable, since it is clear (no pun
intended) then that it conceptually does an `erase()' for all elements.
One might even name it `erase_all_elems()', since it's not a member
function used that often, and one that performs a rather drastic
operation, so it can have a longer name.
-- Niklas Matthies
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Thu, 17 May 2001 11:26:48 GMT Raw View
Radoslav Getov wrote:
...
> How about having 2 versions of the containers - one with allocators and one
> without, instead one version with default allocator? This shouldn't break
> any existing code, I believe, and will be in the spirit of C/C++ (don't pay
> for what you don't need ;-).
And what method would the one defined without an allocator use to
allocate and deallocate needed memory? If it uses 'new' and 'delete',
how would such a container differ from Container<T,std::allocator<T> >,
which is precisely what Container<T> defaults to?
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Francis Glassborow <francis.glassborow@ntlworld.com>
Date: Thu, 17 May 2001 11:34:20 GMT Raw View
In article <3B02A30D.C44ED3B4@dollywood.itp.tuwien.ac.at>, Christopher
Eltschka <celtschk@dollywood.itp.tuwien.ac.at> writes
>> (4) Separate string into mutable and immutable forms. Immutable strings
>> support efficient copying; they can share parts of their representation
>> without bothering with copy-on-write. Mutable strings support efficient
>> editing. They don't need to be sharable.
>
>I'm not sure if this can be done without breaking lots of code.
Suppose that we added a 'basic_string_literal' template type as an extra
type and possibly provided implicit conversion to the corresponding
basic_string. All existing code would continue to work as it already
does, but future code could capitalise on the new type. Those new types
could be used to replace usage of char const*, w_char const* etc. for
handling string literals and so provide a transition away from those
archaic remnants inherited from C (for which there are, currently, no
good substitutes) The new template type should also have a ctor that
takes can create an instance from any string but it should only have a
const interface.
Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: rogero@howzatt.demon.co.uk
Date: Thu, 17 May 2001 17:35:37 GMT Raw View
In article <memo.20010515105511.43417C@brangdon.madasafish.com>, Dave Harris
<brangdon@cix.co.uk> writes:
>
>Suppose we were designing a template library from scratch, without much
>concern for backwards compatibility.
I'm sorry, I think it is too late for this! I wouldn't want C++ to go
the way of "the various flavours of Unix".
What I want is a graceful way to migrate from where we are to where we
would like to be. Something like the @deprecated keyword from Java
for example - some way to mark methods/classes where a newer, improved,
replacement was available but still providing a window of time in which
the old method is available.
>(1) Get rid of allocators. Everyone hates allocators.
What problems do they cause - they're only default arguments?
Some people seem to need them to solve performance problems.
>(2) Get rid of the vector<bool> specialisation.
Yes
>(3) Add reified sequences. Drop the implicit 2-iterator convention.
nc
>(4) Separate string into mutable and immutable forms.
Yes please!! This is the one I feel we need most.
>(5) Fix the method naming conventions, especially the verb/noun
>confusions.
Probably too late for this now...
>(6) Give the containers more specific names.
Please could you explain the benefit of this one?
>(7) Make vector and string range-checked by default.
I'd prefer having a standard way of selecting a checking/non-checking
version of the library (or of some components?).
>(8) Get rid of constant time list::size(). Have constant time splice
>instead.
nc
>(9) Make erase() take a const_iterator instead of a non-const iterator.
OK
--
Roger Orr
MVP in C++ at www.brainbench.com
----- Posted via NewsOne.Net: Free (anonymous) Usenet News via the Web -----
http://newsone.net/ -- Free reading and anonymous posting to 60,000+ groups
NewsOne.Net prohibits users from posting spam. If this or other posts
made through NewsOne.Net violate posting guidelines, email abuse@newsone.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.research.att.com/~austern/csc/faq.html ]
Author: "Al Grant" <tnarga@arm.REVERSE-NAME.com>
Date: Thu, 17 May 2001 17:37:07 GMT Raw View
"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3B031A21.A5636386@wizard.net...
> Radoslav Getov wrote:
> ...
> > How about having 2 versions of the containers - one with allocators and
one
> > without, instead one version with default allocator? This shouldn't
break
> > any existing code, I believe, and will be in the spirit of C/C++ (don't
pay
> > for what you don't need ;-).
>
> And what method would the one defined without an allocator use to
> allocate and deallocate needed memory? If it uses 'new' and 'delete',
> how would such a container differ from Container<T,std::allocator<T> >,
> which is precisely what Container<T> defaults to?
If the default allocator is an empty class and the
container contains the allocator as a member (as in
P.J. Plauger's STL) then a container without an
allocator would be smaller.
Of course, we could instead throw out the rule that
says empty members must take up space.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Radoslav Getov" <nospam@mai.com>
Date: Thu, 17 May 2001 17:37:27 GMT Raw View
"James Kuyper Jr." <kuyper@wizard.net> wrote in message
news:3B031A21.A5636386@wizard.net...
: Radoslav Getov wrote:
: ...
: > How about having 2 versions of the containers - one with allocators and
one
: > without, instead one version with default allocator? This shouldn't
break
: > any existing code, I believe, and will be in the spirit of C/C++ (don't
pay
: > for what you don't need ;-).
:
: And what method would the one defined without an allocator use to
: allocate and deallocate needed memory? If it uses 'new' and 'delete',
: how would such a container differ from Container<T,std::allocator<T> >,
: which is precisely what Container<T> defaults to?
:
By *not* storing an allocator object in each container? By providing a
simpler and faster implementation (i.e. direct new/delete calls instead
allocator.allocate.new etc).
By providing faster swap and assign (and maybe others that insist on
allocators' equality.
By simplifying template class names used in compiler warnings :-)
Radoslav Getov
Radoslav
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>
Date: Thu, 17 May 2001 17:38:18 GMT Raw View
Wed, 16 May 2001 17:06:20 GMT, Daniel Frey <daniel.frey@aixigo.de> pisze:
> Hm, how about:
>=20
> int entry( int i =3D 0 ) const { return entries[i]; }
>=20
> void entry( int i, int e ) { entries[i] =3D e; }
> void entry( int e ) { entries[0] =3D e; }
How would you get 5th entry of a non-const object?
--=20
__("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
\__/
^^ SYGNATURA ZAST=CAPCZA
QRCZAK
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Matthew Austern <austern@research.att.com>
Date: Thu, 17 May 2001 18:15:01 GMT Raw View
"Al Grant" <tnarga@arm.REVERSE-NAME.com> writes:
> > And what method would the one defined without an allocator use to
> > allocate and deallocate needed memory? If it uses 'new' and 'delete',
> > how would such a container differ from Container<T,std::allocator<T> >,
> > which is precisely what Container<T> defaults to?
>
> If the default allocator is an empty class and the
> container contains the allocator as a member (as in
> P.J. Plauger's STL) then a container without an
> allocator would be smaller.
But there are well known techniques for writing containers so that the
default allocator doesn't take up space. (I don't think I should
discuss those techniques here, because they're not really related to
C++ standardization.) Allocators are unquestionably more work for
implementors, but, if well implemented, I don't think they hurt users.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Heinz Huber <hhuber@racon-linz.at>
Date: Thu, 17 May 2001 19:56:39 GMT Raw View
Daniel Frey wrote:
>
> Dave Harris wrote:
> >
> > daniel.frey@aixigo.de (Daniel Frey) wrote (abridged):
[snip]
> > > I personally dislike this naming convention. If you really want to
> > > change the names to match, why not overload them?
> > >
> > > const size_t capacity() const;
> > > void capacity( const size_t newCapacity );
> >
> > Ah, well. These functions do very different things. One changes the state
> > of the object, the other merely returns a result. They are not in any way
> > polymorphically substitutable for each other. They are different. We
> > should be able to tell what a function does from its name. Functions that
> > do different things should have different names.
>
> They have :) Well, somehow...
>
> > In particular, functions that change the state of objects should have
> > "set" in their name, or otherwise make it clear what they are doing. Your
> > general rule, that we can tell what they are doing merely from counting
> > the number of arguments, is not good. Eg:
>
> I'm NOT counting the arguments!! I agree with you that this would be a
> very stupid idea. I indeed use a const and a non-const function to
> indicate what's the setter and what's the getter. Following your
> argumentation a function should not just have 'set' in its name if a
> value (or state?) is set, it should consequently have 'get' or 'do' in
> it's name for the other cases. But this defeates object encapsulation as
> you have a function 'set_xyz' that will change to a function that
> actually *does* something (calculations, etc.) in a later
> implementation. I have some experience with naming schemes and using
> 'set' isn't a good idea, really! :)
>
> > class Table {
> > int entries[10];
> > public:
> > int entry( int i ) { return entries[i]; }
> > void set_entry( int i, int e ) { entries[i] = e; }
> >
> > // Use default of 0 if the index is not specified.
> > int entry() const { return entries[0]; }
> > void set_entry( int e ) { entries[0] = e; }
> > };
>
> Hm, how about:
>
> int entry( int i = 0 ) const { return entries[i]; }
>
> void entry( int i, int e ) { entries[i] = e; }
> void entry( int e ) { entries[0] = e; }
>
> But I anyway consider it bad style (personal opinion) to provide a
> default parameter that way...
I wouldn't do that. I'm not even sure whether it's legal to overload on return
type when using different const qualifications. Furthermore, you wouldn't be
able to call the getter on a non-const object without casting it.
Regards,
Heinz
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Peter Dimov <pdimov@MailAndNews.com>
Date: Thu, 17 May 2001 19:57:15 GMT Raw View
>===== Original Message From bs@research.att.com (Bjarne Stroustrup) =====
>brangdon@cix.co.uk (Dave Harris) writes:
>
>> > > (2) Get rid of the vector<bool> specialisation.
>
>There are problems with vector<bool> and several issues related to it are
>being discussed, but one - more likely IMO - outcome of these discussions
>would be facilities that allows proper proxy containers to be constructed,
>and vector<bool> would be one of those.
The question is not whether to have proper proxy containers, or a bit
vector.
The question is whether this container should be a specialization for
std::vector<T> for T = bool.
Does generic code that uses std::vector<T> benefits from the bool special
case? The disadvantages are obvious: std::vector is often used as a dynamic
array, hence the contiguous storage guarantee and the [&v[0], v.size()]
idiom.
std::vector<bool> does not support this usage.
Naming the bit vector std::vector_bool will still allow users that need it
to
use it.
--
Peter Dimov
Multi Media Ltd.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: James Dennett <jdennett@acm.org>
Date: Thu, 17 May 2001 21:11:31 GMT Raw View
Heinz Huber wrote:
>
> I wouldn't do that. I'm not even sure whether it's legal to overload on return
> type when using different const qualifications.
The const-qualification of "*this" is part of the signature which
enters into overloading, so the difference of return types is not
a problem. Return types are not taken into account during
overload resolution -- and once overload resolution has succeeded,
the return type is uniquely determined.
-- James Dennett
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: kuehl@ramsen.informatik.uni-konstanz.de (Dietmar Kuehl)
Date: Fri, 18 May 2001 03:01:51 GMT Raw View
Hi,
Al Grant (tnarga@arm.REVERSE-NAME.com) wrote:
: Of course, we could instead throw out the rule that
: says empty members must take up space.
An implementation can [easily] avoid any space overhead by relying on
the "empty base optimization": There is no requirement that the address
of a base is different from the address of the full object. This can be
used to implement "members" which don't take up any space in case they
don't have any data. Of course, this requires that the "member" is
accessed solely through a functional interface and never named
explicitly. I think there is an example of this in the Boost library
under the name "compressed_pair" or something like this.
--
<mailto:dietmar_kuehl@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "James Kuyper Jr." <kuyper@wizard.net>
Date: Fri, 18 May 2001 05:45:24 GMT Raw View
Al Grant wrote:
>
> "James Kuyper Jr." <kuyper@wizard.net> wrote in message
> news:3B031A21.A5636386@wizard.net...
> > Radoslav Getov wrote:
> > ...
> > > How about having 2 versions of the containers - one with allocators and
> one
> > > without, instead one version with default allocator? This shouldn't
> break
> > > any existing code, I believe, and will be in the spirit of C/C++ (don't
> pay
> > > for what you don't need ;-).
> >
> > And what method would the one defined without an allocator use to
> > allocate and deallocate needed memory? If it uses 'new' and 'delete',
> > how would such a container differ from Container<T,std::allocator<T> >,
> > which is precisely what Container<T> defaults to?
>
> If the default allocator is an empty class and the
> container contains the allocator as a member (as in
> P.J. Plauger's STL) then a container without an
> allocator would be smaller.
Why? There's no need for a container to keep a copy of the the
allocator. The standard appears to say that it must, but all instances
of std::allocator<> are equivalent, and there's not a single thing a
program can do to detect the fact that each
Container<T,std::allocator<T> > does not contain it's own copy of the
allocator used to initialize it.
This is even true for user-defined allocators, because the standard
gives license for the implementors to assume that all allocator
instances of the same type are interchangeable. Any user-defined
allocator that could detect the failure to store a per-container copy of
the allocator would necessarily involve instances that are not
interchangeable.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Wed, 16 May 2001 13:40:33 GMT Raw View
poenitz@htwm.de (=?iso-8859-1?Q?Andr=E9_P=F6nitz?=) wrote (abridged):
> > (2) Get rid of the vector<bool> specialisation.
>
> What would you use instead of those?
Vector<bool> would still exist but would be a normal vector. Some other
class would provide the implementation that is currently in
std::vector<bool>, eg stl::bitset (with std::bitset becoming
stl::fixed_bitset).
> > (5) Fix the method naming conventions
>
> ... which would confuse people who have adapted to current STL's
> convention...
I'm trying not to think about backwards compatibility at this point.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Radoslav Getov" <nospam@mai.com>
Date: Wed, 16 May 2001 14:12:01 GMT Raw View
"Anthony Williams" <anthwil@nortelnetworks.com> wrote in message
news:9dr5ep$jahq4$1@ID-49767.news.dfncis.de...
: "Dave Harris" <brangdon@cix.co.uk> wrote in message
: news:memo.20010515105511.43417C@brangdon.madasafish.com...
: >
: > Suppose we were designing a template library from scratch, without much
: > concern for backwards compatibility. Suppose it was going in a new
: > namespace, say stl:: instead of std::. What would we do differently?
: >
: > My own thoughts:
: >
: > (1) Get rid of allocators. Everyone hates allocators.
:
: I agree, in general - the majority of projects never need a custom
: allocator, so forcing them on every container means most people pay for
: something they never use. However, in some circumstances people do want
: custom allocators, so it would be nice to be able to have some way of
: keeping them.
:
How about having 2 versions of the containers - one with allocators and one
without, instead one version with default allocator? This shouldn't break
any existing code, I believe, and will be in the spirit of C/C++ (don't pay
for what you don't need ;-).
Radoslav Getov
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Christopher Eltschka <celtschk@dollywood.itp.tuwien.ac.at>
Date: Wed, 16 May 2001 09:34:36 CST Raw View
Daniel Frey wrote:
>
> Dave Harris wrote:
[...]
> > (8) Get rid of constant time list::size(). Have constant time splice
> > instead.
>
> An implementation is IMHO free to "waste" some space and keep a counter
> up-to-date and let size() return that counter (which is O(1)), but I
> don't think there is a reason to force an implementation to do that, as
> it may not be efficient for most users, just for a few and they should
> ask themself if another container wouldn't be better for them.
Read again: He didn't want to force this overhead, he wanted to
*forbid* it. And you gave a perfect description why this would be
a good idea. Besides the fact that you always can cache the size
yourself.
Also note that implementations could still cache the size; the cache
would just have to be invalidated on slice (so they couldn't offer
guaranteed O(1) time, but O(1) except for the first call after slice).
The point is that currently the standard gives the freedom to
have a non-O(1) slice to get an O(1) size. And this is IMHO as wrong
as possible.
[...]
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Wed, 16 May 2001 15:14:36 GMT Raw View
daniel.frey@aixigo.de (Daniel Frey) wrote (abridged):
> For large applications, allocators are a holy gift and a good
> argument for the STL, as the allow you to rapidly create an
> application and optimize it when needed.
OK... what do you use them for? My understanding is that allocators were
introduced for the sake of 16-bit Intel platforms with segment-based
pointers. Microsoft added some keywords to their dialect of C++ to make
that stuff easier, too. Since we didn't add __based to standard C++, I
don't see why we should have added allocators.
Anyway, so allocators have some other use? Is it not possible to use a
specialised operator new() instead?
I'll rephrase that: what changes would be needed so that specialised
operator new() could be used instead of allocators? I imagine the
containers would need to export types such as deque::iterator and
guarantee that they were unique and not typedef'd (char *) (or whatever).
> I bet people will start to use immutable strings as parameters
> whereever possible but as soon as you have a mutable string and pass
> it to a function taking an immutable string, it will be copied.
I would have no implicit conversion from mutable to immutable. The
conversion would be explicit, and would come in two forms. The first form
would be a copy that left the source unchanged.
The second form would transfer ownership of the underlying memory buffer.
This would leave the source in an "empty" state. It should be possible to
implement this in O(1) time, without any copying or memory allocation.
> Or you have to write all those functions twice, once for mutable
> strings and once for immutable ones.
I wouldn't do that. The idea is for one part of the code to build up a
string using the mutating operations. As its final step, it converts to
an immutable string for use by the rest of the code.
> All in all this will lead to a lot of trouble and IMHO this
> isn't justified by the benefits.
Efficient and expressive string handling is important. C++ is currently
rather weak in this area. Eg see the problems implementing "copy on
write".
> I personally dislike this naming convention. If you really want to
> change the names to match, why not overload them?
>
> const size_t capacity() const;
> void capacity( const size_t newCapacity );
Ah, well. These functions do very different things. One changes the state
of the object, the other merely returns a result. They are not in any way
polymorphically substitutable for each other. They are different. We
should be able to tell what a function does from its name. Functions that
do different things should have different names.
In particular, functions that change the state of objects should have
"set" in their name, or otherwise make it clear what they are doing. Your
general rule, that we can tell what they are doing merely from counting
the number of arguments, is not good. Eg:
class Table {
int entries[10];
public:
int entry( int i ) { return entries[i]; }
void set_entry( int i, int e ) { entries[i] = e; }
// Use default of 0 if the index is not specified.
int entry() const { return entries[0]; }
void set_entry( int e ) { entries[0] = e; }
};
This class would become most unclear if we replaced set_entry with entry.
It would be unclear even if we didn't use 0 as a default index.
Still, I appreciate this is the kind of semi-religious argument that the
standards committee wanted to avoid. My feeling is that names matter, and
that some names have objective benefits over others, and it is important
for the standard to exhibit good style. So I think it is worth at least a
little bit of argument.
> > Likewise std::map would become stl::red_black_tree_map.
>
> The name should tell me how I can _use_ a container, not how it is
> implemented.
I sort-of agree, but the STL does imply a lot about how containers are
implemented.
Here's the problem. The thing that I call a "map", or "dictionary", or
"associative array", can be implemented in many ways, eg:
(1) As a balanced tree, eg a red-black tree.
(2) As a hash-table.
(3) As a sorted array, using binary-search for lookup.
All three of these should probably be in the standard library, and we
should be able to switch between them easily. They should have the same
general interface, at least in terms of function signatures. Of course,
operations will vary in complexity between them. Eg lookup is O(1) on
average for the hash-table and O(log N) for the tree and sorted array.
So we need names that convey, not just a set of function signatures, but
the set of complexities. And in my view, "map" doesn't do that. "Map"
fails to distinguish between the 3 implementations.
I accept that "red_black_tree_map" may convey a bit more than we really
want. It should be read as specifying, not a red-black tree, but anything
with the same complexities as a red-black tree. Red-black tree is merely
a typical implementation, an exemplar. (That said, I don't believe it is
possible to implement a conforming std::map with anything other than a
red-black tree.)
Anyway, I think "red_black_tree_map" is an improvement over "map". Do you
have another suggestion? The problem is that how the container is used
should include what complexity guarantees its users may rely on, and a
congeries of complexities is a difficult thing to name well.
> > (7) Make vector and string range-checked by default.
>
> No. In the applications I write, we need speed. It's OK for a debug- /
> safe-STL to check ranges, but not for a productive system.
I am not saying there should be no fast access, only that it should not
be the default. Your applications would use the non-default accessors.
Maybe you would want to subclass stl::vector to remap operator[]() to the
unsafe versions, much as Stroustrup does with Vec and std::vector in
$3.7.2 of the C++PL. You obviously know what you are doing, so I think
you are better placed to write such a subclass than someone just starting
to learn C++.
> > (8) Get rid of constant time list::size(). Have constant time splice
> > instead.
>
> An implementation is IMHO free to "waste" some space and keep a counter
> up-to-date and let size() return that counter (which is O(1)), but I
> don't think there is a reason to force an implementation to do that, as
> it may not be efficient for most users, just for a few and they should
> ask themself if another container wouldn't be better for them.
You seem to be arguing with me here, rather than against me. Currently
std::list::size() is required to be O(1), which means the 3-argument
version of std::list::splice() must be O(N). I would rather it was the
other way about.
I'd rather splice was O(1) even if it meant size() was slower. I can
always keep track of the size myself if I need it fast.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Peter Dimov <pdimov@MailAndNews.com>
Date: Wed, 16 May 2001 15:15:31 GMT Raw View
>===== Original Message From brangdon@cix.co.uk =====
>(2) Get rid of the vector<bool> specialisation.
Agreed - provide vector_bool instead.
>(3) Add reified sequences. Drop the implicit 2-iterator convention.
There's no proof of concept that this will work.
>(5) Fix the method naming conventions, especially the verb/noun
>confusions. For example, is_empty() and set_empty() instead clear() and
>empty(). Set_capacity() and capacity() instead of reserve() and
>capacity().
Note that 'reserve' doesn't set the capacity.
>(6) Give the containers more specific names. For example, "deque" is a
>general ADT which may be implemented in a variety of ways (including a
>linked list). std::deque is a very specific implementation. Likewise
>std::map would become stl::red_black_tree_map.
std::map is not a red-black tree map. It's "a red-black tree map or better,"
just like std::sort is not a quicksort but an introsort nowadays.
--
Peter Dimov
Multi Media Ltd.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Daniel Frey <daniel.frey@aixigo.de>
Date: Wed, 16 May 2001 17:06:20 GMT Raw View
Dave Harris wrote:
>=20
> daniel.frey@aixigo.de (Daniel Frey) wrote (abridged):
> > For large applications, allocators are a holy gift and a good
> > argument for the STL, as the allow you to rapidly create an
> > application and optimize it when needed.
>=20
> OK... what do you use them for? My understanding is that allocators wer=
e
> introduced for the sake of 16-bit Intel platforms with segment-based
> pointers. Microsoft added some keywords to their dialect of C++ to make
> that stuff easier, too. Since we didn't add __based to standard C++, I
> don't see why we should have added allocators.
I've never seen them in this light. You can use them for memory-pools to
avoid fragmentation and for cryptographic uses (a string/container that
clears its memory as soon as it is destroyed or freed). Other uses I
heard of are persistent mappings to databases, but I personally have no
attitude to even try this :)
> I'll rephrase that: what changes would be needed so that specialised
> operator new() could be used instead of allocators? I imagine the
> containers would need to export types such as deque::iterator and
> guarantee that they were unique and not typedef'd (char *) (or whatever=
).
It's a different approach. Maybe you're right and allocators are not
needed, but I think there is a slight difference: With allocators, you
can specify different types for strings (some normal, some cryptographic
strings). Using operator new() will hit all strings at once, right?
Allocators have a better resolution (IMHO), but I have to admit that I
can't overlook this topic so far.
> > I bet people will start to use immutable strings as parameters
> > whereever possible but as soon as you have a mutable string and pass
> > it to a function taking an immutable string, it will be copied.
>=20
> I would have no implicit conversion from mutable to immutable. The
> conversion would be explicit, and would come in two forms. The first fo=
rm
> would be a copy that left the source unchanged.
>
> The second form would transfer ownership of the underlying memory buffe=
r.
> This would leave the source in an "empty" state. It should be possible =
to
> implement this in O(1) time, without any copying or memory allocation.
This seem to increase the complexity of the interface which is not what
most people need. Probably we could keep strings as they are and provide
an alternative class for fast storing. Hm... seem that this is exactly
what you are trying to do by introducing immutable strings... :)
> Efficient and expressive string handling is important. C++ is currently
> rather weak in this area. Eg see the problems implementing "copy on
> write".
I'm not sure about the benefits. I think current implementations aren't
that bad and I wonder if they can be improved for RL-programs by 10%,
100% or 1000%. Do you have any statistics on that?
> > I personally dislike this naming convention. If you really want to
> > change the names to match, why not overload them?
> >
> > const size_t capacity() const;
> > void capacity( const size_t newCapacity );
>=20
> Ah, well. These functions do very different things. One changes the sta=
te
> of the object, the other merely returns a result. They are not in any w=
ay
> polymorphically substitutable for each other. They are different. We
> should be able to tell what a function does from its name. Functions th=
at
> do different things should have different names.
They have :) Well, somehow...
> In particular, functions that change the state of objects should have
> "set" in their name, or otherwise make it clear what they are doing. Yo=
ur
> general rule, that we can tell what they are doing merely from counting
> the number of arguments, is not good. Eg:
I'm NOT counting the arguments!! I agree with you that this would be a
very stupid idea. I indeed use a const and a non-const function to
indicate what's the setter and what's the getter. Following your
argumentation a function should not just have 'set' in its name if a
value (or state?) is set, it should consequently have 'get' or 'do' in
it's name for the other cases. But this defeates object encapsulation as
you have a function 'set_xyz' that will change to a function that
actually *does* something (calculations, etc.) in a later
implementation. I have some experience with naming schemes and using
'set' isn't a good idea, really! :)
> class Table {
> int entries[10];
> public:
> int entry( int i ) { return entries[i]; }
> void set_entry( int i, int e ) { entries[i] =3D e; }
>=20
> // Use default of 0 if the index is not specified.
> int entry() const { return entries[0]; }
> void set_entry( int e ) { entries[0] =3D e; }
> };
Hm, how about:
int entry( int i =3D 0 ) const { return entries[i]; }
void entry( int i, int e ) { entries[i] =3D e; }
void entry( int e ) { entries[0] =3D e; }
But I anyway consider it bad style (personal opinion) to provide a
default parameter that way...
> This class would become most unclear if we replaced set_entry with entr=
y.
> It would be unclear even if we didn't use 0 as a default index.
As long as you count arguments. Look at the 'const' instead and it'll
become clearer! It even helps to express what you mean by code (that can
be checked by the compiler) instead of documentation (by adding set_ to
an identifier). Even your example above shows how it works: You forgot
the 'const' for the first function! :)
> > > Likewise std::map would become stl::red_black_tree_map.
> >
> > The name should tell me how I can _use_ a container, not how it is
> > implemented.
>=20
> I sort-of agree, but the STL does imply a lot about how containers are
> implemented.
>=20
> Here's the problem. The thing that I call a "map", or "dictionary", or
> "associative array", can be implemented in many ways, eg:
>=20
> (1) As a balanced tree, eg a red-black tree.
> (2) As a hash-table.
> (3) As a sorted array, using binary-search for lookup.
>=20
> All three of these should probably be in the standard library, and we
> should be able to switch between them easily. They should have the same
> general interface, at least in terms of function signatures. Of course,
> operations will vary in complexity between them. Eg lookup is O(1) on
> average for the hash-table and O(log N) for the tree and sorted array.
I think this issue was covered by someone else already. I also sort-of
agree with you and a solution could be to seperate the interface from
the implementation. The current STL tries to concentrate on the
interface description, so you just need to be able to select from
different implementations. As don't know if this is prohibited by the
standard, but I don't think so. Therefore, it is an additional feature
and shouldn't lead to forcing someone to choose an implementation.
To summarize it: I think it's a useful addition, but it should be
designed in such a way that it doesn't break existing code or adds
complexity for the standard cases.
> > > (7) Make vector and string range-checked by default.
> >
> > No. In the applications I write, we need speed. It's OK for a debug- =
/
> > safe-STL to check ranges, but not for a productive system.
>=20
> I am not saying there should be no fast access, only that it should not
> be the default. Your applications would use the non-default accessors.
>=20
> Maybe you would want to subclass stl::vector to remap operator[]() to t=
he
> unsafe versions, much as Stroustrup does with Vec and std::vector in
> $3.7.2 of the C++PL. You obviously know what you are doing, so I think
> you are better placed to write such a subclass than someone just starti=
ng
> to learn C++.
Learning C++ means you have to deal with NULL-pointers, etc. I believe
that it even helps to provide non-range-checking strings, etc. by
default as it will make people to notice that they are responsible.
Otherwise, C++ is not the right choice. I don't want to be mean, but I
prefer the STL to match the language behaviour here.
> > > (8) Get rid of constant time list::size(). Have constant time splic=
e
> > > instead.
> >
> > An implementation is IMHO free to "waste" some space and keep a count=
er
> > up-to-date and let size() return that counter (which is O(1)), but I
> > don't think there is a reason to force an implementation to do that, =
as
> > it may not be efficient for most users, just for a few and they shoul=
d
> > ask themself if another container wouldn't be better for them.
>=20
> You seem to be arguing with me here, rather than against me. Currently
Erm... yes, although I didn't noticed it #-P. I totally agree with you
:)))
Regards, Daniel
--
Daniel Frey
aixigo AG - financial training, research and technology
Schlo=DF-Rahe-Stra=DFe 15, 52072 Aachen, Germany
fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: emarkp@CSUA.Berkeley.EDU (E. Mark Ping)
Date: Wed, 16 May 2001 18:28:14 GMT Raw View
In article <memo.20010516142621.38693F@brangdon.madasafish.com>,
Dave Harris <brangdon@cix.co.uk> wrote:
>titi_@skynet.be (TiTi) wrote (abridged):
>> > (1) Get rid of allocators. Everyone hates allocators.
>>
>> Why?
>
>Unnecessary complexity. It just gets in the way.
How do they get in the way? I know this is a blind part of my C++
understanding (allocators in general), but I haven't even had to pay
attention to them, and yet use the library all the time. How do they
get in the way?
>> > (2) Get rid of the vector<bool> specialisation.
>>
>> Why?
>
>Unnecessary complexity. It just gets in the way.
More to the point, a vector<bool> doesn't satisfy the requirements of
a container, and although the specialization is potentially very
useful it can be unexpected. I didn't know about it until I read Herb
Sutter's article in the May 1999 C++ Report. When I ran into it, it
was causing performance problems in an inner loop. When I replaced
the vector<bool> with vector<char> I saw a huge performance increase
(I had wondered why the profiler had tagged that section of code).
--
Mark Ping
emarkp@soda.CSUA.Berkeley.EDU
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Matthew Austern <austern@research.att.com>
Date: Wed, 16 May 2001 19:57:18 GMT Raw View
emarkp@CSUA.Berkeley.EDU (E. Mark Ping) writes:
> In article <memo.20010516142621.38693F@brangdon.madasafish.com>,
> Dave Harris <brangdon@cix.co.uk> wrote:
> >titi_@skynet.be (TiTi) wrote (abridged):
> >> > (1) Get rid of allocators. Everyone hates allocators.
> >>
> >> Why?
> >
> >Unnecessary complexity. It just gets in the way.
>
> How do they get in the way? I know this is a blind part of my C++
> understanding (allocators in general), but I haven't even had to pay
> attention to them, and yet use the library all the time. How do they
> get in the way?
I mostly agree. As an implementor, allocators make my life harder.
As a user, they largely don't matter. A reasonable implementor should
be able to define write the container classes such that allocators
impose no space or time penalty for those who don't use them. And,
again as a user, I find that they're sometimes useful.
One tiny caveat. There's one extension that would be nice, and that
allocators make difficult: instantiating a container class with an
incomplete type. For example,
struct foo {
std::string tag;
std::vector<foo> children;
};
According to the C++ standard, this is undefined. At this moment
you'll find that it works (sort of) on some implementations, and
doesn't work on others. The implementations where it doesn't work
are those that have better support for allocators.
(What I mean by "better support" is real support, as opposed to merely
syntactic, for alternative memory models and alternative pointer
types.)
I don't have a proof of this, but I believe that extending the C++
standard to support instantiations with incomplete types is
incompatible with extending it so that better support for allocators
is required.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Christopher Eltschka <celtschk@dollywood.itp.tuwien.ac.at>
Date: Wed, 16 May 2001 19:58:27 GMT Raw View
Dave Harris wrote:
>
> Suppose we were designing a template library from scratch, without much
> concern for backwards compatibility. Suppose it was going in a new
> namespace, say stl:: instead of std::. What would we do differently?
>
> My own thoughts:
>
> (1) Get rid of allocators. Everyone hates allocators.
I don't hate them (although I don't have any use for them).
>
> (2) Get rid of the vector<bool> specialisation.
Yes.
>
> (3) Add reified sequences.
Yes.
> Drop the implicit 2-iterator convention.
No.
> (4) Separate string into mutable and immutable forms. Immutable strings
> support efficient copying; they can share parts of their representation
> without bothering with copy-on-write. Mutable strings support efficient
> editing. They don't need to be sharable.
I'm not sure if this can be done without breaking lots of code.
>
> (5) Fix the method naming conventions, especially the verb/noun
> confusions.
Some of the member names are _adjectives_. I don't see a verb/noun
confusion.
> For example, is_empty() and set_empty() instead clear() and
> empty().
Please don't. Especially "set_empty" sounds as wrong as it can
(it's like allowing "c.size() = 0"): "set" implies setting a
variable, at least logivally.
> Set_capacity() and capacity() instead of reserve() and
> capacity().
No again. reserve() doesn't _set_ the capacity.
set_capacity() would only appropriate if after the call we
would have a guarantee that capacity() returns the value we
supplied. But indeed, reserve only _increases_ the memory,
i.e. reserves(!) memory for more elements.
>
> (6) Give the containers more specific names. For example, "deque" is a
> general ADT which may be implemented in a variety of ways (including a
> linked list). std::deque is a very specific implementation.
No, it's also an ADT which may be implemented in a variety of ways
(although not as a linked list, since this would not fulfill the
complexity requrements). It's just that there is one well known
implementation which happens to fulfill the requirements.
> Likewise
> std::map would become stl::red_black_tree_map.
Likewise, not.
>
> (7) Make vector and string range-checked by default.
Debatable.
>
> (8) Get rid of constant time list::size(). Have constant time splice
> instead.
Very big YES!
>
> (9) Make erase() take a const_iterator instead of a non-const iterator.
Yes.
[...]
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: jpotter@falcon.lhup.edu (John Potter)
Date: Wed, 16 May 2001 19:59:32 GMT Raw View
On Wed, 16 May 2001 15:14:36 GMT, brangdon@cix.co.uk (Dave Harris)
wrote:
> Here's the problem. The thing that I call a "map", or "dictionary", or
> "associative array", can be implemented in many ways, eg:
>
> (1) As a balanced tree, eg a red-black tree.
> (2) As a hash-table.
> (3) As a sorted array, using binary-search for lookup.
>
> All three of these should probably be in the standard library, and we
> should be able to switch between them easily. They should have the same
> general interface, at least in terms of function signatures. Of course,
> operations will vary in complexity between them. Eg lookup is O(1) on
> average for the hash-table and O(log N) for the tree and sorted array.
>
> So we need names that convey, not just a set of function signatures, but
> the set of complexities. And in my view, "map" doesn't do that. "Map"
> fails to distinguish between the 3 implementations.
>
> I accept that "red_black_tree_map" may convey a bit more than we really
> want. It should be read as specifying, not a red-black tree, but anything
> with the same complexities as a red-black tree. Red-black tree is merely
> a typical implementation, an exemplar. (That said, I don't believe it is
> possible to implement a conforming std::map with anything other than a
> red-black tree.)
AVL-tree, deterministic skip list are two counter examples.
> Anyway, I think "red_black_tree_map" is an improvement over "map". Do you
> have another suggestion? The problem is that how the container is used
> should include what complexity guarantees its users may rely on, and a
> congeries of complexities is a difficult thing to name well.
The associative containers are at a higher level than the sequences
as are stack and queue.
template <class Key, class Value, class Container = rb_tree> class map;
However, that would require adding low level things like rb_tree,
avl_tree, skip_list, and others to the standard.
> Currently
> std::list::size() is required to be O(1), which means the 3-argument
> version of std::list::splice() must be O(N). I would rather it was the
> other way about.
What am I missing? The note A says that it *should* be constant time.
A requirement would use *shall*. It is an implementer choice now.
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.research.att.com/~austern/csc/faq.html ]
Author: remove.haberg@matematik.su.se (Hans Aberg)
Date: Wed, 16 May 2001 20:43:25 GMT Raw View
On Wed, 16 May 2001 15:14:36 GMT, brangdon@cix.co.uk (Dave Harris)
wrote:
> Here's the problem. The thing that I call a "map", or "dictionary", or
> "associative array", can be implemented in many ways, eg:
>
> (1) As a balanced tree, eg a red-black tree.
> (2) As a hash-table.
> (3) As a sorted array, using binary-search for lookup.
>
> All three of these should probably be in the standard library, and we
> should be able to switch between them easily. They should have the same
> general interface, at least in terms of function signatures. Of course,
> operations will vary in complexity between them. Eg lookup is O(1) on
> average for the hash-table and O(log N) for the tree and sorted array.
I think myself that one should on the one hand try to unify the classes
with different interfaces, while on the same time giving greater control
over the underlying implementation, that is, what combination of
complexities to choose, etc.
One can discuss this idea in terms of sequences (I am not sure exactly how
to implement the stuff below):
For example, try to write a single class "sequence" by which it is
possible to choose the underlying implementation, std::vector or std::list
or something else.
If the choice is static, the (pseudo-)code might somehow look like:
std::sequence<int, list> x;
std::sequence<int, vector> y;
...
x = y; // Convert list container to a vector.
Or a dynamic variation:
std::sequence<int> x(list);
...
x.mutate(vector); // Convert list container to a vector.
One would then be able to choose the underlying implementation according
to need.
The same idea would apply to other containers.
Hans Aberg * Anti-spam: remove "remove." from email address.
* Email: Hans Aberg <remove.haberg@member.ams.org>
* Home Page: <http://www.matematik.su.se/~haberg/>
* AMS member listing: <http://www.ams.org/cml/>
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: LR <lruss@superlink.net>
Date: Thu, 17 May 2001 03:05:53 GMT Raw View
Christopher Eltschka wrote:
>
> Dave Harris wrote:
> >
> > Suppose we were designing a template library from scratch, without much
> > concern for backwards compatibility. Suppose it was going in a new
> > namespace, say stl:: instead of std::. What would we do differently?
> >
> > My own thoughts:
> >
> > (1) Get rid of allocators. Everyone hates allocators.
>
> I don't hate them (although I don't have any use for them).
Not only do I not hate them, I came pretty close to using them. I work
on a platform where it's possible for a program (whatever that is) to
use more than one heap. I don't know if this is conforming behavior or
not, but one really nice thing about C++ language and the std lib are
their flexibility. Even the flexibility to consider fixing problems
that the compiler vendor has created.
So if we were designing from scratch, could we please put them in.
> > (5) Fix the method naming conventions, especially the verb/noun
> > confusions.
> > For example, is_empty() and set_empty() instead clear() and
> > empty().
I kinda like clear() and empty().
LR.
The platform that I'm currently using has non standard calls for
HeapAlloc, GlobalAlloc and LocalAlloc but strangely, there is no call to
SmartAlloc.
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Anthony Williams" <anthwil@nortelnetworks.com>
Date: Tue, 15 May 2001 17:28:51 GMT Raw View
"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20010515105511.43417C@brangdon.madasafish.com...
>
> Suppose we were designing a template library from scratch, without much
> concern for backwards compatibility. Suppose it was going in a new
> namespace, say stl:: instead of std::. What would we do differently?
>
> My own thoughts:
>
> (1) Get rid of allocators. Everyone hates allocators.
I agree, in general - the majority of projects never need a custom
allocator, so forcing them on every container means most people pay for
something they never use. However, in some circumstances people do want
custom allocators, so it would be nice to be able to have some way of
keeping them.
> (2) Get rid of the vector<bool> specialisation.
Well, make vector<bool> a proper container. This might mean modifying the
language to enable proper proxy types, so vector<bool>::reference can be
used just like a bool&, or it might mean just removing the specialization
> (3) Add reified sequences. Drop the implicit 2-iterator convention.
Agreed. I really like this idea.
> (4) Separate string into mutable and immutable forms. Immutable strings
> support efficient copying; they can share parts of their representation
> without bothering with copy-on-write. Mutable strings support efficient
> editing. They don't need to be sharable.
OK
> (5) Fix the method naming conventions, especially the verb/noun
> confusions. For example, is_empty() and set_empty() instead clear() and
> empty(). Set_capacity() and capacity() instead of reserve() and
> capacity().
I prefer capacity(int) and capacity(), and is_empty() and clear()
> (6) Give the containers more specific names. For example, "deque" is a
> general ADT which may be implemented in a variety of ways (including a
> linked list). std::deque is a very specific implementation. Likewise
> std::map would become stl::red_black_tree_map.
Better naming is good. A (template) typedef to some default implementation
could then be used to avoid breaking backwards compatibility, and simplify
things for people who just want a general-purpose container of the specified
type. If that becomes a performance bottleneck, then they can specify which
implementation to use
> (7) Make vector and string range-checked by default.
Hmm. Not sure about this one
> (8) Get rid of constant time list::size(). Have constant time splice
> instead.
>
> (9) Make erase() take a const_iterator instead of a non-const iterator.
>
> This is a brain-storming exercise. We can decide later if the list
> contains enough important stuff to actually justify starting a new
> library, or whether we can achieve some of the objectives without
> breaking backwards compatibility.
Anthony
--
Anthony Williams
Software Engineer, Nortel Networks Optoelectronics
The opinions expressed in this message are not necessarily those of my
employer
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: Daniel Frey <daniel.frey@aixigo.de>
Date: Tue, 15 May 2001 17:29:38 GMT Raw View
Dave Harris wrote:
>=20
> Suppose we were designing a template library from scratch, without much
> concern for backwards compatibility. Suppose it was going in a new
> namespace, say stl:: instead of std::. What would we do differently?
>=20
> My own thoughts:
>=20
> (1) Get rid of allocators. Everyone hates allocators.
I like them. If you don't, use the default. For large applications,
allocators are a holy gift and a good argument for the STL, as the allow
you to rapidly create an application and optimize it when needed. What I
hate most about allocators has nothing to do with their functionality: I
can't easily read the errors of my compiler. But this is a different
issue that has to be addressed by the compiler-people.
> (4) Separate string into mutable and immutable forms. Immutable strings
> support efficient copying; they can share parts of their representation
> without bothering with copy-on-write. Mutable strings support efficient
> editing. They don't need to be sharable.
This will lead to a lot of trouble. I bet people will start to use
immutable strings as parameters whereever possible but as soon as you
have a mutable string and pass it to a function taking an immutable
string, it will be copied. Or you have to write all those functions
twice, once for mutable strings and once for immutable ones. All in all
this will lead to a lot of trouble and IMHO this isn't justified by the
benefits.
> (5) Fix the method naming conventions, especially the verb/noun
> confusions. For example, is_empty() and set_empty() instead clear() and
> empty(). Set_capacity() and capacity() instead of reserve() and
> capacity().
I personally dislike this naming convention. If you really want to
change the names to match, why not overload them?
const size_t capacity() const;
void capacity( const size_t newCapacity );
> (6) Give the containers more specific names. For example, "deque" is a
> general ADT which may be implemented in a variety of ways (including a
> linked list). std::deque is a very specific implementation. Likewise
> std::map would become stl::red_black_tree_map.
The name should tell me how I can _use_ a container, not how it is
implemented.
> (7) Make vector and string range-checked by default.
No. In the applications I write, we need speed. It's OK for a debug- /
safe-STL to check ranges, but not for a productive system.
> (8) Get rid of constant time list::size(). Have constant time splice
> instead.
An implementation is IMHO free to "waste" some space and keep a counter
up-to-date and let size() return that counter (which is O(1)), but I
don't think there is a reason to force an implementation to do that, as
it may not be efficient for most users, just for a few and they should
ask themself if another container wouldn't be better for them.
> This is a brain-storming exercise. We can decide later if the list
> contains enough important stuff to actually justify starting a new
> library, or whether we can achieve some of the objectives without
> breaking backwards compatibility.
I'd like the STL to have a lot of additional templates. Boost.org is a
good example for a lot of extensions and ideas. But there is no reason
to abandon the 'old' STL and create a new one. Sure there are some
problems and design flaws but nothing serious IMHO.
Regards, Daniel
--
Daniel Frey
aixigo AG - financial training, research and technology
Schlo=DF-Rahe-Stra=DFe 15, 52072 Aachen, Germany
fon: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
eMail: daniel.frey@aixigo.de, web: http://www.aixigo.de
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "TiTi" <titi_@skynet.be>
Date: Tue, 15 May 2001 23:29:52 GMT Raw View
Dave Harris <brangdon@cix.co.uk> schreef in berichtnieuws
memo.20010515105511.43417C@brangdon.madasafish.com...
[...]
> (1) Get rid of allocators. Everyone hates allocators.
Why?
> (2) Get rid of the vector<bool> specialisation.
Why?
> (3) Add reified sequences. Drop the implicit 2-iterator convention.
What do you mean by that?
> (4) Separate string into mutable and immutable forms. Immutable strings
> support efficient copying; they can share parts of their representation
> without bothering with copy-on-write. Mutable strings support efficient
> editing. They don't need to be sharable.
NC
> (5) Fix the method naming conventions, especially the verb/noun
> confusions. For example, is_empty() and set_empty() instead clear() and
> empty(). Set_capacity() and capacity() instead of reserve() and
> capacity().
Cool thought.
> (6) Give the containers more specific names. For example, "deque" is a
> general ADT which may be implemented in a variety of ways (including a
> linked list). std::deque is a very specific implementation. Likewise
> std::map would become stl::red_black_tree_map.
Mmmm. I'd make the underlying implementation a template parameter (as with
allocation strategy - yup, the one you don't like)
> (7) Make vector and string range-checked by default.
Phooh. Never ever!
> (8) Get rid of constant time list::size(). Have constant time splice
> instead.
Excuse us?
> (9) Make erase() take a const_iterator instead of a non-const iterator.
Definte point there.
TiTi
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: =?iso-8859-1?Q?Andr=E9_P=F6nitz?= <poenitz@htwm.de>
Date: Tue, 15 May 2001 23:36:57 GMT Raw View
Dave Harris <brangdon@cix.co.uk> wrote:
> (2) Get rid of the vector<bool> specialisation.
What would you use instead of those?
> (5) Fix the method naming conventions, especially the verb/noun=20
> confusions. For example, is_empty() and set_empty() instead clear() and=
=20
> empty(). Set_capacity() and capacity() instead of reserve() and=20
> capacity().
... which would confuse people who have adapted to current STL's
convention...=20
> (7) Make vector and string range-checked by default.
No, thank you. Too expensive.
But I think I like the other points.
=20
Andre'
--=20
Andr=E9 P=F6nitz ............................................. poenitz@ht=
wm.de
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: "Andrei Alexandrescu" <andrewalex@hotmail.com>
Date: Tue, 15 May 2001 23:40:44 GMT Raw View
"Dave Harris" <brangdon@cix.co.uk> wrote in message
news:memo.20010515105511.43417C@brangdon.madasafish.com...
> Suppose we were designing a template library from scratch, without much
> concern for backwards compatibility. Suppose it was going in a new
> namespace, say stl:: instead of std::. What would we do differently?
>
> My own thoughts:
[snip]
I like your suggestions, they all make sense. My two cents: I'd make all
member functions of all STL classes nonmember :oO.
Andrei the fascist 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.research.att.com/~austern/csc/faq.html ]
Author: emarkp@CSUA.Berkeley.EDU (E. Mark Ping)
Date: Wed, 16 May 2001 00:42:04 GMT Raw View
In article <memo.20010515105511.43417C@brangdon.madasafish.com>,
Dave Harris <brangdon@cix.co.uk> wrote:
>(2) Get rid of the vector<bool> specialisation.
This is already an open discussion in the language working group. See
http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/lwg-active.html#96
for more details.
--
Mark Ping
emarkp@soda.CSUA.Berkeley.EDU
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Wed, 16 May 2001 13:36:39 GMT Raw View
titi_@skynet.be (TiTi) wrote (abridged):
> > (1) Get rid of allocators. Everyone hates allocators.
>
> Why?
Unnecessary complexity. It just gets in the way.
> > (2) Get rid of the vector<bool> specialisation.
>
> Why?
Unnecessary complexity. It just gets in the way.
> > (3) Add reified sequences. Drop the implicit 2-iterator convention.
>
> What do you mean by that?
See Stroustrup's C++PL, $18.3.1 for the general idea. A search for
"Reified sequences" in the "C++0x" thread should turn up a more elaborate
suggestion. This is also being discussed in comp.lang.c++.moderated.
(I think I've covered your other points elsewhere in this thread.)
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]
Author: brangdon@cix.co.uk (Dave Harris)
Date: Tue, 15 May 2001 11:25:07 GMT Raw View
Suppose we were designing a template library from scratch, without much
concern for backwards compatibility. Suppose it was going in a new
namespace, say stl:: instead of std::. What would we do differently?
My own thoughts:
(1) Get rid of allocators. Everyone hates allocators.
(2) Get rid of the vector<bool> specialisation.
(3) Add reified sequences. Drop the implicit 2-iterator convention.
(4) Separate string into mutable and immutable forms. Immutable strings
support efficient copying; they can share parts of their representation
without bothering with copy-on-write. Mutable strings support efficient
editing. They don't need to be sharable.
(5) Fix the method naming conventions, especially the verb/noun
confusions. For example, is_empty() and set_empty() instead clear() and
empty(). Set_capacity() and capacity() instead of reserve() and
capacity().
(6) Give the containers more specific names. For example, "deque" is a
general ADT which may be implemented in a variety of ways (including a
linked list). std::deque is a very specific implementation. Likewise
std::map would become stl::red_black_tree_map.
(7) Make vector and string range-checked by default.
(8) Get rid of constant time list::size(). Have constant time splice
instead.
(9) Make erase() take a const_iterator instead of a non-const iterator.
This is a brain-storming exercise. We can decide later if the list
contains enough important stuff to actually justify starting a new
library, or whether we can achieve some of the objectives without
breaking backwards compatibility.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
brangdon@cix.co.uk | And close your eyes with holy dread,
| For he on honey dew hath fed
http://www.bhresearch.co.uk/ | And drunk the milk of Paradise."
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.research.att.com/~austern/csc/faq.html ]