STL implementations
joel de guzman
Has anyone done a comprehensive analysis and
comparison of various |STL implementations?
I am particularly intersted in 1) standards
conformance, 2) speed and 3) code size (bloat).
Joel de Guzman
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Pete Becker
>
> Hi,
>
> Has anyone done a comprehensive analysis and
> comparison of various |STL implementations?
> I am particularly intersted in 1) standards
> conformance, 2) speed and 3) code size (bloat).
>
A good starting point is www.cuj.com/roundup/index.htm.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
Emery D. Conrad
try the CUJ, april 2001. there's a good article by herb sutter
addressing some of these issues.
emery
Stan Brown
>joel de guzman wrote:
>> Has anyone done a comprehensive analysis and
>> comparison of various |STL implementations?
>> I am particularly intersted in 1) standards
>> conformance, 2) speed and 3) code size (bloat).
>
>A good starting point is www.cuj.com/roundup/index.htm.
Perhaps you might give us a little more direct hint?
I entered "STL" (without quotes) in the search window at the URL
given above, and none of the thirty-one hits appeared to the
relevant to the question.
--
Stan Brown, Oak Road Systems, Cortland County, New York, USA
http://oakroadsystems.com
C++ FAQ Lite: http://www.parashift.com/c++-faq-lite/
the C++ standard: http://webstore.ansi.org/
reserved C++ identifiers: http://oakroadsystems.com/tech/cppredef.htm
more FAQs: http://oakroadsystems.com/tech/faqget.htm
Hendrik Schober
news:MPG.15523c5a1...@news.mindspring.com...
> Quoth Pete Becker <peteb...@acm.org> in comp.lang.c++.moderated:
> >joel de guzman wrote:
> >> Has anyone done a comprehensive analysis and
> >> comparison of various |STL implementations?
> >> I am particularly intersted in 1) standards
> >> conformance, 2) speed and 3) code size (bloat).
> >
> >A good starting point is www.cuj.com/roundup/index.htm.
>
> Perhaps you might give us a little more direct hint?
>
> I entered "STL" (without quotes) in the search window at the URL
> given above, and none of the thirty-one hits appeared to the
> relevant to the question.
There's a link on this page: www.cuj.com/roundup/a.htm
> Stan Brown, Oak Road Systems, Cortland County, New York, USA
Schobi
--
Spam...@gmx.de is never read
I'm hschober at gmx dot de
Pete Becker
>
> Quoth Pete Becker <peteb...@acm.org> in comp.lang.c++.moderated:
> >joel de guzman wrote:
> >> Has anyone done a comprehensive analysis and
> >> comparison of various |STL implementations?
> >> I am particularly intersted in 1) standards
> >> conformance, 2) speed and 3) code size (bloat).
> >
> >A good starting point is www.cuj.com/roundup/index.htm.
>
> Perhaps you might give us a little more direct hint?
>
> I entered "STL" (without quotes) in the search window at the URL
> given above, and none of the thirty-one hits appeared to the
> relevant to the question.
>
A better approach would be to click on the link named "C++ Conformance
Roundup". <g>
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
P.J. Plauger
news:MPG.15523c5a1...@news.mindspring.com...
> >A good starting point is www.cuj.com/roundup/index.htm.
>
> Perhaps you might give us a little more direct hint?
>
> I entered "STL" (without quotes) in the search window at the URL
> given above, and none of the thirty-one hits appeared to the
> relevant to the question.
http://www.cuj.com/roundup/a.htm
It's the first hot link on the page, labeled C++ Conformance
Roundup. Hint enough?
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
joel de guzman
of the reviewed C++ Standard library products"
This is not fair ;-)
Anyway, this is a nice starting point but although conformance
and portability are both important, ultimately, speed and code
size is more of a concern to real programmers in the field.
Joel de Guzman
"P.J. Plauger" <p...@dinkumware.com> wrote in message
news:3ae8bce8$0$1...@wodc7nh6.news.uu.net...
P.J. Plauger
news:9cd1s8$dhkmj$1...@ID-58159.news.dfncis.de...
> "Dinkumware is both a reviewer and a vendor of one
> of the reviewed C++ Standard library products"
>
> This is not fair ;-)
Indeed, it does give us an unfair advantage in producing
both better libraries and better test suites.
> Anyway, this is a nice starting point but although conformance
> and portability are both important, ultimately, speed and code
> size is more of a concern to real programmers in the field.
That's a judgement call, of course. My priorities are, roughly
in descending order:
correctness
robustness
conformance
performance (speed/size traded off)
YMMV,
Maurice Fox
wrote:
> "joel de guzman" <jo...@interxys.com> wrote in message
> news:9cd1s8$dhkmj$1...@ID-58159.news.dfncis.de...
>
> > "Dinkumware is both a reviewer and a vendor of one
> > of the reviewed C++ Standard library products"
> >
> > This is not fair ;-)
>
> Indeed, it does give us an unfair advantage in producing
> both better libraries and better test suites.
>
> > Anyway, this is a nice starting point but although conformance
> > and portability are both important, ultimately, speed and code
> > size is more of a concern to real programmers in the field.
>
> That's a judgement call, of course. My priorities are, roughly
> in descending order:
>
> correctness
> robustness
> conformance
> performance (speed/size traded off)
>
> YMMV,
>
> P.J. Plauger
> Dinkumware, Ltd.
> http://www.dinkumware.com
Opinions are like a well-known anatomical feature - everybody's got
one, but FWIW, here's mine. I find Mr. Plauger's priorities agree
well with mine. I read a lot of concern about "performance," but most
of the programs that I deal with are completely I/O bound, so that
"performance" is just a chimera.
An anecdote: In a completely tight loop, no I/O, the difference
between having a debug package of mine present but idle (testing a
bool) once each loop, and having it removed completely by a compile
option was only 17 seconds. 17 seconds in 20 million iterations on a
five year old Pentium processor. There's your "performance."
Usually, CPU is free. If performance is really a concern, profile,
then worry.
Maurice
joel de guzman
> Opinions are like a well-known anatomical feature - everybody's got
> one, but FWIW, here's mine. I find Mr. Plauger's priorities agree
> well with mine. I read a lot of concern about "performance," but most
> of the programs that I deal with are completely I/O bound, so that
> "performance" is just a chimera.
That may be true in your case. But as a library provider especially
that of STL, one has to put into consideration the spectrum of users
and many use these libraries in computation intensive applications.
Agreed, correctness and robustness has a higher priority in any case,
but for me, conformance has a lower priority than performance, so I
have to disagree with Mr. Plauger's priority list (a bit). But don't get
me wrong. Conformance very closely follows performance in my list.
Here's mine:
correctness and robustness
performance (speed and code size)
conformance and portability
Indeed this is very subjective. It's like choosing Volvos over Ferraris.
Still even with Mr. Plauger's list and in many others, performance is
and will always be an important issue. You wouldn't say it is not in
your top five concerns now would you? Yet I haven't seen any article
or review addressing this concern in regard to STL implementations
which prompted me to initiate this thread.
> An anecdote: In a completely tight loop, no I/O, the difference
> between having a debug package of mine present but idle (testing a
> bool) once each loop, and having it removed completely by a compile
> option was only 17 seconds. 17 seconds in 20 million iterations on a
> five year old Pentium processor. There's your "performance."
> Usually, CPU is free. If performance is really a concern, profile,
> then worry.
>
This doesn't prove nor mean anything. Give me real world tests.
Benchmarks done in tight loops are misleading and useless in
this modern world of optimizing compilers and CPUs with caches.
Cheers,
Joel de Guzman
James Kanze
> > Opinions are like a well-known anatomical feature - everybody's
> > got one, but FWIW, here's mine. I find Mr. Plauger's priorities
> > agree well with mine. I read a lot of concern about
> > "performance," but most of the programs that I deal with are
> > completely I/O bound, so that "performance" is just a chimera.
> That may be true in your case. But as a library provider especially
> that of STL, one has to put into consideration the spectrum of users
> and many use these libraries in computation intensive applications.
True. But even there, there are probably only a couple of functions
where it is really important. I don't think that anyone would discute
the importance of speed in std::vector::operator[], at least for some
applications. But the constructor of std::vector uses dynamic
allocation; if you are really concerned about creating thousands of
vectors quickly, you won't be using std::vector anyway. And as long
as you get the buffering strategy right, actual IO times are going to
overwhelm any little local tunings in std::filebuf.
[...]
> Still even with Mr. Plauger's list and in many others, performance
> is and will always be an important issue. You wouldn't say it is not
> in your top five concerns now would you? Yet I haven't seen any
> article or review addressing this concern in regard to STL
> implementations which prompted me to initiate this thread.
Perhaps because for the critical operations, like
std::vector::operator[], they are all pretty much the same, and depend
more on the compiler used than the library implementation.
At any rate, there are two aspects to performance: using a n^2
algorithm for sort is going to kill me, but as long as the big-O isn't
changed, I have no performance problems with any of the existing
implementations. It just isn't a consideration.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
James Kanze
> Anyway, this is a nice starting point but although conformance and
> portability are both important, ultimately, speed and code size is
> more of a concern to real programmers in the field.
Are you kidding?
The most importance by far goes to reliability. I must be able to
count on the library working as advertised, without exception. (With
a nuance: if I don't use a feature, that feature doesn't have to be
reliable:-).)
After that, at least in my work, I'd rate portability.
The standard specifies complexity in many cases. Even when it doesn't
(e.g. when appending to a stringstream or a string), it can be an
issue. But for the most part, in my work, even a factor of two or
more in the constant factor isn't important.
As for code size, I've never seen it to be an issue, at least in the
last 10 years. But I would agree that this depends on the application
domain: if you're writing code for an embedded processor, with a
limited amount of ROM, it very definitly is an issue.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
phil hunt
>"joel de guzman" <jo...@interxys.com> wrote in message
>news:9cd1s8$dhkmj$1...@ID-58159.news.dfncis.de...
>
>> "Dinkumware is both a reviewer and a vendor of one
>> of the reviewed C++ Standard library products"
>>
>> This is not fair ;-)
>
>Indeed, it does give us an unfair advantage in producing
>both better libraries and better test suites.
>
>> Anyway, this is a nice starting point but although conformance
>> and portability are both important, ultimately, speed and code
>> size is more of a concern to real programmers in the field.
>
>That's a judgement call, of course. My priorities are, roughly
>in descending order:
>
>correctness
>robustness
>conformance
>performance (speed/size traded off)
>
>YMMV,
Indeed. My top criterion for libraries (simplicity & ease of
understanding) doesn't even appear on your list.
Why do libraries exist? To make it easier for application programmers.
These programmers can use a library more easily if it is easy for
them to understand. This means firstly that the library's interface
be well-designed, and secondly that the library come with decent
documentation.
Only when the library is design well from this point of view can
considerations like correctness apply; who cares if a product
does what it is supposed to do, if what it is supposed to do is
wrong?
(Of course, if you are implementing the C++ Standard Library,
you don't get to choose the library's API, so considerations of
simplicity don't occur).
--
*****[ Phil Hunt ***** ph...@comuno.freeserve.co.uk ]*****
"Mommy, make the nasty penguin go away." -- Jim Allchin, MS head
of OS development, regarding open source software (paraphrased).
joel de guzman
"James Kanze" <James...@dresdner-bank.com> :
> joel de guzman wrote:
>
> > Anyway, this is a nice starting point but although conformance and
> > portability are both important, ultimately, speed and code size is
> > more of a concern to real programmers in the field.
>
> Are you kidding?
No I'm not :-) I have seen the quality of STL implementations improve
dramatically over the years. Take the vector, for example where resizing
is expensive. A good implementation would specialize for built in types
to use fast memory moves, I believe only Metrowerk's CodeWarrior
does this.
>
> The most importance by far goes to reliability. I must be able to
> count on the library working as advertised, without exception. (With
> a nuance: if I don't use a feature, that feature doesn't have to be
> reliable:-).)
I agree. I didn't say that reliability has a lower priority did I?
Yet it's always a balance. I remember the issue on whether
a language should do range checking or not. Why did C choose
not to have range checking? Or how about garbage collection vs.
manual memory management? Why did C++ choose the latter?
Would you say that performance is not an issue in both concerns?
In my other post I mentioned my priorities as:
correctness and robustness
performance (speed and code size)
conformance and portability
>
> After that, at least in my work, I'd rate portability.
>
> The standard specifies complexity in many cases. Even when it doesn't
> (e.g. when appending to a stringstream or a string), it can be an
> issue. But for the most part, in my work, even a factor of two or
> more in the constant factor isn't important.
>
> As for code size, I've never seen it to be an issue, at least in the
> last 10 years. But I would agree that this depends on the application
> domain: if you're writing code for an embedded processor, with a
> limited amount of ROM, it very definitly is an issue.
>
It is for me. If there was a choice between two STL implementations
all things equal except code bloat (STL and templates really bloats
code!), I'll be stupid not to choose the one that produces tighter code.
Same with speed. Hey a factor of 2 in some applications might mean
finishing in a year instead of two.
I still beg to disagree. Performance will always be an issue.
Joel de Guzman
James Kanze
[...]
> >> Anyway, this is a nice starting point but although conformance
> >> and portability are both important, ultimately, speed and code
> >> size is more of a concern to real programmers in the field.
> >That's a judgement call, of course. My priorities are, roughly
> >in descending order:
> >correctness
> >robustness
> >conformance
> >performance (speed/size traded off)
> Indeed. My top criterion for libraries (simplicity & ease of
> understanding) doesn't even appear on your list.
The context is judging implementations of the standard library. I
would agree with your criterion, but it applies largely to the library
definition, not the implementation. (It's true that implementations
of the standard library can differ in safety. The only one with a
significant difference here, I think, is the debugging mode of the
STLPort -- Cay Horstmann's old safe STL.)
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
Pete
> No I'm not :-) I have seen the quality of STL implementations improve
> dramatically over the years. Take the vector, for example where resizing
> is expensive. A good implementation would specialize for built in types
> to use fast memory moves, I believe only Metrowerk's CodeWarrior
> does this.
The Dinkum C++ Library also performs this optimization.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
Pete
> ph...@comuno.freeserve.co.uk (phil hunt) wrote:
> Actually, on the Windows platform, STLport is simpler than others I've
> tried. They use pragmas to make sure the correct library is included. Just
> set whether you're making a debug, non-debug, multi-threaded, etc. build,
> and the correct library will be automagically inserted. With others, you
> have to take an additional step of specifying the correct library, and
> specifying libraries in the incorrect order can lead to conflicts with the
> Microsoft runtime libraries.
The Dinkum C++ Library also performs this service.
P.J. Plauger
Dinkumware, Ltd.
http://www.dinkumware.com
James Kanze
> "James Kanze" <James...@dresdner-bank.com> :
> > joel de guzman wrote:
> > > Anyway, this is a nice starting point but although conformance
> > > and portability are both important, ultimately, speed and code
> > > size is more of a concern to real programmers in the field.
> > Are you kidding?
> No I'm not :-) I have seen the quality of STL implementations
> improve dramatically over the years. Take the vector, for example
> where resizing is expensive. A good implementation would specialize
> for built in types to use fast memory moves, I believe only
> Metrowerk's CodeWarrior does this.
With a good compiler, the *fastest* way to write the move is to use
the typical implementation of std::copy. And a good compiler will
also recognize that destructor loop is a no-op, and suppress it.
The advantage of leaving this optimization to the compiler is that you
get it on almost basic types as well, e.g. struct Point { int x,y; }.
> > The most importance by far goes to reliability. I must be able to
> > count on the library working as advertised, without exception.
> > (With a nuance: if I don't use a feature, that feature doesn't
> > have to be reliable:-).)
> I agree. I didn't say that reliability has a lower priority did I?
You said that "speed and code size is more of a concern." OK, you
didn't mention reliability as the other issue, only portability and
conformance. I don't doubt that there are applications where
portability is of very little importance. I've worked on some. In at
least two such cases, however, we later had problems due to the lack
of portability; someone wanted the software to work on a different
machine. From experience, thus, portability is always important, even
when it isn't part of the immediate concerns.
> Yet it's always a balance. I remember the issue on whether a
> language should do range checking or not. Why did C choose not to
> have range checking?
Poor design? Seriously, at the time C was developped, performance was
more of an issue, because processors were significantly slower, and
compilers were much simpler, and unable to optimize to the point they
do today. Current benchmarks do not show a significant difference in
performance between Java (with range checking) and C++ (without).
> Or how about garbage collection vs. manual memory management? Why
> did C++ choose the latter? Would you say that performance is not an
> issue in both concerns?
Again, modern garbage collecction typically runs faster than a program
with manual memory management. At the time C++ was being developped,
however, there were still serious problems with the generally
available garbage collectors. Performance was only one of the
problems.
> In my other post I mentioned my priorities as:
> correctness and robustness
> performance (speed and code size)
> conformance and portability
> > After that, at least in my work, I'd rate portability.
> > The standard specifies complexity in many cases. Even when it
> > doesn't (e.g. when appending to a stringstream or a string), it
> > can be an issue. But for the most part, in my work, even a factor
> > of two or more in the constant factor isn't important.
> > As for code size, I've never seen it to be an issue, at least in
> > the last 10 years. But I would agree that this depends on the
> > application domain: if you're writing code for an embedded
> > processor, with a limited amount of ROM, it very definitly is an
> > issue.
> It is for me. If there was a choice between two STL implementations
> all things equal except code bloat (STL and templates really bloats
> code!), I'll be stupid not to choose the one that produces tighter
> code.
All things are never equal. Reducing code bloat will forceably have
costs in other areas.
> Same with speed. Hey a factor of 2 in some applications might mean
> finishing in a year instead of two.
Agreed. There are some special applications where this is true.
Typically, however, you should be able to get that factor 2 with
careful tuning of the critical path.
> I still beg to disagree. Performance will always be an issue.
An issue. But it shouldn't be a major one, provided the libraries are
reasonably written. (It's possible, for example, to make a bubble
sort O(n log n), by adding dummy code to waste time when the number of
elements is small. I would not consider this a reasonable
implementation.)
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
joel de guzman
"James Kanze" <James...@dresdner-bank.com> wrote:
> With a good compiler, the *fastest* way to write the move is to use
> the typical implementation of std::copy. And a good compiler will
> also recognize that destructor loop is a no-op, and suppress it.
>
> The advantage of leaving this optimization to the compiler is that you
> get it on almost basic types as well, e.g. struct Point { int x,y; }.
Ok. But I was referring to resizing of vectors where copying takes
place behind the scenes. It's certainly absurd to benchmark vector
[] indexing. The most expensive operation for vectors is resizing.
> From experience, thus, portability is always important, even
> when it isn't part of the immediate concerns.
Yes it is. I believe so. Even when I have to call the OS directly,
(with a GUI API for example) I have to go through all the trouble
of setting up an abstraction layer with the future in mind.
>
> > Yet it's always a balance. I remember the issue on whether a
> > language should do range checking or not. Why did C choose not to
> > have range checking?
>
> Poor design? Seriously, at the time C was developped, performance was
> more of an issue, because processors were significantly slower, and
> compilers were much simpler, and unable to optimize to the point they
> do today. Current benchmarks do not show a significant difference in
> performance between Java (with range checking) and C++ (without).
:-)... jaaaavaaa... Hmmm, I'll have to see to believe. Compiled to native
machine code?
>
> > Or how about garbage collection vs. manual memory management? Why
> > did C++ choose the latter? Would you say that performance is not an
> > issue in both concerns?
>
> Again, modern garbage collecction typically runs faster than a program
> with manual memory management. At the time C++ was being developped,
> however, there were still serious problems with the generally
> available garbage collectors. Performance was only one of the
> problems.
Thus a concern. yesterday, today, and IMO tomorrow, even with
tera-MIPS chips.
>
> > It is for me. If there was a choice between two STL implementations
> > all things equal except code bloat (STL and templates really bloats
> > code!), I'll be stupid not to choose the one that produces tighter
> > code.
>
> All things are never equal. Reducing code bloat will forceably have
> costs in other areas.
Yes I agree. And that's the whole point I was raising. I was hoping for
a comprehensive analysis and comparison of various STL implementations
that addresses *all* these issues.
> > Same with speed. Hey a factor of 2 in some applications might mean
> > finishing in a year instead of two.
>
> Agreed. There are some special applications where this is true.
>
> Typically, however, you should be able to get that factor 2 with
> careful tuning of the critical path.
>
> > I still beg to disagree. Performance will always be an issue.
>
> An issue. But it shouldn't be a major one, provided the libraries are
> reasonably written. (It's possible, for example, to make a bubble
> sort O(n log n), by adding dummy code to waste time when the number of
> elements is small. I would not consider this a reasonable
> implementation.)
>
Agreed.
Joel de Guzman
phil hunt
>phil hunt wrote:
>
> [...]
>> >> Anyway, this is a nice starting point but although conformance
>> >> and portability are both important, ultimately, speed and code
>> >> size is more of a concern to real programmers in the field.
>
>> >That's a judgement call, of course. My priorities are, roughly
>> >in descending order:
>
>> >correctness
>> >robustness
>> >conformance
>> >performance (speed/size traded off)
>
>> Indeed. My top criterion for libraries (simplicity & ease of
>> understanding) doesn't even appear on your list.
>
>The context is judging implementations of the standard library. I
>would agree with your criterion, but it applies largely to the library
>definition, not the implementation.
That's why I put a proviso at the end of my post.
If course, if the definition of a library is poor (and I would
argue this is true of the STL to some extent), then that affects the
maximum possible quality of any implementation.
Consider: the purpose of a library is to make application programming
easier, because the programmer doesn't have to reinvent the wheel.
Therefore the quality of a library is the extent to which it achieves that
goal.
--
*****[ Phil Hunt ***** ph...@comuno.freeserve.co.uk ]*****
Pstream class library for C++: a Parsing Stream library that
facilitates writing lexical analysers and other programs
that parse data files. Available on an open source license from
<http://www.vision25.demon.co.uk/oss/phlib/intro.html>
James Kanze
> Consider: the purpose of a library is to make application
> programming easier, because the programmer doesn't have to reinvent
> the wheel. Therefore the quality of a library is the extent to
> which it achieves that goal.
Correct.
Note that we encounter here somewhat the same sort of problem as we do
with defining user friendliness. What is "friendly" to a first-time
user will generally frustrate an experienced user. For tools I only
use rarely (like a debugger), I want first-time "user friendliness",
but for tools that I use daily, like the editor... nothing beats viper
mode under emacs.
In the case of libraries, similar considerations are involved. A
library designed to access little used facilities should be
ultra-simple to understand and use. In the case of something
fundamental like the STL, however, it is reasonable to require a bit
more experience to use it correctly if we obtain more power in return.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
James Kanze
> "James Kanze" <James...@dresdner-bank.com> wrote:
> > With a good compiler, the *fastest* way to write the move is to
> > use the typical implementation of std::copy. And a good compiler
> > will also recognize that destructor loop is a no-op, and suppress
> > it.
> > The advantage of leaving this optimization to the compiler is that
> > you get it on almost basic types as well, e.g. struct Point { int
> > x,y; }.
> Ok. But I was referring to resizing of vectors where copying takes
> place behind the scenes.
Whether it is behind the scenes or not, the code will be compiled for
each type. With special optimization for each type. Almost every
compiler, for example, will know that the pointers are aligned for the
type in question, and generate its loops accordingly; memcpy must do
this check dynamically, or copy bytes. Similarly, memcpy, since it
knows nothing of the actual types involved, must be prepared to deal
with an odd number of bytes at the end. I doubt that memcpy could
possibly be faster except for types smaller than int. And even then,
a really good compiler could determine that the pointers were all the
results of a new, and thus know that they were aligned. An
exceptional compiler could even analyse the allocation strategy,
determine that all allocations were a multiple of n, and skip the
check for the odd bytes at the end; I don't expect to see compilers
that good anytime soon, though.
> It's certainly absurd to benchmark vector [] indexing. The most
> expensive operation for vectors is resizing.
Given that most vectors are never resized, it's certainly absurd to
benchmark resizing:-).
It all depends on the application. If the application is using
vectors as a replacement for C style arrays, and the vectors are
reasonably large, it is probable that the times will be dominated by
operator[]. (If the application is using a lot of very small vectors
which come and go, the times may be dominated by construction.)
> > From experience, thus, portability is always important, even when
> > it isn't part of the immediate concerns.
> Yes it is. I believe so. Even when I have to call the OS directly,
> (with a GUI API for example) I have to go through all the trouble of
> setting up an abstraction layer with the future in mind.
> > > Yet it's always a balance. I remember the issue on whether a
> > > language should do range checking or not. Why did C choose not
> > > to have range checking?
> > Poor design? Seriously, at the time C was developped, performance
> > was more of an issue, because processors were significantly
> > slower, and compilers were much simpler, and unable to optimize to
> > the point they do today. Current benchmarks do not show a
> > significant difference in performance between Java (with range
> > checking) and C++ (without).
> :-)... jaaaavaaa... Hmmm, I'll have to see to believe. Compiled to
> native machine code?
Yes and no. Run under JVM, but modern JVM's internally compile the
byte code to native, then execute the native.
I've seen the benchmarks. I've even verified them on my
implementation (g++ 2.95.2 vs. JDK 1.2.2 with JIT, under Windows NT).
I might add that knowing something about the technologies involved, I
wasn't really surprised. On other platforms, C++ compiler technology
may be more mature, and the Java technology is definitly less mature,
so the results will probably be different.
Whether the current techologies really scale is another question.
It's relatively easy for a compiler to suppress the bounds checking in
cases like:
for ( int i = 0 ; i < array.length ; ++ i ) {
// ...
}
Start passing arrays and their indexes around separately (because you
are working with sub-arrays in a larger array, for example), and the
analysis is more complex. But not impossible.
(Note that all of the benchmarks involve arrays of basic types. Where
Java really slows down, at least at present, is when you need arrays
of things like "struct Point { int x , y ; }". Currently in Java, it
is both awkward to write the code which creates the instances, and the
performance takes a real hit. Time critical Java programs can still
use the old Fortran technique of declaring two arrays, one with the
x's, and one with the y's, and achieve performance at the C++ level,
but at a significant cost to readability.)
> > > Or how about garbage collection vs. manual memory management?
> > > Why did C++ choose the latter? Would you say that performance
> > > is not an issue in both concerns?
> > Again, modern garbage collecction typically runs faster than a
> > program with manual memory management. At the time C++ was being
> > developped, however, there were still serious problems with the
> > generally available garbage collectors. Performance was only one
> > of the problems.
> Thus a concern. yesterday, today, and IMO tomorrow, even with
> tera-MIPS chips.
You seemed to have missed the tense of the verb. Performance *was* a
concern. The one actual benchmark I've seen comparing a modern
garbage collection with manual allocation showed garbage collection to
be faster. (The benchmark consisted of using the Boehm collector with
X Windows, which is written in C. Obviously, a collector in a
language designed for collection can do even better.)
Early garbage collection had a bad reputation not so much for
performance per se, but for its tendancy to lock up the machine from
time to time; the run-time it did use occurred in a solid block when
nothing else happened. This is not a problem for modern incremental
garbage collectors, however. (I use a lisp based editor which uses
garbage collection internally. When I first tried it, about 10 years
ago, it often stalled with the message "garbage collecting". Today,
even on my 8 year old Sparc, I'm totally unaware of the garbage
collection.)
I, for one, certainly hope that C++ will make some form of garbage
collection available. (No one should be required to use it, of
course. Ideally, I'd like to see it the default, with a requirement
to do something additional to not use it, but I don't think that this
will be possible and still maintain backwards compatibility.)
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
Maciej Sobczak
"James Kanze" <James...@dresdner-bank.com> wrote in message
news:3AF25B0C...@dresdner-bank.com...
> > :-)... jaaaavaaa... Hmmm [...]
>
> > > > Or how about garbage collection vs. manual memory management?
> > > > Why did C++ choose the latter? Would you say that performance
> > > > is not an issue in both concerns?
>
> > > Again, modern garbage collecction typically runs faster than a
> > > program with manual memory management. At the time C++ was being
> > > developped, however, there were still serious problems with the
> > > generally available garbage collectors. Performance was only one
> > > of the problems.
>
> > Thus a concern. yesterday, today, and IMO tomorrow, even with
> > tera-MIPS chips.
>
> I, for one, certainly hope that C++ will make some form of garbage
> collection available. (No one should be required to use it, of
> course. Ideally, I'd like to see it the default, with a requirement
> to do something additional to not use it, but I don't think that this
> will be possible and still maintain backwards compatibility.)
Here are my thoughts:
I wonder how can it be that on some benchmarks, the garbage collector can be
faster that the manual memory management.
The only reason for this is clear after looking at the code:
// some bottleneck
for (...; ...; ...)
{
p = new SomeClass();
// do something
// the line below is not present for GC
delete p;
}
The GC like in Java (and I suppose any sane GC) follows the "lazy
destruction" strategy.
And like "lazy evaluation", it can add to the overwhelming speed of Java.
;-)
Why? Because the actual destruction (collection) takes place off the peaks
generated by the code, so that this part of memory management just sneaks
out of the benchamark. If GC is driven by some other thread of execution,
which has lower prority than the worker thread, it will wait for its turn to
have a chance to collect the garbage, giving the impression that the code
runs "faster".
The problem (with those bechmarks) is that when any conscious programmer
finds the code above to be a real performance bottleneck, he/she will
certainly resort to some other solutions:
1. object reusing
2. memory pool
3. custom new/delete
4. others?
(which can speed up things orders of magnitude more that any GC)
The real power of the language comes not from the fact that it *has* GC, but
from the fact, that it *can* have (bot does not have to).
I can even imagine the "lazy destruction" scheme implemented in C++. Just
push the pointer to some queue (instead of deleting it on the spot) and have
another thread popping pointers and making the actual deletion. Problem? No.
The smart pointer that will do the push of its pointee automatically when
going out of scope is not a problem, too.
I can see no reason to have a native GC in C++. I'm perfectly happy with the
flexibility I have now, so that I *can* have whatever I want, but I do not
have to. Especially, I *can* make choices.
Moreover, the real reason I would place delete operator on the spot (and not
use lazy destruction) is that operator delete does *much more* than just
reclaiming memory. And thanks to that "much more" I can also see no point in
making such comparisons.
Maciej Sobczak, http://www.cern.ch/Maciej.Sobczak
"in theory, there is no difference between theory and practice - but in
practice, there is"
Dennis Yelle
I am really surprised.
I thought all modern compilers inlined memcpy,
and thus could apply all of the optimizations you
refer to above.
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/
joel de guzman
>Performance was only one
> > > of the problems.
>
> > Thus a concern. yesterday, today, and IMO tomorrow, even with
> > tera-MIPS chips.
>
> You seemed to have missed the tense of the verb. Performance *was* a
> concern. The one actual benchmark I've seen comparing a modern
> garbage collection ... [snip]
Please allow me to re-focus the issue I was trying to discus on. I would not
want to shift to another GC vs. Manual Mem. Management now. This is
already being discused in other threads.
Again, back to the performance issue. Are you implying that performance
in terms of speed/size is not an issue anymore in relation to STL
implementations?
Joel de Guzman
Dietmar Kuehl
this thread gives some interesting view points, eg. that performance
does not matter in I/O bound programs. Given that there are differences
in performance of I/O operations of a factor of ten (no, I'm not
assuming that the data is cached already somewhere; I'm speaking of
eg. writing a new file containing formatted data...) I doubt that
there is indeed no performance issue with the implementation of the
standard library...
Also, I have seen a distinction between "correctness" and
"conformance". Maybe someone can point out what specification a
correct but non conforming implementation correctly implements? Put
differently: Conformance to the standard is equivalent to correct
implementation of the standard library.
In addition, any library implementer faces an essential problem: [S]He
does not know how the library is used in the application. Thus, I think
that everything should be implemented to performance with as low
overhead as possible because everything might be used in a performance
critical path in an application. Sometimes optimizations for what is
expected to be the "normal" case conflict with specific uses but
unlikely uses of the library (eg. my implementation assumes in some
parts that locale objects are created infrequently and used a lot; if
this does not hold, a certain optimization actually imposes
considerable overhead). In such cases it is useful to have the user
choose whether the optimization is desired. Actually, in general it is
useful to have the user choose certain implementation aspects, eg.
whether to use multi-threading, various forms of safety checking, etc.
Also note, that even if the system is actually faster than systems have
been in the past, this does not mean that we have enough time: The
requirements on performance and what is done underneath simply
increase! There is no such thing as "fast enough" if it takes more than
no time or something "small enough" if it takes more than zero memory.
Of course, priorities may be on other aspects (eg.
conformance/correcntess) but performance always was, is, and will be a
criterium.
It is interesting to note that "compile time" is also a performance
issue, one which most implementations do not optimize for.
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
phil hunt
>phil hunt wrote:
>
>> Consider: the purpose of a library is to make application
>> programming easier, because the programmer doesn't have to reinvent
>> the wheel. Therefore the quality of a library is the extent to
>> which it achieves that goal.
>
>Correct.
>
>Note that we encounter here somewhat the same sort of problem as we do
>with defining user friendliness. What is "friendly" to a first-time
>user will generally frustrate an experienced user. For tools I only
>use rarely (like a debugger), I want first-time "user friendliness",
>but for tools that I use daily, like the editor... nothing beats viper
>mode under emacs.
>
>In the case of libraries, similar considerations are involved. A
>library designed to access little used facilities should be
>ultra-simple to understand and use. In the case of something
>fundamental like the STL, however, it is reasonable to require a bit
>more experience to use it correctly if we obtain more power in return.
I agree, there's a trade off between ease of use for a beginner
and ease of use for an expert. But some features of the STL could
be improved. For example, sort routines must take two arguments
specifying the beginning and end of the block to be sorted -- 99
times out of 100 the user will want to sort the whole vector (or
whatever), so this should be the default (C++ allows default
values in parameters, so it should be obvious to use this
feature).
--
*****[ Phil Hunt ***** ph...@comuno.freeserve.co.uk ]*****
Pstream class library for C++: a Parsing Stream library that
facilitates writing lexical analysers and other programs
that parse data files. Available on an open source license from
<http://www.vision25.demon.co.uk/oss/phlib/intro.html>
John Potter
wrote:
> I agree, there's a trade off between ease of use for a beginner
> and ease of use for an expert. But some features of the STL could
> be improved. For example, sort routines must take two arguments
> specifying the beginning and end of the block to be sorted -- 99
> times out of 100 the user will want to sort the whole vector (or
> whatever), so this should be the default (C++ allows default
> values in parameters, so it should be obvious to use this
> feature).
Beginners need to learn that algorithms work on ranges not containers.
Can you supply the "obvious" feature by filling in the defaults?
template <Riter>
void sort (Riter first = ______, Riter last = ______);
Sort requires random access iterators and list has an inconsistent
member which only sorts the entire list. An overload/specialization
of sort for list seems impossible; however, a consistent member of
list which takes a range is possible. That could use defaults, but
then the other containers would be lacking.
If you remove the containers from STL, it is a beautiful consistent
system. I don't see much value without the containers and then the
beauty goes away.
John
Nick Thurn
>
> Beginners need to learn that algorithms work on ranges not containers.
> Can you supply the "obvious" feature by filling in the defaults?
>
> template <Riter>
> void sort (Riter first = ______, Riter last = ______);
>
> Sort requires random access iterators and list has an inconsistent
> member which only sorts the entire list. An overload/specialization
> of sort for list seems impossible; however, a consistent member of
> list which takes a range is possible. That could use defaults, but
> then the other containers would be lacking.
>
What about:
// Warning untested code!!!
template<class C>
void sort(C& container)
{
sort(container.begin(),container.end());
}
template<class C, class Comp>
void sort(C& container,Comp comp)
{
sort(container.begin(),container.end(),comp);
}
template <class T>
void sort(list<T>& somelist)
{
somelist.sort();
}
template <class T, class Comp>
void sort(list<T>& somelist,Comp comp)
{
somelist.sort(comp);
}
just a thought, as devil's advocate.
Eugene Karpachov
>If you remove the containers from STL, it is a beautiful consistent
>system.
It is very incomplete to be useful. For example: STL is functor-oriented, but
binders system is very poor; STL is value-oriented (opposite to
pointer-oriented), but smart/shared pointers are completely missed etc. The
programmer wishing to use power of STL must reinvent the wheel and implement
the features himself every time. (Yes, I know about Boost - but it is another
issue.)
--
jk
James Kanze
> "James Kanze" <James...@dresdner-bank.com> wrote in message
> news:3AF25B0C...@dresdner-bank.com...
> > I, for one, certainly hope that C++ will make some form of garbage
> > collection available. (No one should be required to use it, of
> > course. Ideally, I'd like to see it the default, with a
> > requirement to do something additional to not use it, but I don't
> > think that this will be possible and still maintain backwards
> > compatibility.)
> Here are my thoughts: I wonder how can it be that on some
> benchmarks, the garbage collector can be faster that the manual
> memory management.
Typically, it is specially tuned for the platform, and receives some
help from the OS. Manual memory management isn't cheap. For example,
many programmers, myself included, use reference counted pointers
extensively. This entails a cost at each copy, that garbage
collection avoids.
Whether garbage collection or manual memory management has better
performance will depend on:
- the implementation of the garbage collection,
- the implementation of the allocation in the manual system, and
- the pattern of accesses and use in the application.
Garbage collection tends to perform best when there are a lot of short
term allocations, objects that are allocated and "freed" between two
cycles of garbage collection are never seen by the garbage collector.
> The only reason for this is clear after looking at the code:
> // some bottleneck
> for (...; ...; ...)
> {
> p = new SomeClass();
> // do something
> // the line below is not present for GC
> delete p;
> }
> The GC like in Java (and I suppose any sane GC) follows the "lazy
> destruction" strategy.
> And like "lazy evaluation", it can add to the overwhelming speed of
Java. > ;-)
> Why? Because the actual destruction (collection) takes place off the
> peaks generated by the code, so that this part of memory management
> just sneaks out of the benchamark. If GC is driven by some other
> thread of execution, which has lower prority than the worker thread,
> it will wait for its turn to have a chance to collect the garbage,
> giving the impression that the code runs "faster".
This is a separate issue, but one that is often important. I don't
know how fast the emacs garbage collection is, but I never notice it
now. Basically, it springs into action anytime the editor doesn't
have anything else to do, for example, when it is waiting for keyboard
input. This means that there is never very much to collect, and when
I need the memory, it is there, having already been collected.
The actual benchmarks, however, measured CPU time used by the
application. Not response times.
An additional issue is that memory allocation with a copying collector
can be incredibly fast, almost as fast as allocation of a local
variable on the stack. Copying collectors can't be used with C++,
because a copying collector has to be able to find all of the pointers
and correct them. And I don't see any reasonable way of changing
that.
> The problem (with those bechmarks) is that when any conscious
> programmer finds the code above to be a real performance bottleneck,
> he/she will certainly resort to some other solutions:
> 1. object reusing
> 2. memory pool
> 3. custom new/delete
> 4. others?
> (which can speed up things orders of magnitude more that any GC)
If it is a bottleneck with garbage collection, then the same
strategies may apply.
> The real power of the language comes not from the fact that it *has*
> GC, but from the fact, that it *can* have (bot does not have to).
Formally, it can't. If you want to use the Boehm collector, you have
to avoid certain legal constructs. (Most people, I think, would avoid
them anyway.)
In practice, because it is NOT part of the language, it is very
difficult to convince customers to use the collector.
> I can even imagine the "lazy destruction" scheme implemented in
> C++. Just push the pointer to some queue (instead of deleting it on
> the spot) and have another thread popping pointers and making the
> actual deletion. Problem? No. The smart pointer that will do the
> push of its pointee automatically when going out of scope is not a
> problem, too.
And what would that bring? It will certainly increase C++ time,
totally.
> I can see no reason to have a native GC in C++. I'm perfectly happy
> with the flexibility I have now, so that I *can* have whatever I
> want, but I do not have to. Especially, I *can* make choices.
> Moreover, the real reason I would place delete operator on the spot
> (and not use lazy destruction) is that operator delete does *much
> more* than just reclaiming memory. And thanks to that "much more" I
> can also see no point in making such comparisons.
How often does the delete operator really do more than memory
management? In my code, about 90% of the destructors are only there
for memory management; with garbage collection, they'd be empty. In
the other cases, of course, delete should be used. Except that I find
that most of the objects in the other cases are on the stack anyway.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
phil hunt
>On 6 May 2001 09:35:11 -0400, ph...@comuno.freeserve.co.uk (phil hunt)
>wrote:
>
>> I agree, there's a trade off between ease of use for a beginner
>> and ease of use for an expert. But some features of the STL could
>> be improved. For example, sort routines must take two arguments
>> specifying the beginning and end of the block to be sorted -- 99
>> times out of 100 the user will want to sort the whole vector (or
>> whatever), so this should be the default (C++ allows default
>> values in parameters, so it should be obvious to use this
>> feature).
>
>Beginners need to learn that algorithms work on ranges not containers.
>Can you supply the "obvious" feature by filling in the defaults?
>
>template <Riter>
>void sort (Riter first = ______, Riter last = ______);
No, I've never heard of a "Riter". The way I would achieve this is
either by having the container classes implement a
container.sort() method or by them having a defaultFirst() and
defaultLast() methods; so in this case the Riter class would
supply its Riter::defualtFirst() and Riter::defaultLast() methods.
>Sort requires random access iterators and list has an inconsistent
>member which only sorts the entire list.
There's no reason why a list and a vector can't use the same
interface. Of course, if they did then some operations would be
slow for a vector (e.g. inserting a new object somewhere in the
middle) and some operations slow for a list (e.g. accessing an
item based on its index). So which to use would depend on which
operatinos were performed the most often. An application
programmer could create his containers as vectors, and then time
the application and see if it ran faster when the containers were
implemented as lists.
--
*****[ Phil Hunt ***** ph...@comuno.freeserve.co.uk ]*****
Pstream class library for C++: a Parsing Stream library that
facilitates writing lexical analysers and other programs
that parse data files. Available on an open source license from
<http://www.vision25.demon.co.uk/oss/phlib/intro.html>
Pete Becker
>
> John Potter wrote:
> >
> > Beginners need to learn that algorithms work on ranges not containers.
> > Can you supply the "obvious" feature by filling in the defaults?
> >
> > template <Riter>
> > void sort (Riter first = ______, Riter last = ______);
> >
> > Sort requires random access iterators and list has an inconsistent
> > member which only sorts the entire list. An overload/specialization
> > of sort for list seems impossible; however, a consistent member of
> > list which takes a range is possible. That could use defaults, but
> > then the other containers would be lacking.
> >
> John,
>
> What about:
>
> // Warning untested code!!!
> template<class C>
> void sort(C& container)
> {
> sort(container.begin(),container.end());
> }
Technically, that's not using defaults. It's providing a completely
different function. There's nothing wrong with that, of course. But
given the simplicity of writing this, and the inherent confusion from
having two different ways of doing exactly the same thing, what would be
gained by adding it to the standard library?
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
James Kanze
> In addition, any library implementer faces an essential problem:
> [S]He does not know how the library is used in the
> application. Thus, I think that everything should be implemented to
> performance with as low overhead as possible because everything
> might be used in a performance critical path in an application.
In an ideal world, the library would be 100% optimized, with no
errors. As we all know, however, this requires an infinite amount of
work and testing, and most implementers don't have infinite resources.
I know of no library that is 100% correct, and I know of none in which
there aren't places where performance could be improved.
The only question is where to apply the available resources.
[...]
> It is interesting to note that "compile time" is also a performance
> issue, one which most implementations do not optimize for.
Good point, which I tend to forget. For people in research, it isn't
unusual to compile a program 4 or 5 times, then just run it once.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
Mary K. Kuhner
>Also, I have seen a distinction between "correctness" and
>"conformance". Maybe someone can point out what specification a
>correct but non conforming implementation correctly implements? Put
>differently: Conformance to the standard is equivalent to correct
>implementation of the standard library.
I think there is a practical difference between, say, one of
the compilers I use not implementing vector.assign() at all,
and implementing it but having it cause a memory error. The
first one is a pest. The second one is a disaster, and I
ought to throw away a library that does such things.
That's the difference between conformance and correctness.
A library with some clear, well-documented differences from
Standard has uses, though it is less useful than a Standard
one. A library with bugs is a frightful thing.
>Also note, that even if the system is actually faster than systems have
>been in the past, this does not mean that we have enough time: The
>requirements on performance and what is done underneath simply
>increase!
I'm afraid so. I work on problems that are NP-complete; the
time to finish them increases in a terrifying way for each increase
in the size of the data set, and there will *always* be data
sets we can't analyze in less than geological time.
It's hard to convince users of this. They keep insisting on
collecting more data.
Incidentally, I was curious to see vector.operator[] come up
in this discussion. We recently found to our surprise that
this was among our top ten functions in profiling the current
project. I guess it gets used *way* too much, but this is
hard to fix. The dark side of the syntactic sugar of
overloaded operators is that there is no obvious way to search
for them....
Mary Kuhner mkku...@genetics.washington.edu
James Kanze
> Again, back to the performance issue. Are you implying that
> performance in terms of speed/size is not an issue anymore in
> relation to STL implementations?
For most applications, at least, no. STL has a definite cost in size,
but generally speaking, performs exceptionally well in terms of speed.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
James Kanze
> I thought all modern compilers inlined memcpy, and thus could apply
> all of the optimizations you refer to above.
I don't know of any RISC compiler which inlines it.
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
John Potter
wrote:
> > Sort requires random access iterators and list has an inconsistent
> > member which only sorts the entire list. An overload/specialization
> > of sort for list seems impossible; however, a consistent member of
> > list which takes a range is possible. That could use defaults, but
> > then the other containers would be lacking.
>
> What about:
>
> // Warning untested code!!!
> template<class C>
> void sort(C& container)
> {
> sort(container.begin(),container.end());
> }
[snip]
> just a thought, as devil's advocate.
Well, yes. That would make a very different STL. There are no
algorithms which take containers. Maybe that is what is needed.
John
John Potter
wrote:
> On 6 May 2001 14:55:54 -0400, John Potter <jpo...@falcon.lhup.edu> wrote:
> >On 6 May 2001 09:35:11 -0400, ph...@comuno.freeserve.co.uk (phil hunt)
> >wrote:
> >
> >> I agree, there's a trade off between ease of use for a beginner
> >> and ease of use for an expert. But some features of the STL could
> >> be improved. For example, sort routines must take two arguments
> >> specifying the beginning and end of the block to be sorted -- 99
> >> times out of 100 the user will want to sort the whole vector (or
> >> whatever), so this should be the default (C++ allows default
> >> values in parameters, so it should be obvious to use this
> >> feature).
> >
> >Beginners need to learn that algorithms work on ranges not containers.
> >Can you supply the "obvious" feature by filling in the defaults?
> >
> >template <Riter>
> >void sort (Riter first = ______, Riter last = ______);
>
> No, I've never heard of a "Riter".
Then substitute T, it is a template parameter. You do understand that
the STL is based on algorithms which take iterators?
> The way I would achieve this is
> either by having the container classes implement a
> container.sort() method or by them having a defaultFirst() and
> defaultLast() methods; so in this case the Riter class would
> supply its Riter::defualtFirst() and Riter::defaultLast() methods.
These are static members? There are no objects available to call
members in the expression sort<X>(). Remember that you wanted to be
able to call sort with defaults. You can't even name the object. We
usually use sort by naming the object and using the default first and
last iterators by writing sort(v.begin(), v.end()).
You obviously are using something other than the standard C++ library.
If you would like to replace it with something else, then say that
rather than claiming that it can be doctored into something else by
using default values where there are none.
See above. There are no algorithms which work on containers. There
is an STL concept. Replacement requires a new concept not some
fictional patches. Also note that your desire to add member functions
to the existing containers, and future developements, must include the
other forty odd algorithms not just sort.
John
Nick Thurn
> Nick Thurn wrote:
> >
> > What about:
> >
> > // Warning untested code!!!
> > template<class C>
> > void sort(C& container)
> > {
> > sort(container.begin(),container.end());
> > }
>
> different function. There's nothing wrong with that, of course. But
> given the simplicity of writing this, and the inherent confusion from
> having two different ways of doing exactly the same thing, what would be
> gained by adding it to the standard library?
Agree, note I was acting devil's advocate.
James Kanze
> There are no algorithms which work on containers. There is an STL
> concept. Replacement requires a new concept not some fictional
> patches.
It probably wouldn't be too difficult to add direct support for
containers. Everywhere an algorithm takes a pair of vectors, add an
overload which takes a container, instead of a pair of vectors, and
calls the existing algorithm with container.begin(), container.end().
--
James Kanze mailto:ka...@gabi-soft.de
Conseils en informatique orientée objet/
Beratung in objektorientierter Datenverarbeitung
Ziegelhüttenweg 17a, 60598 Frankfurt, Germany Tel. +49(069)63198627
Maciej Sobczak
> How often does the delete operator really do more than memory
> management? In my code, about 90% of the destructors are only there
> for memory management; with garbage collection, they'd be empty. In
> the other cases, of course, delete should be used. Except that I find
> that most of the objects in the other cases are on the stack anyway.
Yes, it's true.
We have this functionality thanks to the notion of automatic objects (which
have well defined point of destruction).
However, I think that the semantics of automatic objects is one of most
important aspects of C++, which differentiates thinking in C++ from thinking
in Java, for example.
What I'm up to is the fact, that we cannot afford *two* semantics: one for
automatic objects (so that we can think in terms of scope and lifetime) and
one for objects on the free store (so that the GC would be more natural).
Certainly, we cannot afford to resign from the first.
Or, why not (first solution)?
If programmers find themselves struggling hard to make objects only
stack-allocatable or free-store-allocatable by using some language hacks,
then maybe we need this differentiation on the language level? What about
objects designed for free-store (and garbage-collected, arrrrgh...) and
designed for stack?
No new keywords are needed. There is an old keyword "auto" that nobody uses:
// warning: not valid C++
class auto Transaction
{
// ...
};
class SomeOtherStuff
{
// ...
};
later:
void foo()
{
Transaction t;
SomeOtherStuff p = new SomeOtherStuff();
// ...
}
Here, object 't' is destructed at the and of foo (because it's automatic),
but we don't care about the object pointed to by 'p', because it gets
collected (at some time for which we don't care either). The GC for this
case would be probably more natural in construction than any other approach,
because SomeOtherStuff has it written in its *type*, thus banning some other
language constructs that would render GC difficult or impossible to write.
Just thinking...
Maciej Sobczak, http://www.cern.ch/Maciej.Sobczak
"in theory, there is no difference between theory and practice - but in
practice, there is"
John Potter
<James...@dresdner-bank.com> wrote:
> John Potter wrote:
>
> > There are no algorithms which work on containers. There is an STL
> > concept. Replacement requires a new concept not some fictional
> > patches.
>
> It probably wouldn't be too difficult to add direct support for
> containers. Everywhere an algorithm takes a pair of vectors, add an
> overload which takes a container, instead of a pair of vectors, and
> calls the existing algorithm with container.begin(), container.end().
s/vector/iterator/
Yes, but see also Pete's response to Nick.
It's not likely worth it, but it would open the door for algorithms
which can't be implemented on ranges. Erase_if is may favorite. Is
that kind of change a danger to the simplicity of the standard
library?
John
Carlos Moreno
James Kanze wrote:
>
> It probably wouldn't be too difficult to add direct support for
> containers. Everywhere an algorithm takes a pair of vectors, add an
> overload which takes a container, instead of a pair of vectors
You meant a pair of iterators, right? :-)
Carlos
--
Pete Becker
>
> John Potter wrote:
>
> > There are no algorithms which work on containers. There is an STL
> > concept. Replacement requires a new concept not some fictional
> > patches.
>
> It probably wouldn't be too difficult to add direct support for
> containers. Everywhere an algorithm takes a pair of vectors, add an
> overload which takes a container, instead of a pair of vectors, and
> calls the existing algorithm with container.begin(), container.end().
>
True, but that misses the point. STL algorithms operate on sequences.
Containers are one way of creating sequencres. Algorithms that operate
directly on containers are foreign to STL as it is currently designed.
On the other hand, those who think that providing two iterators is too
large an imposition can easily write their own template to do it for
them:
template <class Container> void sort(Container c) { sort(c.begin(),
c.end()); }
Since it's so simple, there's no need to add it to the standard library.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
phil hunt
>On 7 May 2001 12:03:27 -0400, ph...@comuno.freeserve.co.uk (phil hunt)
>wrote:
>
>> On 6 May 2001 14:55:54 -0400, John Potter <jpo...@falcon.lhup.edu> wrote:
>> >On 6 May 2001 09:35:11 -0400, ph...@comuno.freeserve.co.uk (phil hunt)
>> >wrote:
>> >
>> >> I agree, there's a trade off between ease of use for a beginner
>> >> and ease of use for an expert. But some features of the STL could
>> >> be improved. For example, sort routines must take two arguments
>> >> specifying the beginning and end of the block to be sorted -- 99
>> >> times out of 100 the user will want to sort the whole vector (or
>> >> whatever), so this should be the default (C++ allows default
>> >> values in parameters, so it should be obvious to use this
>> >> feature).
>> >
>> >Beginners need to learn that algorithms work on ranges not containers.
>> >Can you supply the "obvious" feature by filling in the defaults?
>> >
>> >template <Riter>
>> >void sort (Riter first = ______, Riter last = ______);
>>
>> No, I've never heard of a "Riter".
>
>Then substitute T, it is a template parameter. You do understand that
>the STL is based on algorithms which take iterators?
Sort-of. I've used the STL, but not extensively.
I find it a lot harder to learn that the equivalent classes in Smalltalk
or Python. Though partly that's because C++ is a more low-level language
(which is not a criticism of it; merely noting that it is designed for
a different problem domain).
>> The way I would achieve this is
>> either by having the container classes implement a
>> container.sort() method or by them having a defaultFirst() and
>> defaultLast() methods; so in this case the Riter class would
>> supply its Riter::defualtFirst() and Riter::defaultLast() methods.
>
>These are static members? There are no objects available to call
>members in the expression sort<X>(). Remember that you wanted to be
>able to call sort with defaults. You can't even name the object. We
>usually use sort by naming the object and using the default first and
>last iterators by writing sort(v.begin(), v.end()).
If there are defualts, then why couldn't the STL just include a
sort routine that uses them:
template<class SomeCollection>
void sort (SomeCollection& col){
sort(col.begin(), col.end());
}
>See above. There are no algorithms which work on containers.
In the STL? Not having my STL reference handy I cna't confirm this.
If so, it seems wierd to me, since the STL is all about containers
and, in general, classes which implement data structures.
--
*****[ Phil Hunt ***** ph...@comuno.freeserve.co.uk ]*****
Pstream class library for C++: a Parsing Stream library that
facilitates writing lexical analysers and other programs
that parse data files. Available on an open source license from
<http://www.vision25.demon.co.uk/oss/phlib/intro.html>
Carlos Moreno
Pete Becker wrote:
>
> On the other hand, those who think that providing two iterators is too
> large an imposition can easily write their own template to do it for
> them:
>
> template <class Container> void sort(Container c) { sort(c.begin(),
> c.end()); }
Hmmm, I doubt that would do it for them :-) (you forgot the pass-by-
reference)
> Since it's so simple, there's no need to add it to the standard library.
I don't think this is a reason not to include something in a standard
library -- 90% or more of the facilities are trivial to write: for_each,
copy, strcpy, strlen, transform, count, find, etc., and they're still
part of the Standard Library...
Carlos
--
James Dennett
>
> >See above. There are no algorithms which work on containers.
>
> In the STL? Not having my STL reference handy I cna't confirm this.
Well, it's somewhat "true by definition" if you don't consider
member functions such as std::list::sort to be STL algorithms.
Only the free function templates are generally considered to be
algorithms in the STL sense.
> If so, it seems wierd to me, since the STL is all about containers
> and, in general, classes which implement data structures.
Myth. The STL is about generic algorithms at least as much as it
is about generic containers, and iterators are the abstraction which
can be used to bind the algorithms to containers, but iterators are
a much more powerful concept that covers ranges which don't have to
exist inside of a container. I might print the numbers from 1 to 10
by using a range defined by two integer_iterators, if I chose to
define such a class. Or I could use a range of directory_iterators
to view the content of a directory inside a filesystem, or a
random_number_iterator to read an unbounded sequence of pseudo-
random numbers. I can extend the STL with new algorithms which
will work on any range, and as a bonus they will automatically
work on all of the pre-defined containers. I can extend the STL
with new containers, and the algorithms will work on those.
The STL is not just another container library. That's just the
easiest way to sell it to developers ;)
-- James Dennett
Dave Harris
> > It probably wouldn't be too difficult to add direct support for
> > containers. Everywhere an algorithm takes a pair of vectors, add an
> > overload which takes a container, instead of a pair of vectors, and
> > calls the existing algorithm with container.begin(), container.end().
>
> True, but that misses the point. STL algorithms operate on sequences.
The problem (in my view) is that sequences, despite being the
all-important things which the algorithms operate on, are not actually
reified anywhere. Instead we pass around pairs of iterators. It is left
implicit that two iterators make a sequence.
So I would suggest making that explicit with a nominal "sequence"
concept, something like:
template <typename iterator>
class sequence {
public:
sequence( iterator first, iterator last );
iterator begin() const;
iterator end() const;
};
with algorithms being specialised on that rather than on containers:
template <typename Sequence>
void sort( Sequence s ) {
sort( s.begin(), c.end() );
}
We then provide nominal functions like:
template <typename T>
sequence< vector<T>::iterator > get_all( vector<T> &v ) {
return sequence< vector<T>::iterator >( v.begin(), v.end() );
}
I say "nominal" because, of course, with this definition a container is
already a model of a sequence and we don't need a function to convert
them.
(Apologies if I am not using the words "model" and "concept" quite right.
I intend the STL meanings but can't find a reference on them.)
> Containers are one way of creating sequencres. Algorithms that operate
> directly on containers are foreign to STL as it is currently designed.
Agreed.
What I've written above may look mere like slight of hand, but it also
allows sequences to be constructed from an arbitrary pair of iterators,
or from a c-array.
char text[] = "Hello, world";
sequence<char *> s( text );
sort( s );
(This assumes a specialisation of sequence<char *> which adds a
one-argument constructor.)
> On the other hand, those who think that providing two iterators is too
> large an imposition can easily write their own template to do it for
> them:
>
> template <class Container> void sort(Container c) { sort(c.begin(),
> c.end()); }
>
> Since it's so simple, there's no need to add it to the standard
> library.
The library contains many things which are simple. I don't think "too
simple" is a good reason for rejecting something. The sequence concept is
important. Standardising it will help compatibility between code written
by different people.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."
Nick Thurn
>
> Pete Becker wrote:
>
> > Since it's so simple, there's no need to add it to the standard library.
>
> library -- 90% or more of the facilities are trivial to write: for_each,
> copy, strcpy, strlen, transform, count, find, etc., and they're still
> part of the Standard Library...
>
Totally agree. The point of the standard is to standardize normal boring
stuff (or at least that's what it should be!!)
cheers
Nick
John Potter
wrote:
> >See above. There are no algorithms which work on containers.
>
> In the STL? Not having my STL reference handy I cna't confirm this.
> If so, it seems wierd to me, since the STL is all about containers
> and, in general, classes which implement data structures.
Ah, that's the problem. The STL is all about algorithms which work
on ranges represented by iterators. The containers are a poorly
done patch which attempts to provide some ranges to the algorithms.
Most of us mortals do not understand that. We do understand containers
and find them useful. We mostly ignore the algorithms other than sort
and pretend that we are using the STL.
I think that the number of special member functions in the containers
other than array look alikes shows that they just do not fit. The
algorithms work on arrays and occasionally poorly on other containers.
Maybe someone with a better insight to the STL without containers can
post some enlightenment.
John
Pete Becker
>
> > Since it's so simple, there's no need to add it to the standard library.
>
> I don't think this is a reason not to include something in a standard
> library -- 90% or more of the facilities are trivial to write: for_each,
> copy, strcpy, strlen, transform, count, find, etc., and they're still
> part of the Standard Library...
>
So, do you think that this should be part of the standard library, and
if so, why?
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> Pete Becker wrote:
> >
>
> I don't think this is a reason not to include something in a standard
> library -- 90% or more of the facilities are trivial to write: for_each,
> copy, strcpy, strlen, transform, count, find, etc., and they're still
> part of the Standard Library...
>
The only reason I can think of for including something as anti-thematic
as algorithms that operate on containers would be that they would be
hard to write. Since that is clearly not the case, people who want to
this wart can provide it themselves.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> peteb...@acm.org (Pete Becker) wrote (abridged):
> > > It probably wouldn't be too difficult to add direct support for
> > > containers. Everywhere an algorithm takes a pair of vectors, add an
> > > overload which takes a container, instead of a pair of vectors, and
> > > calls the existing algorithm with container.begin(), container.end().
> >
> > True, but that misses the point. STL algorithms operate on sequences.
>
> The problem (in my view) is that sequences, despite being the
> all-important things which the algorithms operate on, are not actually
> reified anywhere. Instead we pass around pairs of iterators. It is left
> implicit that two iterators make a sequence.
Implicit in the code, perhaps, but explicit in the definitions of
algorithms.
>
> What I've written above may look mere like slight of hand, but it also
> allows sequences to be constructed from an arbitrary pair of iterators,
> or from a c-array.
>
> char text[] = "Hello, world";
> sequence<char *> s( text );
> sort( s );
What is the advantage of this over the current mechanism:
char text[] = "Hello, world";
sort(text, text + sizeof(text));
I don't see where there's an end to this, either. Currently I can write:
int main(int argc, char *argv[])
{
copy(argv, argv + argc, output_iterator<char *>(cout));
return 0;
}
So would you also add a specialization of sequence for arrays of
char*'s? And for whatever other type someone might want to use?
>
> (This assumes a specialisation of sequence<char *> which adds a
> one-argument constructor.)
>
> > On the other hand, those who think that providing two iterators is too
> > large an imposition can easily write their own template to do it for
> > them:
> >
> > template <class Container> void sort(Container c) { sort(c.begin(),
> > c.end()); }
> >
> > Since it's so simple, there's no need to add it to the standard
> > library.
>
> The library contains many things which are simple. I don't think "too
> simple" is a good reason for rejecting something. The sequence concept is
> important. Standardising it will help compatibility between code written
> by different people.
>
How will it help compatibility? Assuming, of course, that people use
namespaces sensibly...
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> Carlos Moreno wrote:
> >
> > Pete Becker wrote:
> >
> > > Since it's so simple, there's no need to add it to the standard library.
> >
> > I don't think this is a reason not to include something in a standard
> > library -- 90% or more of the facilities are trivial to write: for_each,
> > copy, strcpy, strlen, transform, count, find, etc., and they're still
> > part of the Standard Library...
> >
>
> Totally agree. The point of the standard is to standardize normal boring
> stuff (or at least that's what it should be!!)
>
Please don't propogate that out-of-context quote. The context was that
STL algorithms apply to sequences, not containers. Adding this wart
might be justified if it were hard for users to do. Since it's so
simple, that justification does not apply.
As I've said elsewhere, if you think this should be part of the
standard, give reasons. Just saying that my objection (even if
mischaracterized) isn't convincing doesn't mean that it should be added.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Carlos Moreno
Pete Becker wrote:
>
> Carlos Moreno wrote:
> >
> > > Since it's so simple, there's no need to add it to the standard library.
> >
> > I don't think this is a reason not to include something in a standard
> > library -- 90% or more of the facilities are trivial to write: for_each,
> > copy, strcpy, strlen, transform, count, find, etc., and they're still
> > part of the Standard Library...
> >
>
> So, do you think that this should be part of the standard library, and
> if so, why?
Well, I was just refusing the argument that because something is simple,
it shouldn't be part of the standard library -- but now that you twist
my arm to make me confess :-)
I do think that the idea of including this in the library would be very
nice and convenient. You keep hearing and reading about how code should
be readable above all else. You should design classes and code with
straightforwardness in mind, then, as a secondary concern, comes
efficiency and other features...
So, when I read something like:
sort (a.begin(), a.end())
I wonder... "What? We're sorting two things, or one? Are we sorting
the first thing with the second one being a "tagarray"? Is it or is it
not a what we want to sort????"
If I read:
sort (a);
it is immediately obvious that you're sorting... well, a, of course!!!
What else could you be sorting?
Also, there is much less possibility of screwing up coding a sort(a)
than a sort (begin, end). Examples:
sort (my_vector.begin(), my_vector2.end());
If you're unlucky enough to have another vector of the same type
named my_vector2, then you'll pay very expensive for that typo...
vector<int>::iterator beg = v.begin();
vector<int>::iterator end = v.end();
v.push_back (....);
end = v.end();
// Hey, I'm smart, and I know that I have to re-compute end!
// ^^^^^^^^^^^ NOT REALLY!!!!
sort (beg, end);
// BOOM!!! -- hey, I wasn't that smart after all... :-(
The examples are silly, but I'm sure that there may be more
reasonable situations where a moderately competent programmer
could make these mistakes...
Carlos
--
Dave Harris
> > all-important things which the algorithms operate on, are not
> > actually
> > reified anywhere. Instead we pass around pairs of iterators. It is
> > left
> > implicit that two iterators make a sequence.
>
> Implicit in the code, perhaps, but explicit in the definitions of
> algorithms.
Doesn't that mismatch bother you? If it is worth saying, it is worth
saying in code.
> > char text[] = "Hello, world";
> > sequence<char *> s( text );
> > sort( s );
>
> What is the advantage of this over the current mechanism:
>
> char text[] = "Hello, world";
> sort(text, text + sizeof(text));
Sizeof will give the wrong answer if text is a pointer rather than an
array. But really the point was to illustrate how sequences can be
defined in more general ways than the current STL admits.
Another advantage shows up more when passing these things around or
generally manipulating them. We only have half as many arguments to pass.
Eg forwarding functions:
void my_container::erase( const sequence<iterator> &s ) {
m_base_container.erase( s );
}
The improvement is small but real. Common idioms should be short and
lightweight so as not to distract.
> I don't see where there's an end to this, either.
Absolutely. By turning sequences into objects we provide a place to put
other useful code and specialisations. I would expect users to write
their own sequence classes with their own specialisations. Exactly which
we provide as standard is open to debate, of course. Array + length and
iterator + terminating value are two obvious ones.
> How will it help compatibility? Assuming, of course, that people use
> namespaces sensibly...
Namespaces merely allow incompatible sequences to coexist. They don't
necessarily allow them to interoperate. We should be able to pass a
sequence created by one vendor to an algorithm defined by another vendor.
There are several ways to define a sequence object. Eg should the methods
be begin/end or first/last? Should "sequence" have an initial capital?
One issue is whether we should use member functions. Eg:
template <typename iterator>
iterator begin( const sequence<iterator> &s );
versus:
template <typename iterator>
iterator sequence<iterator>::begin() const;
Another is whether we should provide other methods, like first() or
empty(). Perhaps even an increment that applies to begin(), allowing
methods like:
template <typename sequence, typename functor>
void for_each( sequence s, functor f ) {
while (!s.empty()) {
f( s.first() );
++s;
}
}
Some kinds of sequence would find this more convenient or efficient.
Maybe we should have a traits class so that algorithms could be
specialised differently for the different kinds of sequence.
Generally I find making important concepts explicit creates many
opportunities for improving code. Sequences seem like a fertile area. I
don't have a fully-worked out proposal, though.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Hendrik Schober
> Carlos Moreno wrote:
> >
> > > Since it's so simple, there's no need to add it to the standard
library.
> >
> > I don't think this is a reason not to include something in a standard
> > library -- 90% or more of the facilities are trivial to write: for_each,
> > copy, strcpy, strlen, transform, count, find, etc., and they're still
> > part of the Standard Library...
> >
>
> So, do you think that this should be part of the standard library, and
> if so, why?
What Carlos mentions above _is_ part of the standard
library.
Anyway there's one more reason _I_ would like to have
algorithms that take containers. Whenever I switch
from 'vetcor' to 'list' or the other way I have to go
through my code and find all calls to 'sort' and change
them. Why shouldn't my compiler take care of this.
> --
> Pete Becker
Schobi
--
Spam...@gmx.de is never read
I'm hschober at gmx dot de
P.S.: Ich suche einen Job in Berlin.
Pete Becker
>
> So, when I read something like:
>
> sort (a.begin(), a.end())
>
> I wonder... "What? We're sorting two things, or one? Are we sorting
> the first thing with the second one being a "tagarray"? Is it or is it
> not a what we want to sort????"
>
> If I read:
>
> sort (a);
>
> it is immediately obvious that you're sorting... well, a, of course!!!
> What else could you be sorting?
That's a beginner's problem: it only arises if you don't know how STL
works. C++ for the most part hasn't been tweaked for the convenience of
beginners, and shouldn't be.
>
> Also, there is much less possibility of screwing up coding a sort(a)
> than a sort (begin, end). Examples:
>
> sort (my_vector.begin(), my_vector2.end());
>
> If you're unlucky enough to have another vector of the same type
> named my_vector2, then you'll pay very expensive for that typo...
How often have you made this mistake? I don't recall ever doing it...
>
> vector<int>::iterator beg = v.begin();
> vector<int>::iterator end = v.end();
Non-idiomatic. Pass iterators to algorithms. Creating named iterators is
usually a sign of trouble.
>
> v.push_back (....);
>
> end = v.end();
> // Hey, I'm smart, and I know that I have to re-compute end!
> // ^^^^^^^^^^^ NOT REALLY!!!!
>
> sort (beg, end);
> // BOOM!!! -- hey, I wasn't that smart after all... :-(
>
> The examples are silly, but I'm sure that there may be more
> reasonable situations where a moderately competent programmer
> could make these mistakes...
>
Yes, it's possible to make mistakes. For folks who are worried about
their ability to use STL correctly, the fix is simple: write a template
that takes a container and passes its iterators to the real algorithm.
Why clutter every implementation with something that's so simple and so
non-idiomatic?
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> peteb...@acm.org (Pete Becker) wrote (abridged):
> > > The problem (in my view) is that sequences, despite being the
> > > all-important things which the algorithms operate on, are not
> > > actually
> > > reified anywhere. Instead we pass around pairs of iterators. It is
> > > left
> > > implicit that two iterators make a sequence.
> >
> > Implicit in the code, perhaps, but explicit in the definitions of
> > algorithms.
>
> Doesn't that mismatch bother you? If it is worth saying, it is worth
> saying in code.
I think that's a bit too long a stretch for that slogan. There are lots
of constraints that don't appear in code.
>
> > > char text[] = "Hello, world";
> > > sequence<char *> s( text );
> > > sort( s );
> >
> > What is the advantage of this over the current mechanism:
> >
> > char text[] = "Hello, world";
> > sort(text, text + sizeof(text));
>
> Sizeof will give the wrong answer if text is a pointer rather than an
> array.
But it's not a pointer, it's an array. Just like your example. And
that's appropriate for an STL algorithm: there are none that operate on
single pointers. They operate on sequences, and an array is one way of
creating a sequence.
However, if you insist on a version that works with a null terminated
character sequence, here it is:
sort(text, text + strlen(text));
> But really the point was to illustrate how sequences can be
> defined in more general ways than the current STL admits.
I don't see it. How is sequence<char*> more general than two char*'s?
>
> Another advantage shows up more when passing these things around or
> generally manipulating them. We only have half as many arguments to pass.
> Eg forwarding functions:
>
> void my_container::erase( const sequence<iterator> &s ) {
> m_base_container.erase( s );
> }
>
> The improvement is small but real. Common idioms should be short and
> lightweight so as not to distract.
Here's the code as it would be written now:
void my_container::erase( iterator begin, iterator end ) {
m_base_container.erase( begin, end);
}
I just don't see the benefit that comes from making it more complex,
with both iterator and sequence involved in the argument type.
>
> > I don't see where there's an end to this, either.
>
> Absolutely. By turning sequences into objects we provide a place to put
> other useful code and specialisations. I would expect users to write
> their own sequence classes with their own specialisations. Exactly which
> we provide as standard is open to debate, of course. Array + length and
> iterator + terminating value are two obvious ones.
>
> > How will it help compatibility? Assuming, of course, that people use
> > namespaces sensibly...
>
> Namespaces merely allow incompatible sequences to coexist.
That wasn't what I was getting at. They allow users to write their own
versions of algorithms that take whatever arguments they like, and
forward to the ones in the standard library.
>
> Generally I find making important concepts explicit creates many
> opportunities for improving code. Sequences seem like a fertile area. I
> don't have a fully-worked out proposal, though.
>
Well, you've got plenty of time to experiment, work out the bugs, and
propose it. Still, it just looks to me like clutter.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> "Pete Becker" <peteb...@acm.org> wrote:
> > Carlos Moreno wrote:
> > >
> > > > Since it's so simple, there's no need to add it to the standard
> library.
> > >
> > > I don't think this is a reason not to include something in a standard
> > > library -- 90% or more of the facilities are trivial to write: for_each,
> > > copy, strcpy, strlen, transform, count, find, etc., and they're still
> > > part of the Standard Library...
> > >
> >
> > So, do you think that this should be part of the standard library, and
> > if so, why?
>
> What Carlos mentions above _is_ part of the standard
> library.
No, "this" referred to the subject under discussion, namely, algorithms
that take containers. But you understood that, didn't you? That's why
you said:
> Anyway there's one more reason _I_ would like to have
> algorithms that take containers. Whenever I switch
> from 'vetcor' to 'list' or the other way I have to go
> through my code and find all calls to 'sort' and change
> them. Why shouldn't my compiler take care of this.
>
That's a legitimate issue, but there are solutions that don't violate
the design of the STL. Since list has a sort member function, adding one
to the other containers would "fix" this. That doesn't screw up the
algorithms, but puts knowledge of containers where it belongs: in the
containers themselves.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
John Potter
wrote:
> Anyway there's one more reason _I_ would like to have
> algorithms that take containers. Whenever I switch
> from 'vetcor' to 'list' or the other way I have to go
> through my code and find all calls to 'sort' and change
> them. Why shouldn't my compiler take care of this.
You may have hit the real problem. The STL is an experiment which
seems to be failing. I think we have a clear cut case of premature
optimization.
It has been admitted that there was no real reason to require
random access iterators for sort. There are good sorting algorithms
which work with forward iterators. That leaves random shufle and
the heap operations. There are also a few algorithms which require
bidirectional iterators. Given the current containers, they are not
a problem.
It would be a shame to throw out the entire idea just because of a
decision that everyone would rather have a faster sort member of
list than a slower general algorithm _always_. That may be true in
the end, but not during developement.
John
Dave Harris
> The problem (in my view) is that sequences, despite being the
> all-important things which the algorithms operate on, are not actually
> reified anywhere. Instead we pass around pairs of iterators. It is
> left implicit that two iterators make a sequence.
I have posted this thought as a suggestion for the forthcoming C++
standard, in the "C++0x" thread started by Francis Glassborow in
comp.std.c++.
Dave Harris
> > defined in more general ways than the current STL admits.
>
> I don't see it. How is sequence<char*> more general than two char*'s?
For example, a sequence can be terminated by a special value instead of
by an end-marker. This is more appropriate when dealing with null
terminated strings or arrays (such as argv), or streams terminated by
EOF, or lines terminated by '\n', or fields terminated by '\t', or
whatever.
A sequence can also be demarcated by a start position and a length. This
will be more convenient if we happen to know how many items we want, but
we don't have random access or absolute positioning.
Some sequences are infinitely long, and have no meaningful end position.
> > void my_container::erase( const sequence<iterator> &s ) {
> > m_base_container.erase( s );
> > }
>
> Here's the code as it would be written now:
>
> void my_container::erase( iterator begin, iterator end ) {
> m_base_container.erase( begin, end);
> }
>
> I just don't see the benefit that comes from making it more complex,
> with both iterator and sequence involved in the argument type.
Well, in practice these would all be typedefs. So it would be:
void my_container::erase( const sequence &s ) {
m_base_container.erase( s );
}
So there is only one type in the argument list. One type and one
argument. This is simpler. There is less scope for mistakes, eg writing
it as:
void my_container::erase( iterator begin, iterator end ) {
m_base_container.erase( end, begin );
}
or some such. Using two arguments goes against the "once and only once"
guideline. There is a lot of implicit information that is replicated
everywhere they are used.
> Well, you've got plenty of time to experiment, work out the bugs, and
> propose it. Still, it just looks to me like clutter.
There is a brainstorming session on possible directions for the next C++
standard over in comp.std.c++, so I have mentioned it there now.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Matt Seitz
"Pete Becker" <peteb...@acm.org> wrote in message
news:3AFA94C9...@acm.org...
> Carlos Moreno wrote:
> >
> > So, when I read something like:
> >
> > sort (a.begin(), a.end())
> >
> > I wonder... "What? We're sorting two things, or one? Are we sorting
> > the first thing with the second one being a "tagarray"? Is it or is it
> > not a what we want to sort????"
> >
> > If I read:
> >
> > sort (a);
> >
> > it is immediately obvious that you're sorting... well, a, of course!!!
> > What else could you be sorting?
>
> That's a beginner's problem: it only arises if you don't know how STL
> works. C++ for the most part hasn't been tweaked for the convenience of
> beginners, and shouldn't be.
> Yes, it's possible to make mistakes. For folks who are worried about
> their ability to use STL correctly, the fix is simple: write a template
> that takes a container and passes its iterators to the real algorithm.
> Why clutter every implementation with something that's so simple and so
> non-idiomatic?
I look at this the other way around: why force every programmer to have to
either
a) type the long-winded "container.begin(), container.end()" form over and
over again
b) keep reinventing the wheel by creating their own set of container based
algorithms
Including a standard set of container algorithms, whether defined as
stand-alone functions or as member functions, would save programmers time
and effort.
Nicola Musatti
James Kanze wrote:
>
> Dietmar Kuehl wrote:
>
> > In addition, any library implementer faces an essential problem:
> > [S]He does not know how the library is used in the
> > application. Thus, I think that everything should be implemented to
> > performance with as low overhead as possible because everything
> > might be used in a performance critical path in an application.
>
> In an ideal world, the library would be 100% optimized, with no
> errors. As we all know, however, this requires an infinite amount of
> work and testing, and most implementers don't have infinite resources.
> I know of no library that is 100% correct, and I know of none in which
> there aren't places where performance could be improved.
This is not possible even in theory: optimization requires a usage model
which is subjective by definition.
Best regards,
Nicola Musatti
John Potter
> Hendrik Schober wrote:
> > Anyway there's one more reason _I_ would like to have
> > algorithms that take containers. Whenever I switch
> > from 'vetcor' to 'list' or the other way I have to go
> > through my code and find all calls to 'sort' and change
> > them. Why shouldn't my compiler take care of this.
> >
>
> That's a legitimate issue, but there are solutions that don't violate
> the design of the STL. Since list has a sort member function, adding one
> to the other containers would "fix" this. That doesn't screw up the
> algorithms, but puts knowledge of containers where it belongs: in the
> containers themselves.
That totally screws up the STL. You have just stated that the whole
idea behind it is wrong. There should be no algorithms, the containers
should do things to themselves.
List also has remove and remove_if which erase (can't even get the
name right :). Unique, merge, and reverse. Let's add these to the
other containers also.
BTW, how are you going to add them to array? That's where it all
started, the other containers are just conveniences.
The STL idea was to be able to apply the same algorithms to an array
and a linked list. It is beautiful. It has failed in the name of
efficiency.
John
Dietmar Kuehl
James Kanze (James...@dresdner-bank.com) wrote:
: > It is interesting to note that "compile time" is also a performance
: > issue, one which most implementations do not optimize for.
: Good point, which I tend to forget. For people in research, it isn't
: unusual to compile a program 4 or 5 times, then just run it once.
It isn't just research: The compile times in the projects I have worked
on amount to a significant portion of the overall costs! During coding
and debugging, there tend to be many compiles. Although it isn't as
extreme as in some "sientific" cases (some of this stuff are
optimizations applied to real world problems) where the program is run
only once. But then, how often a debug version of a program is run?
Until the next error is found which is often also just once...
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
Carlos Moreno
John Potter wrote:
>
> The STL idea was to be able to apply the same algorithms to an array
> and a linked list. It is beautiful. It has failed in the name of
> efficiency.
Yes, but if you try to sort a linked-list with vector-like idioms,
then you wouldn't have a linked-list (that is, you would have a
structure that does not exhibit the typical characteristics of a
linked-list).
What I wonder is why they had to sacrifice the beauty of the STL
concept in the name of efficiency:
template <typename T>
void sort (list<T>::iterator begin, list<T>::iterator end)
{
// use an algorithm optimized for lists
}
template <typename T, typename Cmp>
void sort (list<T>::iterator begin, list<T>::iterator end, Cmp cmp)
{
// same
}
Instead of providing sort as member functions of list<>. Am I
missing something here? Yes, I know, this might have to be
overloaded for several types of iterators, maybe... Well, so
be it... The idea is to keep a concept that is beautiful; we
make compiler vendors work slightly harder in exchange for
consistency and beauty in the final product.
That, or... We provide algorithms that receive containers ;-)
Carlos
--
Pete Becker
>
> I look at this the other way around: why force every programmer to have to
> either
> a) type the long-winded "container.begin(), container.end()" form over and
> over again
> b) keep reinventing the wheel by creating their own set of container based
> algorithms
>
Because algorithms operate on sequences, not on containers.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> peteb...@acm.org (Pete Becker) wrote (abridged):
> > > But really the point was to illustrate how sequences can be
> > > defined in more general ways than the current STL admits.
> >
> > I don't see it. How is sequence<char*> more general than two char*'s?
>
> For example, a sequence can be terminated by a special value instead of
> by an end-marker. This is more appropriate when dealing with null
> terminated strings or arrays (such as argv), or streams terminated by
> EOF, or lines terminated by '\n', or fields terminated by '\t', or
> whatever.
But how do you write an algorithm to recognize this special value?
>
> A sequence can also be demarcated by a start position and a length. This
> will be more convenient if we happen to know how many items we want, but
> we don't have random access or absolute positioning.
Does that mean that there would be two sets of algorithms?
> So there is only one type in the argument list. One type and one
> argument. This is simpler. There is less scope for mistakes, eg writing
> it as:
>
> void my_container::erase( iterator begin, iterator end ) {
> m_base_container.erase( end, begin );
> }
How common is this "mistake"? Do we really need to protect programmers
from it?
>
> or some such. Using two arguments goes against the "once and only once"
> guideline. There is a lot of implicit information that is replicated
> everywhere they are used.
Huh? Whatever you do, you need to know where a sequence starts and where
it ends. Blobbing those two things together into a single struct doesn't
change that.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dietmar Kuehl
Carlos Moreno (mor...@mochima.com) wrote:
: What I wonder is why they had to sacrifice the beauty of the STL
: concept in the name of efficiency:
: template <typename T>
: void sort (list<T>::iterator begin, list<T>::iterator end)
: {
: // use an algorithm optimized for lists
: }
: template <typename T, typename Cmp>
: void sort (list<T>::iterator begin, list<T>::iterator end, Cmp cmp)
: {
: // same
: }
Maybe they didn't provide these overloads because you cannot specialize
on nested types... Also, lists are not the only containers which would
need a special sorting algorithm: Basically, the Quicksort variation
used in 'std::sort()' only works with random access iterators. Thus,
the correct change would be provision of a sort function operating on
bidirectional or even forward iterators, too.
There is another issue for the list stuff: Probably the sorting
algorithm for lists does not swap elements but rather just adjusts
pointers. In this case it is necssary to adjust the head point at some
time which in turn needs the list element (well, not really but
dictating that it is not supposed to need the list elements somewhat
restricts implementations).
: The idea is to keep a concept that is beautiful; we
: make compiler vendors work slightly harder in exchange for
: consistency and beauty in the final product.
"Working slightly harder" to achieve something impossible? Well, I
think it takes more than just a little work...
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dennis Yelle
>
> John Potter wrote:
> >
> > The STL idea was to be able to apply the same algorithms to an array
> > and a linked list. It is beautiful. It has failed in the name of
> > efficiency.
>
> Yes, but if you try to sort a linked-list with vector-like idioms,
> then you wouldn't have a linked-list (that is, you would have a
> structure that does not exhibit the typical characteristics of a
> linked-list).
>
> What I wonder is why they had to sacrifice the beauty of the STL
> concept in the name of efficiency:
>
> template <typename T>
> void sort (list<T>::iterator begin, list<T>::iterator end)
> {
> // use an algorithm optimized for lists
> }
>
> template <typename T, typename Cmp>
> void sort (list<T>::iterator begin, list<T>::iterator end, Cmp cmp)
> {
> // same
> }
>
> Instead of providing sort as member functions of list<>. Am I
> missing something here?
Well, it is a bit more complicated that it appears at first glance:
1. The obvious way to implement the functions above is to
first use splice to grab the range to be sorted.
2. splice is a member function of list, you cannot call
splice unless you have a container, or pointer, or reference
to a container.
3. Given two iterators into a list, there is no way to get the
list container itself.
4. slist (the singly linked list) is (slightly) worse.
5. sort is supposed to work with only O(1) additional space,
so a version which first copies the range cannot
be the only version offered.
These problems are all solvable by the library implementer,
but not by the library user, and they seem to require thinking
slightly "outside the box".
Also, a lot of things that could have been in the standard library
were left out. I think it is time to put this one in.
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/
John Potter
> What I wonder is why they had to sacrifice the beauty of the STL
> concept in the name of efficiency:
>
> template <typename T>
> void sort (list<T>::iterator begin, list<T>::iterator end)
> {
> // use an algorithm optimized for lists
> }
That's not the general form.
template <typename Biter>
void sort (Biter first, Biter last, bidirectional_iterator_tag) {
// use an algorithm optimized for bidirectional iterators
}
Likewise for forward iterator, the comp versions and the usual compile
time dispatch.
> Instead of providing sort as member functions of list<>. Am I
> missing something here? Yes, I know, this might have to be
> overloaded for several types of iterators, maybe... Well, so
> be it...
Done, finished, several <= 4.
There is a price to pay for generality. It will always be faster to
implement the algorithm as a member; however, these versions can be
reasonable for developement. If the final version shows that there
is a bottleneck in the sorting and the list has been decided, a shift
to the member is appropriate at that time.
The question is whether users want the generality or would rather
change their code when they change containers. Maybe good designers
never change the container.
I have done a quick implementation and there is considerable difference
between these times and the member times. Still at worst Nlog^2(N).
John
Dave Harris
> > of by an end-marker. This is more appropriate when dealing with null
> > terminated strings or arrays (such as argv), or streams terminated by
> > EOF, or lines terminated by '\n', or fields terminated by '\t', or
> > whatever.
>
> But how do you write an algorithm to recognize this special value?
The algorithm wouldn't. The sequence would.
The following is untested code. Apologies for the length, but it seems
necessary to spell out the idea in a bit more detail. Suppose our
abstract sequence concept looks like:
class sequence {
public:
iterator first() const;
iterator last() const;
bool empty() const;
sequence &operator++();
};
And suppose we have two concrete models. The first is the usual
2-iterator template:
template <typename iterator>
class iterator_sequence {
public:
iterator_sequence( iterator first, iterator last ) :
m_first(first), m_last(last) {}
iterator first() const {
return m_first;
}
iterator last() const {
return m_last;
}
bool empty() const {
return m_first != m_last;
}
iterator_sequence<iterator> &operator++() {
++first;
return *this;
}
private:
iterator m_first, m_last;
};
The second uses a terminating sentinel value.
template <typename iterator,
iterator_traits<iterator>::value_type sentinel=0>
class sentinel_sequence {
public:
sentinel_sequence( iterator next ) :
m_next(next) {}
iterator first() const {
return m_next;
}
iterator last() const {
iterator i = m_next;
while (*i != sentinel)
++i;
return i;
}
bool empty() const {
return *m_next == sentinel;
}
sentinel_sequence<iterator,sentinal> &operator++() {
++m_next;
return *this;
}
private:
iterator m_next;
};
Here our last() function is inefficient; it is O(N). On the other hand,
we only need to store 1 iterator so we have less data to pass around.
A typical forward-iterator algorithm, translated to sequences, would look
like:
template <typename sequence, typename fun>
fun for_each( sequence s, fun f ) {
for ( ; !s.empty(); ++s)
f( *s.begin() );
return f;
}
Now, if we use an iterator_sequence, for example:
void demo1( char *text ) {
iterator_sequence<char *> s( text, text+strlen(text) );
for_each( s, f );
}
a good optimiser should produce code identical to:
fun for_each( iterator first, iterator last, fun f ) {
for ( ; first != last; ++first)
f( *first );
return f;
}
If instead we use a sentinel_sequence:
void demo2( char *text ) {
sentinel_sequence<char *> s( text );
for_each( s, f );
}
a good optimiser will produce code identical to:
fun for_each( char *str, fun f ) {
for ( ; *str; ++str)
f( *str );
return f;
}
Points to notice:
(1) We only have to write the algorithm once, not once per model.
(2) The algorithm doesn't need to know about special sentinel values.
(3) The code for the iterator_sequence is as good as what the current STL
would produce.
(4) The code for the sentinel_sequence is more efficient than the current
STL because it does not need to compute strlen() - it only makes one pass
over the string.
I have used first/last instead of begin/end, because we are now passing
sequences by value so it is inappropriate for a container to be a model
of a sequence. We wouldn't want to copy an entire vector. We can easily
have a template like:
template <typename container>
iterator_sequence all( container &c ) {
return iterator_sequence<container::iterator>(
c.begin(), c.end() );
}
which would be used like:
void demo3( vector<int> &v ) {
for_each( all(v), f );
}
> Does that mean that there would be two sets of algorithms?
Hopefully not. The aim of the sequence concept is to insulate the
algorithm from details of how the sequence is implemented. The for_each
example above shows it is possible to do this, without loss of
efficiency, in at least some cases.
That said, some algorithms might benefit from being specialised for
particular kinds of sequence. This is similar to the way algorithms such
as distance<> are specialised for random-access iterators. We probably
need a sequence_traits template similar to iterator_traits, with a
sequence_category to deal with issues such as whether an O(1) last() is
available.
> How common is this "mistake"? Do we really need to protect programmers
> from it?
Well, put it this way: when I am reading source code looking for bugs,
these are among the things I habitually check for. I would be happier if
this kind of mistake was impossible. I often write validation code such
as:
void remove( iterator first, iterator last ) {
assert( first <= last );
//...
}
to defend against it.
By the way, have you read Stroustrup's C++PL? In the 3rd edition, section
18.3.1, he touches on this topic. He writes:
Writing x.begin(), x.end() to express "all the elements of x" is
common, tedious, and can even be error-prone. For example, when
several iterators are used, it is too easy to provide an algorithm
with a pair of arguments that does not constitute a sequence:
and he gives examples. He then develops a template broadly similar to
iterator_sequence above. I don't mean to argue from authority, but I had
thought I was being rather unoriginal and conventional here. I am
surprised to be meeting such resistance.
> > Using two arguments goes against the "once and only once"
> > guideline. There is a lot of implicit information that is replicated
> > everywhere they are used.
>
> Huh? Whatever you do, you need to know where a sequence starts and
> where it ends. Blobbing those two things together into a single struct
> doesn't change that.
Well, the "where it ends" part can sometimes be computed lazily, but
that's not what I meant. The replicated information is stuff like: this
iterator points into the same sequence as that one; this iterator is <=
that one; if these two iterators are equal, the sequence is empty.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dennis Yelle
[...]
> class sequence {
> public:
> iterator first() const;
> iterator last() const;
> bool empty() const;
> sequence &operator++();
> };
What should find() return in your model?
Should it just return a single iterator?
Or should it return a sequence?
Or a pair of sequences?
And if find() returns an iterator, and then
I want to call find() again, am I supposed to
build a new sequence to pass to find()?
Do you propose to get rid of all the algorithms
that take a range specified by 2 iterators?
Or do you just propose to add a bunch of
new algorithms that take a sequence?
[...]
> I don't mean to argue from authority, but I had
> thought I was being rather unoriginal and conventional here. I am
> surprised to be meeting such resistance.
Some of the resistance is just,
"I spent a lot of time and energy learning the
way things work. Don't go changing everything now."
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/
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Dietmar Kuehl
John Potter (jpo...@falcon.lhup.edu) wrote:
: On 12 May 2001 04:23:04 -0400, Carlos Moreno <mor...@mochima.com> wrote:
: template <typename Biter>
: void sort (Biter first, Biter last, bidirectional_iterator_tag) {
: // use an algorithm optimized for bidirectional iterators
: }
: Likewise for forward iterator, the comp versions and the usual compile
: time dispatch.
You are probably refering to a 'sort()' implementation like this:
template <typename It> void sort(It beg, It end) {
sort(beg, end, typename std::iterator_traits<It>::category());
}
That is, the 'sort()' function internally determines the best algorithm
to the given iterator traits. As I mentioned in an article in
comp.std.c++ I would probably use a different name for a method
selecting the best algorithm to make clear that the runtime
characteristics of the function can differ widely between different
containers.
BTW, we should really rename "algorithm" to "solver" or something like
this: The "algorithms" in the standard aren't algorithms. They are
functions solving a particular problem in an unspecified way. An
algorithm is a specific approach to solve a certain problem. Functions
like 'quick_sort()', 'merge_sort()', 'heap_sort()', ... would be
implementations of specific algorithms. 'sort()', implemented in terms
of one of those, just solves the problem of sorting a sequence. And
'best_sort()', to stick with the name I have used in comp.std.c++,
would use the best algorithm applicable to a given sequence.
: There is a price to pay for generality. It will always be faster to
: implement the algorithm as a member;
With "faster" you mean the member will never be slower? This is obvious
as the member can, if necessary, delegate processing to the non-member
function :-)
I see, however, no restriction why the non-member function has to be
slower! My understanding is that the member function can gain
performance from the fact that it can adjust pointers rather than
swapping elements. In particular, I can envision an implementation
merge sorting the elements and adjusting only the forward pointer
during the sort and then fixing up the backward pointers once the sort
is complete. That is, rather than swaping elements over and over, only
a few pointers are adjusted.
The tricky thing about this is setting the pointer in the list object
to point to the first element after the sort. But then, this isn't as
bad as it sounds: A typical list implementation will probably be
something like cyclic list with a special node hold by the list object
which does not contain a data record but only the forward and backward
pointers pointing to the first and the last element of the list. This
way there is no need for special treatment of the start and the end of
the list. As a side effect, a pointer adjusting sorting algorithm can
be implemented. Of course, this would need suitable concepts currently
not defined in the standard C++ library. The implementation can use
private concepts for the implementation of 'std::list' but this would
exclude the users from taking advantage of this optimization forcing
the use of 'std::iter_swap()' for other containers.
: I have done a quick implementation and there is considerable difference
: between these times and the member times. Still at worst Nlog^2(N).
I guess you have used 'swap()' to exchange the value...
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Nick Thurn
>
> Some of the resistance is just,
> "I spent a lot of time and energy learning the
> way things work. Don't go changing everything now."
>
a std algorithm and execute it for the sequence represented
by a container? Say something like:
template <class T...>
class somecontainer
{
public:
template <class U>
typename function_traits<U>::return_type
function()
{
return U(begin(),end());
}
template <class U,class P>
typename function_traits<U>::return_type
function(P& param)
{
return U(begin(),end(),param);
}
//...
};
that gets called something like:
container.function<sort>();
container.function<for_each>(MyOperation());
Be nice now ;-). My point is: it may not be necessary to
provide a complete set of algorithm adaptors to accept
containers. Just provide each container with the appropriate
adaptor to accept any (appropriate) algorithm.
Note I don't *literally* mean the code above. I'm sure
others can think of better ways (like ones that actually work!!)
and better or more appropriate names.
cheers
Nick nick....@db.com
Ariel Scolnicov
> Dennis Yelle wrote:
> >
> > Some of the resistance is just,
> > "I spent a lot of time and energy learning the
> > way things work. Don't go changing everything now."
> >
> Can anyone think of a template member that would take
> a std algorithm and execute it for the sequence represented
> by a container? Say something like:
[...]
> that gets called something like:
>
> container.function<sort>();
> container.function<for_each>(MyOperation());
Better, perhaps:
template<class C>
void ezsort(C& c)
{
std::sort(c.begin(), c.end());
}
which you use like so:
std::vector<int> v;
// now fill v with a zillion ints
ezsort(v);
> Be nice now ;-). My point is: it may not be necessary to
> provide a complete set of algorithm adaptors to accept
> containers. Just provide each container with the appropriate
> adaptor to accept any (appropriate) algorithm.
I'm not sure if it's possible to write `ez' so that `ez<std::sort>(v)'
will do what you like, though.
[...]
--
Ariel Scolnicov |"GCAAGAATTGAACTGTAG" | ari...@compugen.co.il
Compugen Ltd. |Tel: +972-2-5713025 (Jerusalem) \ We recycle all our Hz
72 Pinhas Rosen St. |Tel: +972-3-7658117 (Main office)`---------------------
Tel-Aviv 69512, ISRAEL |Fax: +972-3-7658555 http://3w.compugen.co.il/~ariels
Pete Becker
>
> Points to notice:
> (1) We only have to write the algorithm once, not once per model.
> (2) The algorithm doesn't need to know about special sentinel values.
> (3) The code for the iterator_sequence is as good as what the current STL
> would produce.
> (4) The code for the sentinel_sequence is more efficient than the current
> STL because it does not need to compute strlen() - it only makes one pass
> over the string.
I see now what you're after. It's a drastic change from the current
principles underlying STL, and, as I've said before, I don't see any
overall benefit. Some things become simpler, some become harder. In
particular, though, where STL has a single way of communicating with
algorithms (start here, stop here), adding this layer of indirection
results in several different ways (start here, stop at delimiter; start
here, stop after n items; start at the beginning of this container, stop
at the end). I don't trust code that's supposed to figure out what I
meant. <g>
>
> By the way, have you read Stroustrup's C++PL? In the 3rd edition, section
> 18.3.1, he touches on this topic. He writes:
>
> Writing x.begin(), x.end() to express "all the elements of x" is
> common, tedious, and can even be error-prone. For example, when
> several iterators are used, it is too easy to provide an algorithm
> with a pair of arguments that does not constitute a sequence:
>
> and he gives examples. He then develops a template broadly similar to
> iterator_sequence above. I don't mean to argue from authority, but I had
> thought I was being rather unoriginal and conventional here. I am
> surprised to be meeting such resistance.
There's a difference between "it's useful" and "it should be part of the
standard library."
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
André Pönitz
> What is the advantage of this over the current mechanism:
>
> char text[] = "Hello, world";
> sort(text, text + sizeof(text));
Since everybody seems to re-iterate old arguments:
You have to type "text" (at least) twice.
"Not a big thing" you say.
So what if "text" is not a static char[] but the result of some longish
computation?
"Make an explicit temporary" you say.
Of what type? typeof() is not part of the language, is it?
Even if so, why should the principle of "Only pay for a feature if you need
it" be abonded?
I "need" algorithms (like counting/copying/...), I have "sequences"
(usually certain elements of a graph), but "pairs of single iterators"
simply are not appropriate description of a "sequence" in this case
(mostly because such a pair is fatter than a single "compound" iterator
holding both the start and end of the sequence).
Having an intermediate explicit concept of a "sequence" would allow a much
clearer mapping of "real world concepts" to code.
Andre'
PS: Yes I know I can add such "warts" to my own code at will. Don't pull
this argument again.
PPS: Nobody needs 'for' either. 'while' is fine, isn't it? ... well. 'if'
and 'goto' would do as well...
--
André Pönitz ............................................. poe...@htwm.de
Dave Harris
> What should find() return in your model?
Good question. It also applies to erase() and many other functions (some
container members rather than pure algorithms) that currently return
iterators.
> Should it just return a single iterator?
Yes.
> Or should it return a sequence?
Which sequence? Presumably [r, last) where 'r' is the result of the
current find(). However, what if we want [begin, r)? Although that is
probably rarer, I don't think find() should really be guessing what we
want.
Also, using a sequence where a single iterator is needed would sometimes
be less efficient. I'd prefer to avoid needless inefficiency in common
idioms.
> Or a pair of sequences?
Presumably both [first, r) and [r, last) ? That would be rather
redundant. The caller doesn't need to be told first and last, and doesn't
need to be told r twice.
In efficiency terms, if a sequence is a pair of iterators, we would be
returning 4 of them where 1 is needed. It seems like a massive cost for
no benefit.
> And if find() returns an iterator, and then
> I want to call find() again, am I supposed to
> build a new sequence to pass to find()?
Yes. If you want to keep your code fully generic.
Since this is not getting rid of iterators completely, we will need
facilities to make sequences and iterators work well together. For
example, a way to make a new sequence from an iterator into an old one,
and an at_end() test to avoid computing last() unnecessarily.
For example, consider the function currently written as:
// True if a comes before b in the given sequence.
bool comesBefore( iterator first, iterator last,
const value &a, const value &b ) {
iterator ia = find( first, last, a );
iterator ib = find( ia, last, b );
return ib != last;
}
We could use a mixture of sequences and iterators:
// True if a comes before b in the given sequence.
bool comesBefore( sequence s, const value &a, const value &b ) {
sequence::iterator ia = find( s, a );
sequence::iterator ib = find( ia, s.last(), b );
return ib != s.last();
}
and this should work. However, consider instead constructing the
subsequence after 'a' explicitly:
// True if a comes before b in the given sequence.
bool comesBefore( sequence s, const value &a, const value &b ) {
sequence::iterator ia = find( s, a );
sequence::iterator ib = find( sequence( s, ia ), b );
return !s.at_end( ib );
}
In my view, this is clearer than either of the above. It is also more
generic, in that it supports the more general sequences without losing
efficiency.
> Do you propose to get rid of all the algorithms
> that take a range specified by 2 iterators?
> Or do you just propose to add a bunch of
> new algorithms that take a sequence?
I don't think it is feasible to remove the current algorithms, if only
for reasons of backwards compatibility. However, I do think sequences are
the better abstraction. I would be tempted to mechanically rewrite the
existing 2-iterator algorithms to have them forward to the sequence
versions, eg:
template <typename iterator, typename value )
iterator find( iterator first, iterator last, const value &value ) {
return find( iterator_sequence( first, last ), value );
}
so the core algorithms are only expressed once.
I would probably not teach the old algorithms, except as a footnote. The
library would be simpler without them.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Matt Seitz
> Matt Seitz wrote:
> >
> > I look at this the other way around: why force every programmer to have
to
> > either
> > a) type the long-winded "container.begin(), container.end()" form over
and
> > over again
> > b) keep reinventing the wheel by creating their own set of container
based
> > algorithms
> >
>
> Because algorithms operate on sequences, not on containers.
So what? If there is an obvious mapping of a container to a sequence, why
not allow the library to handle this conversion, rather than forcing
programmers to do it by hand? Why insist on making life harder on
programmers?
Allowing a programmer to express an operation in the terms they use to think
of the problem makes it easier to both read and write code. Programmers
often think in terms of applying algorithms to containers ("I want to sort
this list."). Allowing them to express that concept directly in code makes
the code easier to write and read.
John Potter
> denn...@jps.net (Dennis Yelle) wrote (abridged):
> > What should find() return in your model?
>
> Good question. It also applies to erase() and many other functions (some
> container members rather than pure algorithms) that currently return
> iterators.
>
> > Should it just return a single iterator?
>
> Yes.
>
> > Or should it return a sequence?
>
> Which sequence? Presumably [r, last) where 'r' is the result of the
> current find(). However, what if we want [begin, r)? Although that is
> probably rarer, I don't think find() should really be guessing what we
> want.
The obvious sequence is [r, r + 1) if found or [last, last) when not
found. You do allow empty sequences don't you? But, that seems to be
a problem when last is a condition not an iterator. Then neither of
them is valid.
> Also, using a sequence where a single iterator is needed would sometimes
> be less efficient. I'd prefer to avoid needless inefficiency in common
> idioms.
I've been following this with interest. It now appears that a sequence
is nothing more than another abstraction to confuse the issues.
Premature optimization is ...
What does equal_range return? A pair of iterators or a sequence?
John
Pete Becker
>
> Allowing a programmer to express an operation in the terms they use to think
> of the problem makes it easier to both read and write code. Programmers
> often think in terms of applying algorithms to containers ("I want to sort
> this list."). Allowing them to express that concept directly in code makes
> the code easier to write and read.
>
I never sort a list. I sort the contents of a list. In STL terms, that
means that I sort the sequence of values contained in the list.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> Allowing a programmer to express an operation in the terms they use to think
> of the problem makes it easier to both read and write code. Programmers
> often think in terms of applying algorithms to containers ("I want to sort
> this list."). Allowing them to express that concept directly in code makes
> the code easier to write and read.
>
In other words, we should redesign STL to make it look like what
programmers who don't understand it think it is. <g>
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Matt Seitz
> Matt Seitz wrote:
> >
> > Allowing a programmer to express an operation in the terms they use to
think
> > of the problem makes it easier to both read and write code. Programmers
> > often think in terms of applying algorithms to containers ("I want to
sort
> > this list."). Allowing them to express that concept directly in code
makes
> > the code easier to write and read.
> >
>
> In other words, we should redesign STL to make it look like what
> programmers who don't understand it think it is. <g>
In short, yes! Isn't that what concepts like "abstraction" and "high-level"
are all about; making something look like what the programmer thinks it is,
regardless of how the underlying mechanism is implemented?
In this case, we have a disconnect between how programmers think of a
problem and how STL presents its functions. The "redesign" solves the
problem, seems very simple, and does not involve breaking any existing code.
What's the downside here?
Matt Seitz
> Matt Seitz wrote:
> >
> > Allowing a programmer to express an operation in the terms they use to
think
> > of the problem makes it easier to both read and write code. Programmers
> > often think in terms of applying algorithms to containers ("I want to
sort
> > this list."). Allowing them to express that concept directly in code
makes
> > the code easier to write and read.
> >
>
> I never sort a list. I sort the contents of a list.
That is a subtle distinction that is not made in the common use of English
language. In common usage, "sorting a list" and "sorting the contents of a
list" are used interchangably to mean the same thing.
> In STL terms, that means that I sort the sequence of values contained in
the list.
So why not make "sorting a list" mean, in STL terms, sorting the sequence of
values contained in the list, just as "sorting the contents of a list" means
sorting the sequence of values contained in the list? Why is it so vital to
make programmers think in terms of "sort from the beginning of the list to
the end of the list" rather than simply "sort the list"?
Dave Harris
> The obvious sequence is [r, r + 1) if found or [last, last) when not
> found.
So obvious it didn't occur to me :-)
Currently find() returns a point from within the sequence it is given. I
don't see any reason to change that semantics. Making find() return a
new, single-element sequence seems like it is trying to push sequences
where they don't fit. find() is not equal_range().
> You do allow empty sequences don't you?
Of course.
> But, that seems to be a problem when last is a condition not
> an iterator. Then neither of them is valid.
It is a problem if the return sequence must have the same type as the
argument sequence. I wouldn't make that restriction.
> What does equal_range return? A pair of iterators or a sequence?
It seems clear to me that it *does* return a sequence, even if it is not
explicit. std::pair<iterator,iterator> is a sequence in disguise.
I suggest that equal_range be:
template <typename sequence, typename value>
iterator_sequence<sequence::iterator> equal_range(
sequence s, const value &v );
In other words, it returns a sequence of a different type.
> > I'd prefer to avoid needless inefficiency in common idioms.
>
> I've been following this with interest. It now appears that a sequence
> is nothing more than another abstraction to confuse the issues.
> Premature optimization is ...
I know "efficiency" is a dirty word to some people. I think efficiency is
a good thing; it suggests we are "carving nature at the joints". I
distrust designs that are gratuitously inefficient, because that usually
results from redundancy and/or poor understanding of essence, which hints
at other problems. A concern for efficiency runs all though the STL.
Of course, explicit sequences are not only, or even primarily, about
efficiency. They seem to have many potential benefits - they are less
repetitive, less error-prone and more generic. So I don't agree they are
a premature optimisation.
Dave Harris, Nottingham, UK | "Weave a circle round him thrice,
bran...@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."
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
Programming is not "common usage". It's technical writing, and
distinctions between things that are different are important.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Peter Dimov
>Pete Becker <peteb...@acm.org> wrote:
>> What is the advantage of this over the current mechanism:
>>
>> char text[] = "Hello, world";
>> sort(text, text + sizeof(text));
>
>
>Since everybody seems to re-iterate old arguments:
>
>
>You have to type "text" (at least) twice.
Spell it 't'. :-)
In a for loop you usually have to type 'i' at least three times.
>So what if "text" is not a static char[] but the result of some longish
>computation?
>
>"Make an explicit temporary" you say.
>
>
>Of what type? typeof() is not part of the language, is it?
It's not, and even if it was, it probably wouldn't be the tool for declaring
temporaries.
The usual solution for the problem
typeof(expr) temp(expr);
// do something with temp
is
template<class T> void f(T temp)
{
// do something with temp
}
f(expr);
If we apply this principle to our current situation, we'd arrive at
template<class C> typename C::iterator begin(C & c)
{
return c.begin();
}
template<class T, int N> T * begin(T (&a) [N])
{
return a;
}
template<class C> typename C::iterator end(C & c)
{
return c.end();
}
template<class T, int N> T * end(T (&a) [N])
{
return a + N;
}
template<class C> void sort2(C & c)
{
std::sort(begin(c), end(c));
}
and then we could simply write
sort2(text);
The question now is how much of the code above should go into std::.
begin/end
should have been std::begin/std::end from the start, IMHO; but I'm not
convinced about sort2 becoming an overload for std::sort. The standard
library
is not a repository for cool one-liners. :-) On the other hand, a
single-argument sort() can detect a std::list and do the right thing.
--
Peter Dimov
Multi Media Ltd.
Pete Becker
>
> "Pete Becker" <peteb...@acm.org> wrote in message
> news:3B01251F...@acm.org...
> > Matt Seitz wrote:
> > >
> > > Allowing a programmer to express an operation in the terms they use to
> think
> > > of the problem makes it easier to both read and write code. Programmers
> > > often think in terms of applying algorithms to containers ("I want to
> sort
> > > this list."). Allowing them to express that concept directly in code
> makes
> > > the code easier to write and read.
> > >
> >
> > In other words, we should redesign STL to make it look like what
> > programmers who don't understand it think it is. <g>
>
> In short, yes! Isn't that what concepts like "abstraction" and "high-level"
> are all about; making something look like what the programmer thinks it is,
> regardless of how the underlying mechanism is implemented?
No, not at all. Abstraction is not about making things easy for people
who don't know what they're doing. It's about isolating dependencies,
and that usually requires deep knowledge of the problem domain.
>
> In this case, we have a disconnect between how programmers think of a
> problem and how STL presents its functions.
No, there is perhaps a disconnect between how SOME programmers think of
a problem and how STL presents its functions. It's certainly possible to
change how STL works. It's also possible to change programmers who
haven't bothered to understand how STL works, by encouraging them to
understand it. It's a very elegant design, and hacking at it in order to
make it easier for lazy programmers to use is would not be an
improvement.
> The "redesign" solves the
> problem, seems very simple, and does not involve breaking any existing code.
> What's the downside here?
>
The downside is that this would result in two different ways of doing
the same thing, only one of which provides the full generality of the
STL.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Nick Thurn
> > > programmers who don't understand it think it is. <g>
> >
> > In short, yes! Isn't that what concepts like "abstraction" and "high-level"
> > are all about; making something look like what the programmer thinks it is,
> > regardless of how the underlying mechanism is implemented?
>
> No, not at all. Abstraction is not about making things easy for people
> who don't know what they're doing. It's about isolating dependencies,
> and that usually requires deep knowledge of the problem domain.
>
Algorithms are nice and consistent wrt using pairs of iterators.
Containers cause problems becaues they are inherently inconsistent
depending on implementation (eg list<T> sort, remove_if, reverse,
merge and unique).
The problem is that containers are what most folks use most often
(if they use the stl *at all*). Easier or more consistent ways
of using containers is desirable (eg if list has the members
above so should other containers where they make semantic sense).
IMO consistency is more important than purity. You are wrong
wrt abstraction. Abstraction is about hiding detail and merging
many concepts into a simpler one. This is a two edged sword as
casual users can do inappropriate things. A useful library
provides ways to use it *without deep understanding* that
does not punish the user.
> >
> > In this case, we have a disconnect between how programmers think of a
> > problem and how STL presents its functions.
>
> No, there is perhaps a disconnect between how SOME programmers think of
> a problem and how STL presents its functions. It's certainly possible to
Sorry it's MOST not SOME. Most so called C++ Programmers are enmeshed
in MS specific noise and ignore the standard.
> change how STL works. It's also possible to change programmers who
> haven't bothered to understand how STL works, by encouraging them to
> understand it. It's a very elegant design, and hacking at it in order to
> make it easier for lazy programmers to use is would not be an
> improvement.
>
It's not lazyness. It's the fact that containers appear to have been
seen as merely a means to an end while algorithms were central.
In most usage containers are central. The missing link between
containers and algorithms needs filling in.
somecontainer<X> c;
sort(c); // error on ordered and associative containers
// or
c.sort(); // again only available for unordered containers
makes more sense than the iterator based version when
the entire container is to be sorted. It is more readable
and shorter. It is also a zero overhead when implemented
as simply passing control to std::sort(c.begin(),c.end()).
No one has commented on my suggestion on adding an algorithm
adaptor to containers to make them consistent without having
to create a raft of new algorithm/container adaptors (even
the usual "tut tut tut" hasn't materialised ;-). Perhaps
it's a dumb (tm) idea.
> > The "redesign" solves the
> > problem, seems very simple, and does not involve breaking any existing code.
> > What's the downside here?
> >
>
> The downside is that this would result in two different ways of doing
> the same thing, only one of which provides the full generality of the
> STL.
>
I thought having 200 ways to do the same thing *was* the standard ;-)
cheers
Nick nick....@db.com
Francis Glassborow
Seitz <mse...@yahoo.com> writes
>In short, yes! Isn't that what concepts like "abstraction" and "high-level"
>are all about; making something look like what the programmer thinks it is,
>regardless of how the underlying mechanism is implemented?
But experience is about modifying our expectations to meet reality.
Anyone who has learnt to sail a small boat will remember that steering a
boat is counter intuitive, but after a few hours what the novice does
seems counter intuitive:)
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
John Potter
> jpo...@falcon.lhup.edu (John Potter) wrote (abridged):
> Currently find() returns a point from within the sequence it is given. I
> don't see any reason to change that semantics. Making find() return a
> new, single-element sequence seems like it is trying to push sequences
> where they don't fit. find() is not equal_range().
An admission that sequences are just a special case patch which is not
needed in the general system of iterators?
> > What does equal_range return? A pair of iterators or a sequence?
>
> It seems clear to me that it *does* return a sequence, even if it is not
> explicit. std::pair<iterator,iterator> is a sequence in disguise.
>
> I suggest that equal_range be:
>
> template <typename sequence, typename value>
> iterator_sequence<sequence::iterator> equal_range(
> sequence s, const value &v );
>
> In other words, it returns a sequence of a different type.
>
>
> > > I'd prefer to avoid needless inefficiency in common idioms.
> >
> > I've been following this with interest. It now appears that a sequence
> > is nothing more than another abstraction to confuse the issues.
> > Premature optimization is ...
>
> I know "efficiency" is a dirty word to some people. I think efficiency is
> a good thing; it suggests we are "carving nature at the joints". I
> distrust designs that are gratuitously inefficient, because that usually
> results from redundancy and/or poor understanding of essence, which hints
> at other problems. A concern for efficiency runs all though the STL.
>
> Of course, explicit sequences are not only, or even primarily, about
> efficiency. They seem to have many potential benefits - they are less
> repetitive, less error-prone and more generic. So I don't agree they are
> a premature optimisation.
My point was that refusing to use a sequence where it would work is the
premature optimization. This idea is just getting started. Don't kill
it by saying that sequences are inefficient.
What does copy return? I want to cascade algorithms.
copy(sort(transform(equal_range(first_seq), second_seq, f)), third_seq);
How about a pipe_sequence? Overload operator| and operator>
equal_range(first_seq) | make_pair(transform, f) | sort | copy >
third_seq;
Now maybe you've got something.
If a sequence is just a pair<iterator, iterator> in disguise, I don't
need them. I have not seen anything that a sequence can represent
that can not also be represented by an iterator pair. If sequences
"don't fit" they are excess baggage.
John
John Potter
wrote:
> Algorithms are nice and consistent wrt using pairs of iterators.
>
> Containers cause problems becaues they are inherently inconsistent
> depending on implementation (eg list<T> sort, remove_if, reverse,
> merge and unique).
Merge, remove, reverse, and unique are optimizations for list and
belong there only. Of course, remove should be called erase. The
general algorithms still work for list.
Sort is the problem. It is fine for list to have an optimization for
this algorithm also. It is a problem for the general algorithm to
not work for list. When the most visible algorithm in the library is
inconsistent, it makes the whole library seem wrong.
> No one has commented on my suggestion on adding an algorithm
> adaptor to containers to make them consistent without having
> to create a raft of new algorithm/container adaptors (even
> the usual "tut tut tut" hasn't materialised ;-). Perhaps
> it's a dumb (tm) idea.
IMO, it creates a new problem rather than solving the real problem.
John
Pete Becker
>
> A useful library
> provides ways to use it *without deep understanding* that
> does not punish the user.
>
I wasn't talking about requiring users to have deep understanding of the
problem domain. I was talking about the designer of the abstraction.
Beginners should not design interfaces; they simply don't know enough to
do it well.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Pete Becker
>
> Pete Becker wrote:
> > change how STL works. It's also possible to change programmers who
> > haven't bothered to understand how STL works, by encouraging them to
> > understand it. It's a very elegant design, and hacking at it in order to
> > make it easier for lazy programmers to use is would not be an
> > improvement.
> >
>
> It's not lazyness. It's the fact that containers appear to have been
> seen as merely a means to an end while algorithms were central.
Yes, that's how STL was designed.
>
> In most usage containers are central. The missing link between
> containers and algorithms needs filling in.
>
> somecontainer<X> c;
> sort(c); // error on ordered and associative containers
> // or
> c.sort(); // again only available for unordered containers
>
> makes more sense than the iterator based version when
> the entire container is to be sorted. It is more readable
> and shorter. It is also a zero overhead when implemented
> as simply passing control to std::sort(c.begin(),c.end()).
It is conceptual overhead when someone has to switch to a different
notion of what constitutes a sequence in order to sort part of a
sequence, or, indeed, to sort the command line arguments that come in
through argv. The elegance of the STL is that algorithms have a
consistent interface. Certainly, list::sort is ugly, but that doesn't
mean that evey container should be equally ugly.
>
> No one has commented on my suggestion on adding an algorithm
> adaptor to containers to make them consistent without having
> to create a raft of new algorithm/container adaptors (even
> the usual "tut tut tut" hasn't materialised ;-). Perhaps
> it's a dumb (tm) idea.
>
> > > The "redesign" solves the
> > > problem, seems very simple, and does not involve breaking any existing code.
> > > What's the downside here?
> > >
> >
> > The downside is that this would result in two different ways of doing
> > the same thing, only one of which provides the full generality of the
> > STL.
> >
> I thought having 200 ways to do the same thing *was* the standard ;-)
>
Design by cheapshot is just as bad as design by beginners.
--
Pete Becker
Dinkumware, Ltd. (http://www.dinkumware.com)
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
Nick Thurn
> Nick Thurn wrote:
> >
> > It's not lazyness. It's the fact that containers appear to have been
> > seen as merely a means to an end while algorithms were central.
>
> Yes, that's how STL was designed.
>
> It is conceptual overhead when someone has to switch to a different
> notion of what constitutes a sequence in order to sort part of a
> sequence, or, indeed, to sort the command line arguments that come in
> through argv. The elegance of the STL is that algorithms have a
Disagree. Partial sorting is not the most common usage. The conceptual
overhead is very low.
> consistent interface. Certainly, list::sort is ugly, but that doesn't
> mean that evey container should be equally ugly.
>
I disagree that it is ugly. It is against the spirit of separation
of containers and algorithms however sort is in a gray area where
the algorithm is inherent to the container. IMO the ugliness
is in NOT providing a consistent interface to the other unordered
containers.
Removing list::sort etc would be the most consistent resolution.
This would only be realistic if a specialisation that sorted merged...
lists or parts of lists as efficiently was mandated (and implementable).
Adding the special methods from list to vector and deque would
also be consistent however if implemented using the iterator pair
algorithms it would add unnecessary visibility of the <algorithm>
header to <vector> and <deque>.
cheers
Nick