Algorithms in C++

[beli...@aol.com]

Robert Sedgewick has written well-known books on algorithms with

Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching, Third Edition 3rd Edition

being published in 1998. I know that C++ has changed a lot since 1998. Is there a book on algorithms in C++ that uses the more modern features of the language? Or is this book still a good one for a beginning C++ programmer?

[Öö Tiib]

It is *not* book that teaches C++. It is book that teaches algorithms.
4th edition seems to be printed 2014 so it is likely good book.
Algorithms can be expressed in any programming language, in some pseudo-code
or in human language. A book about algorithms is not teaching programming
language and is bad source for actual implementations. It is teaching the
way how to think about algorithms. Most compile-time checks run-time
checks optimization tricks and whatever meta-programming are usually cut
out of book illustration codes. OTOH if you take implementation of
particular algorithm from standard library or some other library then
it is likely well-optimized and tested but is bad illustration to the
algorithm it implements.

If you want other books about algorithms then perhaps start with
bestsellers list from Amazon:
https://www.amazon.com/Best-Sellers-Books-Programming-Algorithms/zgbs/books/3870

... then research further what each book is. You may find online courses
and even freely available books. For example:
Algorithms by Robert Sedgewick & Kevin Wayne (Java and C++)
4th edition seems to be free to read here (http://algs4.cs.princeton.edu/home/)

However if you want to learn C++ then find yourself a book about C++
language.

[Bo Persson]

The book is about algorithms and not about C++. It uses code to
illustrate the items it explains, but the code is from the 1990's and
adapted from other language editions of the book.

So it uses lots of arrays an indexes, when modern C++ code would use
iterators over a sequence. And of course, it cannot use any of the new
neat features from C++11 and C++14.

So, for learning algorithms it is ok, for learning C++ - not so good.


Bo Persson

[Richard]

[Please do not mail me a copy of your followup]

beli...@aol.com spake the secret code
<9f0314bb-317f-4313...@googlegroups.com> thusly:

Have you tried contacting the author directly? Most of these people
can be directly reached on the net these days.
--
"The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline>
The Computer Graphics Museum <http://computergraphicsmuseum.org>
The Terminals Wiki <http://terminals.classiccmp.org>
Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[Alf P. Steinbach]

On 18.09.2016 16:44, Stefan Ram wrote:
>
> [snip]
> I must mention that Chandler Carruth in a recent speech
> praised Wirth's book "Algorithms + Data Structures =
> Programs" from 1976. Chandler looks quite young to me.
> So I thought: Young people in the seventies learned
> programming from this book, and now - in the 2010s -
> young people read and praise it. That's quite exceptional
> for a programming book!

Unfortunately the original Pascal based version is not freely available,
as far as I know.

However, Wirth rewrote it in Modula-2 or Oberon (I don't remember which
of these two languages), and that version is available.

I think if he wrote that book today, he's just 82 so that's something he
really might do, he'd call it “algorithms + data structures =
functions”. For as Betrand Meyers remarked, “real systems have no top”
(quoting from memory). A modern program of some size is not structured
as a single function, other than an artifical `main` to start it.


Cheers!,

- Alf

[Osmium]

"Alf P. Steinbach" wrote:

> On 18.09.2016 16:44, Stefan Ram wrote:
>>
>> [snip]
>> I must mention that Chandler Carruth in a recent speech
>> praised Wirth's book "Algorithms + Data Structures =
>> Programs" from 1976. Chandler looks quite young to me.
>> So I thought: Young people in the seventies learned
>> programming from this book, and now - in the 2010s -
>> young people read and praise it. That's quite exceptional
>> for a programming book!
>
> Unfortunately the original Pascal based version is not freely available,
> as far as I know.

I have the original version and like it. Amazon lists several used copies
as being available. It would probably be a good idea to verify, with the
seller, that he is selling the first edition, which, of course, is not
marked as first edition. Mine is marked ©1976 and the cover is white and
red.

[Mr Flibble]

On 19/09/2016 20:53, Stefan Ram wrote:
> int main( void ){ abort(); }
>
> is a program. Both call into a library.
>
> But »main« still is crucial. Change
> »application_start« into »abort« and
> it will be a word processor no more.
>
> That main can be so small, does not
> change the fact that it's so important.

No, it isn't. It is possible for a C++ program to do whatever it needs
to without main ever being called.

/Flibble

[Mr Flibble]

Example of a C++ program that never calls main():

#include <iostream>

struct program
{
program()
{
std::cout << "Hello, World!" << std::endl;
exit(0);
};
} instance;

int main() {}

[woodb...@gmail.com]

That's a mess compared to a "Hello, World" that uses main().

Brian
Ebenezer Enterprises - In G-d we trust.
http://webEbenezer.net

[David Brown]

I don't think Mr. Flibble was suggesting it was a good idea to replace
main() with the constructor of a static object - merely that it is
/possible/ to do so. In particular, such constructors let you do useful
work before main() is called, and it is possible that an issue in such
constructors means that main() is /never/ called.

And in a freestanding environment, the toolchain can happily have no
main() function (the "main" function can have any name), and you may
have many methods for calling code before a "main" function is run.

[Öö Tiib]

Neither woodbrian nor Flibble wrote if it is good or bad idea.
Flibble seemingly wrote that it is possible and woodbrian
seemingly wrote that it has messy style. IMHO it is an idea
to avoid.

Calling order of such static object (and static data member
object) constructors is defined only within single compilation
unit that defines those. In project that matters there are lot of
compilation units. So when the statics are defined in several
compilation units and the initialization order matters then
things will become quite hairy.

The reasons how that order matters may pop up in late stages
of development and the "best" idioms of dealing with such
fiasco (like Schwarz counter) look quite confusing and will
result with pointless code generated. Additionally such
statics are source of synchronization issues and later there
can be destruction order fiasco as well. ;)

So I typically try to avoid the statics. When these are
unavoidable then I try to make these with maximally
lightweight and independent construction. When more
sophisticated initialization is needed then I try to dodge
it by adding lazy or explicit additional initialization steps
that will run after 'main' is called.

>
> And in a freestanding environment, the toolchain can happily have no
> main() function (the "main" function can have any name), and you may
> have many methods for calling code before a "main" function is run.

C++ standard has seemingly no good policy for choosing
what belongs into freestanding library and what does not.
It seems to require more than needed; also there are no
mechanism of indicating optional features. As result what
is "freestanding" feels incomplete and inconsistent. In
practice it is some non-conforming slice of C++ and so
it is hard to build any arguments upon it.

[David Brown]

On 20/09/16 13:45, Öö Tiib wrote:

>
> Calling order of such static object (and static data member
> object) constructors is defined only within single compilation
> unit that defines those. In project that matters there are lot of
> compilation units. So when the statics are defined in several
> compilation units and the initialization order matters then
> things will become quite hairy.

Yes indeed. It would be nice if there had been more control over this,
but I understand where the limitation comes from. (It would also have
been nice if it were possible to declare function-static objects, but
have them constructed/initialised before main() rather than when first
used.)

Even compiler extensions (such as gcc's init_priority attribute) leave
something to be desired - it uses numbers, and has no way to say
"initialise this object before that one" or "initialise that object
before this one".

It would all be much easier if the compiler could handle this better.
Perhaps compilers could spot common idioms (such as returning a
reference to a static object) and turn them into carefully ordered
pre-main initialisation.

[Öö Tiib]

On Tuesday, 20 September 2016 16:09:14 UTC+3, David Brown wrote:
> On 20/09/16 13:45, Öö Tiib wrote:
>
> >
> > Calling order of such static object (and static data member
> > object) constructors is defined only within single compilation
> > unit that defines those. In project that matters there are lot of
> > compilation units. So when the statics are defined in several
> > compilation units and the initialization order matters then
> > things will become quite hairy.
>
> Yes indeed. It would be nice if there had been more control over this,
> but I understand where the limitation comes from. (It would also have
> been nice if it were possible to declare function-static objects, but
> have them constructed/initialised before main() rather than when first
> used.)
>
> Even compiler extensions (such as gcc's init_priority attribute) leave
> something to be desired - it uses numbers, and has no way to say
> "initialise this object before that one" or "initialise that object
> before this one".

Also it AFAIK does not affect initialization order between different
shared libraries. It is comical how so lot of things use modules
written in C++ while C++ lacks a concept of modules whatsoever.

>
> It would all be much easier if the compiler could handle this better.
> Perhaps compilers could spot common idioms (such as returning a
> reference to a static object) and turn them into carefully ordered
> pre-main initialisation.

You probably did mean linker here. I would be happy even with
diagnostic that whatever order it mechanically picked results with
usage of not yet constructed object.

[Mr Flibble]

[snip]

But if you only have one such static object in your program then there
is no problem: you could use Meyers' Singleton for other objects.

/Flibble

[David Brown]

On 20/09/16 16:37, Öö Tiib wrote:
> On Tuesday, 20 September 2016 16:09:14 UTC+3, David Brown wrote:
>> On 20/09/16 13:45, Öö Tiib wrote:
>>
>>>
>>> Calling order of such static object (and static data member
>>> object) constructors is defined only within single compilation
>>> unit that defines those. In project that matters there are lot of
>>> compilation units. So when the statics are defined in several
>>> compilation units and the initialization order matters then
>>> things will become quite hairy.
>>
>> Yes indeed. It would be nice if there had been more control over this,
>> but I understand where the limitation comes from. (It would also have
>> been nice if it were possible to declare function-static objects, but
>> have them constructed/initialised before main() rather than when first
>> used.)
>>
>> Even compiler extensions (such as gcc's init_priority attribute) leave
>> something to be desired - it uses numbers, and has no way to say
>> "initialise this object before that one" or "initialise that object
>> before this one".
>
> Also it AFAIK does not affect initialization order between different
> shared libraries. It is comical how so lot of things use modules
> written in C++ while C++ lacks a concept of modules whatsoever.

One day, we will have proper modules in C++. I believe both clang and
MSVC have experimental module systems (I was going to say "module
concepts", but that would add to confusion with another overdue feature
of C++). But until one of these, or a combination, is picked as the
standard, it is not possible to work with them for anything more than
experimentation.

>
>>
>> It would all be much easier if the compiler could handle this better.
>> Perhaps compilers could spot common idioms (such as returning a
>> reference to a static object) and turn them into carefully ordered
>> pre-main initialisation.
>
> You probably did mean linker here. I would be happy even with
> diagnostic that whatever order it mechanically picked results with
> usage of not yet constructed object.
>

I really meant "toolchain", as I suspect this would need support from
both the compiler and the linker.

Certainly a useful diagnostic that things are not as you want them to be
is much better than silently wrong code!

[A. Bolmarcich]

On 2016-09-19, Osmium <r124c...@comcast.net> wrote:
> "Alf P. Steinbach" wrote:
>
>> On 18.09.2016 16:44, Stefan Ram wrote:
>>>
>>> [snip]
>>> I must mention that Chandler Carruth in a recent speech
>>> praised Wirth's book "Algorithms + Data Structures =
>>> Programs" from 1976. Chandler looks quite young to me.
>>> So I thought: Young people in the seventies learned
>>> programming from this book, and now - in the 2010s -
>>> young people read and praise it. That's quite exceptional
>>> for a programming book!
>>
>> Unfortunately the original Pascal based version is not freely available,
>> as far as I know.
>
> I have the original version and like it. Amazon lists several used copies
> as being available. It would probably be a good idea to verify, with the
> seller, that he is selling the first edition, which, of course, is not
> marked as first edition. Mine is marked ©1976 and the cover is white and
> red.
>
>> However, Wirth rewrote it in Modula-2 or Oberon (I don't remember which of
>> these two languages), and that version is available.

About ten years after "Algorithms + Data Structures = Programs" was
published, a new edition was published with the title "Algorithms &
Data Structures". According the to Preface of the new edition: "The
major change which prevades the entire text concerns the programming
language used to express the algorithms. Pascal has been replaced by
Modula-2."

--- news://freenews.netfront.net/ - complaints: ne...@netfront.net ---