MESSAGE
| DATE | 2016-12-02 |
| FROM | ruben safir
|
| SUBJECT | Subject: [Learn] Fwd: Tutorial on threaded binary tree part 1: simple
|
From learn-bounces-at-nylxs.com Fri Dec 2 17:47:35 2016
Return-Path:
X-Original-To: archive-at-mrbrklyn.com
Delivered-To: archive-at-mrbrklyn.com
Received: from www.mrbrklyn.com (www.mrbrklyn.com [96.57.23.82])
by mrbrklyn.com (Postfix) with ESMTP id 6FB96161312;
Fri, 2 Dec 2016 17:47:35 -0500 (EST)
X-Original-To: learn-at-nylxs.com
Delivered-To: learn-at-nylxs.com
Received: from [10.0.0.62] (flatbush.mrbrklyn.com [10.0.0.62])
by mrbrklyn.com (Postfix) with ESMTP id 6790E160E77
for ; Fri, 2 Dec 2016 17:47:30 -0500 (EST)
References:
<9090c736-611d-47ef-9214-5242d0307248-at-googlegroups.com>
<9ZadnT-WYP2JCdzFnZ2dnUU7-XXNnZ2d-at-giganews.com>
<_dKdnW0rnKZnP93FnZ2dnUU7-bPNnZ2d-at-giganews.com>
<38fa732e-e7ec-4e15-af08-a3eab7bfc66b-at-googlegroups.com>
To: learn-at-nylxs.com
From: ruben safir
X-Forwarded-Message-Id:
<9090c736-611d-47ef-9214-5242d0307248-at-googlegroups.com>
<9ZadnT-WYP2JCdzFnZ2dnUU7-XXNnZ2d-at-giganews.com>
<_dKdnW0rnKZnP93FnZ2dnUU7-bPNnZ2d-at-giganews.com>
<38fa732e-e7ec-4e15-af08-a3eab7bfc66b-at-googlegroups.com>
Message-ID:
Date: Fri, 2 Dec 2016 17:47:30 -0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
MIME-Version: 1.0
In-Reply-To:
Content-Type: multipart/mixed; boundary="------------5DBB2C766E4500A288914E29"
Subject: [Learn] Fwd: Tutorial on threaded binary tree part 1: simple
unthreaded tree
X-BeenThere: learn-at-nylxs.com
X-Mailman-Version: 2.1.17
Precedence: list
List-Id:
List-Unsubscribe: ,
List-Archive:
List-Post:
List-Help:
List-Subscribe: ,
Errors-To: learn-bounces-at-nylxs.com
Sender: "Learn"
This is a multi-part message in MIME format.
--------------5DBB2C766E4500A288914E29
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
enjoy
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Tutorial on threaded binary tree part 1: simple unthreaded tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Tutorial on threaded binary tree part 1: simple unthreaded t";
filename*1="ree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!goblin2!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Alf P. Steinbach"
Newsgroups: comp.lang.c++
Subject: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Thu, 1 Dec 2016 10:32:30 +0100
Organization: A noiseless patient Spider
Message-ID:
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 1 Dec 2016 09:34:11 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="9cd7663789d3a634ae180fd0240269a4";
logging-data="12473"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX1/z9ZwAHkoIJTHhlSQ0kzU+"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
Cancel-Lock: sha1:cn6OWD02nG3eSJeVJW59r82OmZ0=
Xref: panix comp.lang.c++:1125696
This tutorial, if it works (it's an experiment), is intended to work
this way:
* I post some working code.
* Learner(s) study it and ask about things.
* Others answer questions and post critique or get bogged down in long
sub-threads about sausages and swearing.
The following code implements a simple sorted binary tree with traversal.
There's no attempt at balancing, so this code does not deal nicely with
sorted input in the big O sense. Random input is the thing here. I used
the digits of pi.
[code]
namespace cppx {
struct No_copy_or_move
{
auto operator=( No_copy_or_move const& ) -> No_copy_or_move& =
delete;
auto operator=( No_copy_or_move&& ) -> No_copy_or_move& = delete;
No_copy_or_move() = default;
No_copy_or_move( No_copy_or_move const& ) = delete;
No_copy_or_move( No_copy_or_move&& ) = delete;
};
} // namespace cppx
namespace my {
using Value = double;
class Tree
: public cppx::No_copy_or_move
{
private:
struct Node
{
Node* left;
Node* right;
Value value;
};
Node* root_ = nullptr;
template< class Func >
static void apply_in_infix_order( Node* root, Func const& f )
{
if( root != nullptr )
{
apply_in_infix_order( root->left, f );
f( root->value );
apply_in_infix_order( root->right, f );
}
}
public:
void add( Value const& value )
{
Node** p_ptr = &root_;
while( *p_ptr != nullptr )
{
Node*& ref_ptr = *p_ptr;
p_ptr = &(value < ref_ptr->value? ref_ptr->left :
ref_ptr->right);
}
*p_ptr = new Node{ nullptr, nullptr, value };
}
template< class Func >
void for_each( Func const& f )
{
apply_in_infix_order( root_, f );
}
Tree() = default;
};
} // my
#include
using namespace std;
auto main()
-> int
{
my::Tree t;
for( int const v : {3, 1, 4, 1, 5, 9, 2, 6, 5, 4} )
{
t.add( v );
}
t.for_each(
[]( double x ) { cout << x << ' '; }
);
cout << endl;
}
}
[/code]
Enjoy,
- Alf
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!newsswitch.lcs.mit.edu!ottix-news.ottix.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 01 Dec 2016 14:23:14 -0600
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Newsgroups: comp.lang.c++
References:
From: Mr Flibble
Date: Thu, 1 Dec 2016 20:23:15 +0000
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
MIME-Version: 1.0
In-Reply-To:
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID:
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-BdrzLy8YnCMyQOhVTHd50gfXzRMlPtzOFAg+5wpiwUKORmaLBvNXGsgL1rSZppUPKMGpXEnaj9f6Bxc!R4+F6ihqceRLe6U3t7DfvvVFVHERQxMQWsoa1+6lWrCKsAFetRHRhwW5mf45nwuR+OLSRLQDZg==
X-Complaints-To: abuse-at-giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3910
Xref: panix comp.lang.c++:1125702
On 01/12/2016 09:32, Alf P. Steinbach wrote:
> This tutorial, if it works (it's an experiment), is intended to work
> this way:
>
> * I post some working code.
> * Learner(s) study it and ask about things.
> * Others answer questions and post critique or get bogged down in long
> sub-threads about sausages and swearing.
>
> The following code implements a simple sorted binary tree with traversal.
>
> There's no attempt at balancing, so this code does not deal nicely with
> sorted input in the big O sense. Random input is the thing here. I used
> the digits of pi.
>
>
> [code]
> namespace cppx {
> struct No_copy_or_move
> {
> auto operator=( No_copy_or_move const& ) -> No_copy_or_move& =
> delete;
> auto operator=( No_copy_or_move&& ) -> No_copy_or_move& = delete;
>
> No_copy_or_move() = default;
> No_copy_or_move( No_copy_or_move const& ) = delete;
> No_copy_or_move( No_copy_or_move&& ) = delete;
> };
> } // namespace cppx
>
> namespace my {
>
> using Value = double;
>
> class Tree
> : public cppx::No_copy_or_move
> {
> private:
> struct Node
> {
> Node* left;
> Node* right;
> Value value;
> };
>
> Node* root_ = nullptr;
>
> template< class Func >
> static void apply_in_infix_order( Node* root, Func const& f )
> {
> if( root != nullptr )
> {
> apply_in_infix_order( root->left, f );
> f( root->value );
> apply_in_infix_order( root->right, f );
> }
> }
>
> public:
> void add( Value const& value )
> {
> Node** p_ptr = &root_;
> while( *p_ptr != nullptr )
> {
> Node*& ref_ptr = *p_ptr;
> p_ptr = &(value < ref_ptr->value? ref_ptr->left :
> ref_ptr->right);
> }
> *p_ptr = new Node{ nullptr, nullptr, value };
> }
>
> template< class Func >
> void for_each( Func const& f )
> {
> apply_in_infix_order( root_, f );
> }
>
> Tree() = default;
> };
> } // my
>
> #include
> using namespace std;
> auto main()
> -> int
> {
> my::Tree t;
> for( int const v : {3, 1, 4, 1, 5, 9, 2, 6, 5, 4} )
> {
> t.add( v );
> }
> t.for_each(
> []( double x ) { cout << x << ' '; }
> );
> cout << endl;
> }
> }
> [/code]
Without balancing your tree is as good as useless; your post was totally
pointless.
/Flibble
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!jstuckle.eternal-september.org!.POSTED!not-for-mail
From: Jerry Stuckle
Newsgroups: comp.lang.c++
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Thu, 1 Dec 2016 16:54:55 -0500
Organization: A noiseless patient Spider
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 1 Dec 2016 21:53:21 -0000 (UTC)
Injection-Info: jstuckle.eternal-september.org; posting-host="dcd143411b7390f54b15f162d0e6185f";
logging-data="10662"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX19S9kP5/a/UvlcTo8ebxkwz8PEyv72jTnU="
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
In-Reply-To:
Cancel-Lock: sha1:gksImc+ntBB9YLXulJWKDaZqOQ4=
Xref: panix comp.lang.c++:1125704
On 12/1/2016 3:23 PM, Mr Flibble wrote:
> On 01/12/2016 09:32, Alf P. Steinbach wrote:
>> This tutorial, if it works (it's an experiment), is intended to work
>> this way:
>>
>> * I post some working code.
>> * Learner(s) study it and ask about things.
>> * Others answer questions and post critique or get bogged down in long
>> sub-threads about sausages and swearing.
>>
>> The following code implements a simple sorted binary tree with traversal.
>>
>> There's no attempt at balancing, so this code does not deal nicely with
>> sorted input in the big O sense. Random input is the thing here. I used
>> the digits of pi.
>
> Without balancing your tree is as good as useless; your post was totally
> pointless.
>
> /Flibble
>
No, it's not. This is a start and builds the tree correctly. Balancing
can come later. It's just a matter of adding about 4 functions and call
them from the appropriate places. The existing code will still work.
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex-at-attglobal.net
==================
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!goblin2!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Alf P. Steinbach"
Newsgroups: comp.lang.c++
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Fri, 2 Dec 2016 03:15:16 +0100
Organization: A noiseless patient Spider
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 2 Dec 2016 02:16:56 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="10898c670d21c99e9cd59e8600373116";
logging-data="29100"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX19OetErQVaMYS1m0Eh6Pm/N"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.1
In-Reply-To:
Cancel-Lock: sha1:x/bLMHnQuWt8mE8pIxHHlOC0JRk=
Xref: panix comp.lang.c++:1125709
On 01.12.2016 21:23, Mr Flibble wrote:
> On 01/12/2016 09:32, Alf P. Steinbach wrote:
[snip]
>> void add( Value const& value )
>> {
>> Node** p_ptr = &root_;
>> while( *p_ptr != nullptr )
>> {
>> Node*& ref_ptr = *p_ptr;
>> p_ptr = &(value < ref_ptr->value? ref_ptr->left :
>> ref_ptr->right);
>> }
>> *p_ptr = new Node{ nullptr, nullptr, value };
>> }
>>
[snip]
>
> Without balancing your tree is as good as useless; your post was totally
> pointless.
The intention of a “part 1”, implying a later “part 2”, and so on, was
to establish a baseline and see if the idea of generating discussion,
rather than providing it, panned out.
I agree that balancing is crucial for dealing with sorted or mostly
sorted input, to avoid quadratic accumulated insertion time.
And there's one even more special case to consider: the case of a sorted
input that is a sequence of equal values. Here simple balancing doesn't
help, because a sequence of equal values always becomes a degenerate
tree, a single branch of right-pointers (or left-pointers, depending on
one's choice), that cannot be balanced up. So ideally, to avoid square
time also for this special case, the `add` routine should be modified to
not descend down such a chain of equal value nodes.
Possibilities include:
• Inserting a new node with value V at the very top of an existing chain
of V, reducing the insertion complexity to logarithmic.
• Adding a value count in each node, and just incrementing it.
This precludes using the tree to associate different info with each
key V.
• Treating the tree as a simple set, and failing or doing nothing if V
already exists.
I think there may be some complexity hidden in the first possibility.
But anyway, as you can see, avoiding square time /in general/ so as to
make the structure generally useful, involves a decision about what the
tree is used for, and modifying the `add` routine accordingly:
a set (last bullet), a multiset (middle bullet), or a multimap (first
bullet)?
Cheers!,
- Alf
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
X-Received: by 10.99.115.14 with SMTP id o14mr19819840pgc.103.1480686354666;
Fri, 02 Dec 2016 05:45:54 -0800 (PST)
X-Received: by 10.157.15.143 with SMTP id d15mr2957516otd.2.1480686354555;
Fri, 02 Dec 2016 05:45:54 -0800 (PST)
Path: reader1.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!168.235.88.217.MISMATCH!feeder.erje.net!2.us.feeder.erje.net!newspeer1.nac.net!border2.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!n6no1279852qtd.0!news-out.google.com!m27ni1376qtf.1!nntp.google.com!n6no1279847qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Fri, 2 Dec 2016 05:45:54 -0800 (PST)
In-Reply-To:
Complaints-To: groups-abuse-at-google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=213.205.227.195;
posting-account=WDTkygoAAAA935ebIqvZE5RtOPZuShLr
NNTP-Posting-Host: 213.205.227.195
References:
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID:
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
From: leigh.v.johnston-at-googlemail.com
Injection-Date: Fri, 02 Dec 2016 13:45:54 +0000
Content-Type: text/plain; charset=UTF-8
Bytes: 1368
Xref: panix comp.lang.c++:1125712
Adding multiple identical keys should be no problem for any self balancing search tree otherwise we wouldn't have std::multiset and std::multimap.
/leigh
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
X-Received: by 10.157.17.136 with SMTP id v8mr10489360otf.92.1480696239020;
Fri, 02 Dec 2016 08:30:39 -0800 (PST)
X-Received: by 10.157.39.129 with SMTP id c1mr3062774otb.15.1480696238972;
Fri, 02 Dec 2016 08:30:38 -0800 (PST)
Path: reader1.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!newsswitch.lcs.mit.edu!ottix-news.ottix.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!p16no1356116qta.1!news-out.google.com!j8ni4962qtc.0!nntp.google.com!p16no1356112qta.1!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Fri, 2 Dec 2016 08:30:38 -0800 (PST)
In-Reply-To:
Complaints-To: groups-abuse-at-google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=212.47.207.1; posting-account=pysjKgkAAACLegAdYDFznkqjgx_7vlUK
NNTP-Posting-Host: 212.47.207.1
References:
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <9090c736-611d-47ef-9214-5242d0307248-at-googlegroups.com>
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
From: =?UTF-8?B?w5bDtiBUaWli?=
Injection-Date: Fri, 02 Dec 2016 16:30:39 +0000
Content-Type: text/plain; charset=UTF-8
Xref: panix comp.lang.c++:1125716
On Friday, 2 December 2016 15:46:18 UTC+2, leigh.v....-at-googlemail.com wrote:
> Adding multiple identical keys should be no problem for any self
> balancing search tree otherwise we wouldn't have std::multiset
> and std::multimap.
Not a problem but it takes some time to write and to test
otherwise we wouldn't have container templates.
There are different requirements so the underlying
implementation of such templates is often rather different.
Compare things like std::(unordered_)(multi)map(set,
boost::flat_(multi)map/set and boost::intrusive::set.
Lot of those don't even have tree underneath.
Implementing threaded binary tree sounds like not bad
idea as it allows to optimize out parent_ pointer in tree
node; fastens iterating over container up and reduces
potential need for recursive algorithms or fat iterators.
However that is theory ... in practice it looks like a
complex beast and so I haven't profiled one.
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!newsswitch.lcs.mit.edu!ottix-news.ottix.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 02 Dec 2016 09:32:36 -0600
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Newsgroups: comp.lang.c++
References:
From: Mr Flibble
Date: Fri, 2 Dec 2016 15:32:37 +0000
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.1
MIME-Version: 1.0
In-Reply-To:
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <9ZadnT-WYP2JCdzFnZ2dnUU7-XXNnZ2d-at-giganews.com>
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-0y9IrpuAjPMgs1Wus5+dHxy4JDobTB2GytYoXUzy+MPdltNDTZXfMQk5MXDWFGKVIrIB9hHKDoVN+DZ!dX4vs9pxZqezzUMChU26ZdX58Ka0Z2FgkMGsDpcTxyK27nOqmj6DgeK2B/3BnPz+seirlClR1A==
X-Complaints-To: abuse-at-giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4129
Xref: panix comp.lang.c++:1125713
On 02/12/2016 02:15, Alf P. Steinbach wrote:
> On 01.12.2016 21:23, Mr Flibble wrote:
>> On 01/12/2016 09:32, Alf P. Steinbach wrote:
> [snip]
>>> void add( Value const& value )
>>> {
>>> Node** p_ptr = &root_;
>>> while( *p_ptr != nullptr )
>>> {
>>> Node*& ref_ptr = *p_ptr;
>>> p_ptr = &(value < ref_ptr->value? ref_ptr->left :
>>> ref_ptr->right);
>>> }
>>> *p_ptr = new Node{ nullptr, nullptr, value };
>>> }
>>>
> [snip]
>>
>> Without balancing your tree is as good as useless; your post was totally
>> pointless.
>
> The intention of a “part 1”, implying a later “part 2”, and so on, was
> to establish a baseline and see if the idea of generating discussion,
> rather than providing it, panned out.
>
> I agree that balancing is crucial for dealing with sorted or mostly
> sorted input, to avoid quadratic accumulated insertion time.
>
> And there's one even more special case to consider: the case of a sorted
> input that is a sequence of equal values. Here simple balancing doesn't
> help, because a sequence of equal values always becomes a degenerate
> tree, a single branch of right-pointers (or left-pointers, depending on
> one's choice), that cannot be balanced up. So ideally, to avoid square
> time also for this special case, the `add` routine should be modified to
> not descend down such a chain of equal value nodes.
>
> Possibilities include:
>
> • Inserting a new node with value V at the very top of an existing chain
> of V, reducing the insertion complexity to logarithmic.
>
> • Adding a value count in each node, and just incrementing it.
> This precludes using the tree to associate different info with each
> key V.
>
> • Treating the tree as a simple set, and failing or doing nothing if V
> already exists.
>
> I think there may be some complexity hidden in the first possibility.
>
> But anyway, as you can see, avoiding square time /in general/ so as to
> make the structure generally useful, involves a decision about what the
> tree is used for, and modifying the `add` routine accordingly:
>
> a set (last bullet), a multiset (middle bullet), or a multimap (first
> bullet)?
>
> Cheers!,
Perhaps you are talking about guaranteeing the stability of a sequence
of duplicate keys? In which case an incrementing counter approach will
mean your insert operation cannot guarantee logarithmic complexity any
longer. The correct approach to implementing a binary search tree that
guarantees stability of duplicate key order is to make it a hybrid data
structure that also includes a linked list: this approach offers other
advantages: iterator increment/decrement changes from logarithmic
complexity to constant time.
/Flibble
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!newsswitch.lcs.mit.edu!ottix-news.ottix.net!border1.nntp.dca1.giganews.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 02 Dec 2016 10:15:08 -0600
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Newsgroups: comp.lang.c++
References:
<9ZadnT-WYP2JCdzFnZ2dnUU7-XXNnZ2d-at-giganews.com>
From: Mr Flibble
Date: Fri, 2 Dec 2016 16:15:10 +0000
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.1
MIME-Version: 1.0
In-Reply-To: <9ZadnT-WYP2JCdzFnZ2dnUU7-XXNnZ2d-at-giganews.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID:
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-NETziVX9csInBY2WFG2X28mWP5yll7ccYGGg68yhTTb73fJ3XErTwuh2kILkx/xD551ti1ISS0Te72Z!j9pip8sm/6mj3r9pv5e9JQhqQWxTcSNo/f8PQ2jhaniEUyUlxbyLE/yGUwH00Fq39ibVzVhkXQ==
X-Complaints-To: abuse-at-giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 4576
Xref: panix comp.lang.c++:1125715
On 02/12/2016 15:32, Mr Flibble wrote:
> On 02/12/2016 02:15, Alf P. Steinbach wrote:
>> On 01.12.2016 21:23, Mr Flibble wrote:
>>> On 01/12/2016 09:32, Alf P. Steinbach wrote:
>> [snip]
>>>> void add( Value const& value )
>>>> {
>>>> Node** p_ptr = &root_;
>>>> while( *p_ptr != nullptr )
>>>> {
>>>> Node*& ref_ptr = *p_ptr;
>>>> p_ptr = &(value < ref_ptr->value? ref_ptr->left :
>>>> ref_ptr->right);
>>>> }
>>>> *p_ptr = new Node{ nullptr, nullptr, value };
>>>> }
>>>>
>> [snip]
>>>
>>> Without balancing your tree is as good as useless; your post was totally
>>> pointless.
>>
>> The intention of a “part 1”, implying a later “part 2”, and so on, was
>> to establish a baseline and see if the idea of generating discussion,
>> rather than providing it, panned out.
>>
>> I agree that balancing is crucial for dealing with sorted or mostly
>> sorted input, to avoid quadratic accumulated insertion time.
>>
>> And there's one even more special case to consider: the case of a sorted
>> input that is a sequence of equal values. Here simple balancing doesn't
>> help, because a sequence of equal values always becomes a degenerate
>> tree, a single branch of right-pointers (or left-pointers, depending on
>> one's choice), that cannot be balanced up. So ideally, to avoid square
>> time also for this special case, the `add` routine should be modified to
>> not descend down such a chain of equal value nodes.
>>
>> Possibilities include:
>>
>> • Inserting a new node with value V at the very top of an existing chain
>> of V, reducing the insertion complexity to logarithmic.
>>
>> • Adding a value count in each node, and just incrementing it.
>> This precludes using the tree to associate different info with each
>> key V.
>>
>> • Treating the tree as a simple set, and failing or doing nothing if V
>> already exists.
>>
>> I think there may be some complexity hidden in the first possibility.
>>
>> But anyway, as you can see, avoiding square time /in general/ so as to
>> make the structure generally useful, involves a decision about what the
>> tree is used for, and modifying the `add` routine accordingly:
>>
>> a set (last bullet), a multiset (middle bullet), or a multimap (first
>> bullet)?
>>
>> Cheers!,
>
> Perhaps you are talking about guaranteeing the stability of a sequence
> of duplicate keys? In which case an incrementing counter approach will
> mean your insert operation cannot guarantee logarithmic complexity any
> longer. The correct approach to implementing a binary search tree that
> guarantees stability of duplicate key order is to make it a hybrid data
> structure that also includes a linked list: this approach offers other
> advantages: iterator increment/decrement changes from logarithmic
> complexity to constant time.
Obviously if you have a balancing scheme that does not alter sort order
of nodes (e.g. red-black tree rotation that most std:: node based
container implementations use) then stability of equivalent keys and
logarithmic complexity for insert can be guaranteed.
/Flibble
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!newsswitch.lcs.mit.edu!ottix-news.ottix.net!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 02 Dec 2016 09:55:42 -0600
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Newsgroups: comp.lang.c++
References:
From: Mr Flibble
Date: Fri, 2 Dec 2016 15:55:43 +0000
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.1
MIME-Version: 1.0
In-Reply-To:
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID:
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-2jufHO+h3s2o+ed2REcp0TF0qBMKI9Xm65etBZsBk2xq0b9jbWGjRdCCf3cIWmhwVdT4hyyPOu8YMdi!2Butuucqo0s6w/fElSoZoZ7bdh/oPexkXbyVvxklnRutMv3iU69wErkztHwQCzZ7ZTw+ADLIUw==
X-Complaints-To: abuse-at-giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3834
Xref: panix comp.lang.c++:1125714
On 02/12/2016 02:15, Alf P. Steinbach wrote:
> On 01.12.2016 21:23, Mr Flibble wrote:
>> On 01/12/2016 09:32, Alf P. Steinbach wrote:
> [snip]
>>> void add( Value const& value )
>>> {
>>> Node** p_ptr = &root_;
>>> while( *p_ptr != nullptr )
>>> {
>>> Node*& ref_ptr = *p_ptr;
>>> p_ptr = &(value < ref_ptr->value? ref_ptr->left :
>>> ref_ptr->right);
>>> }
>>> *p_ptr = new Node{ nullptr, nullptr, value };
>>> }
>>>
> [snip]
>>
>> Without balancing your tree is as good as useless; your post was totally
>> pointless.
>
> The intention of a “part 1”, implying a later “part 2”, and so on, was
> to establish a baseline and see if the idea of generating discussion,
> rather than providing it, panned out.
>
> I agree that balancing is crucial for dealing with sorted or mostly
> sorted input, to avoid quadratic accumulated insertion time.
>
> And there's one even more special case to consider: the case of a sorted
> input that is a sequence of equal values. Here simple balancing doesn't
> help, because a sequence of equal values always becomes a degenerate
> tree, a single branch of right-pointers (or left-pointers, depending on
> one's choice), that cannot be balanced up. So ideally, to avoid square
> time also for this special case, the `add` routine should be modified to
> not descend down such a chain of equal value nodes.
>
> Possibilities include:
>
> • Inserting a new node with value V at the very top of an existing chain
> of V, reducing the insertion complexity to logarithmic.
>
> • Adding a value count in each node, and just incrementing it.
> This precludes using the tree to associate different info with each
> key V.
>
> • Treating the tree as a simple set, and failing or doing nothing if V
> already exists.
>
> I think there may be some complexity hidden in the first possibility.
>
> But anyway, as you can see, avoiding square time /in general/ so as to
> make the structure generally useful, involves a decision about what the
> tree is used for, and modifying the `add` routine accordingly:
>
> a set (last bullet), a multiset (middle bullet), or a multimap (first
> bullet)?
You are wrong about how multiset and multimap differ: certainly they do
not correspond to your bullet points. multiset and multimap have
identical data structures: the only difference is multimap value_type is
a pair in which the key is the first part.
/Flibble
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!news.linkpendium.com!news.linkpendium.com!news.snarked.org!xmission!nnrp.xmission!.POSTED.shell.xmission.com!not-for-mail
From: legalize+jeeves-at-mail.xmission.com (Richard)
Newsgroups: comp.lang.c++
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Thu, 1 Dec 2016 21:34:32 +0000 (UTC)
Organization: multi-cellular, biological
Sender: legalize+jeeves-at-mail.xmission.com
Message-ID:
References:
Reply-To: (Richard) legalize+jeeves-at-mail.xmission.com
Injection-Date: Thu, 1 Dec 2016 21:34:32 +0000 (UTC)
Injection-Info: news.xmission.com; posting-host="shell.xmission.com:2607:fa18:0:beef::4";
logging-data="23954"; mail-complaints-to="abuse-at-xmission.com"
X-Reply-Etiquette: No copy by email, please
Mail-Copies-To: never
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
Originator: legalize-at-shell.xmission.com (Richard)
Xref: panix comp.lang.c++:1125703
[Please do not mail me a copy of your followup]
I believe you have said in previous threads that you like it for
"consistency" (which you don't seem to apply consistently throughout
even this small code sample), but the use of auto deduced return types
for methods and functions here feels gratuitous. It doesn't add any
clarity but comes at the expense of more tokens I have to scan through
in order to see what is happening.
"Everything should be made as simple as possible, but no simpler."
(Attributed to Einstein, )
To my mind, that means writing things in the simplest form with as
few tokens as possible.
It's why we write ++i instead of i = i + 1 and if (predicate) instead
of if (predicate == true). In both cases, the former is simpler and
expresses the exact same semantics.
Slavishly using auto and trailing return types on functions/methods
(and not even consistently throughout) just takes something simple
and makes it more complicated without any benefit.
Yes, it's a matter of style and not correctness, so your opinion may
differ -- I assume it does as you wrote it that way. Consider that when
we write code, we should think of the next person that is reading it
and not use code as an attempt to inculcate the rest of the world into
using our personal preferences.
Given that matters of style are personal taste, barring other
operational or security considerations, my tendency is to borrow the
style of Kernighan and Ritchie when writing code in C/C++. There are
many stylistic fads and opinions which differ from their style and I
uniformly have found them all to be of no benefit, or at best they
solve a problem in the wrong way. Your code exhibits one or two of
these tendencies but I don't consider them to be worth elevating to a
point of discussion as much as the gratuitous use of auto deduced
return types.
--
"The Direct3D Graphics Pipeline" free book
The Terminals Wiki
The Computer Graphics Museum
Legalize Adulthood! (my blog)
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!168.235.88.217.MISMATCH!2.us.feeder.erje.net!feeder.erje.net!1.eu.feeder.erje.net!newsfeed.datemas.de!enother.net!enother.net!enother.net!peer02.fr7!futter-mich.highwinds-media.com!peer01.iad!feed-me.highwinds-media.com!news.highwinds-media.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Thu, 01 Dec 2016 16:23:54 -0600
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Newsgroups: comp.lang.c++
References:
From: Mr Flibble
Date: Thu, 1 Dec 2016 22:23:56 +0000
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
MIME-Version: 1.0
In-Reply-To:
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <_dKdnW0rnKZnP93FnZ2dnUU7-bPNnZ2d-at-giganews.com>
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-MPyOLu+zn1yDmHJ6xL2Naf86uH8LVuZO9FPGP3VufHIwxBLthj7hGcQvdoVX9ybhxToEMqbYWJoQ+0E!Eg8YBfnfpc4D1S9ZvnQlhZnAUUeSHiwpqg7VAXHDD1W+9IpMukfXjzguQiSlAROve3nij7Yzrg==
X-Complaints-To: abuse-at-giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3433
X-Received-Body-CRC: 3297266546
X-Received-Bytes: 3645
Xref: panix comp.lang.c++:1125705
On 01/12/2016 21:34, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> I believe you have said in previous threads that you like it for
> "consistency" (which you don't seem to apply consistently throughout
> even this small code sample), but the use of auto deduced return types
> for methods and functions here feels gratuitous. It doesn't add any
> clarity but comes at the expense of more tokens I have to scan through
> in order to see what is happening.
>
> "Everything should be made as simple as possible, but no simpler."
> (Attributed to Einstein, )
>
> To my mind, that means writing things in the simplest form with as
> few tokens as possible.
>
> It's why we write ++i instead of i = i + 1 and if (predicate) instead
> of if (predicate == true). In both cases, the former is simpler and
> expresses the exact same semantics.
>
> Slavishly using auto and trailing return types on functions/methods
> (and not even consistently throughout) just takes something simple
> and makes it more complicated without any benefit.
>
> Yes, it's a matter of style and not correctness, so your opinion may
> differ -- I assume it does as you wrote it that way. Consider that when
> we write code, we should think of the next person that is reading it
> and not use code as an attempt to inculcate the rest of the world into
> using our personal preferences.
>
> Given that matters of style are personal taste, barring other
> operational or security considerations, my tendency is to borrow the
> style of Kernighan and Ritchie when writing code in C/C++. There are
> many stylistic fads and opinions which differ from their style and I
> uniformly have found them all to be of no benefit, or at best they
> solve a problem in the wrong way. Your code exhibits one or two of
> these tendencies but I don't consider them to be worth elevating to a
> point of discussion as much as the gratuitous use of auto deduced
> return types.
+1
(Alf will now go off in a strop and write a Hello, World! program so he
can write "auto main() -> int" again like some crazy OCD cat person.)
/Flibble
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!168.235.88.217.MISMATCH!2.us.feeder.erje.net!feeder.erje.net!2.eu.feeder.erje.net!news.swapon.de!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Alf P. Steinbach"
Newsgroups: comp.lang.c++
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Fri, 2 Dec 2016 00:32:42 +0100
Organization: A noiseless patient Spider
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 1 Dec 2016 23:34:21 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="10898c670d21c99e9cd59e8600373116";
logging-data="3820"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX1+GrUZjPoWN1fJJ1sqRK1hG"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
In-Reply-To:
Cancel-Lock: sha1:zMAU6iNTLt2BUopoLTIUxUH/2jQ=
Xref: panix comp.lang.c++:1125706
On 01.12.2016 22:34, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> I believe you have said in previous threads that you like it for
> "consistency" (which you don't seem to apply consistently throughout
> even this small code sample), but the use of auto deduced return types
> for methods and functions here feels gratuitous. It doesn't add any
> clarity but comes at the expense of more tokens I have to scan through
> in order to see what is happening.
There are no deduced return types in this code.
Mainly because I mostly agree with your sentiment here. :)
[snip]
> Slavishly using auto and trailing return types on functions/methods
> (and not even consistently throughout) just takes something simple
> and makes it more complicated without any benefit.
Re consistency, this code is totally consistent:
* `void` for Pascal /procedures/ (no expression result functions).
* `auto` for Pascal functions (functions that return value).
:)
But the 100% consistency here is just a coincidence, due to the
shortness of the code. I do not believe 100% consistency is good! In the
end, I believe, this boils down to the reason why programming can't be
automated: we need humans to supply intelligence.
Dang, there was a good quote about consistency, I've forgotten it...
Cheers!,
- Alf
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!news.linkpendium.com!news.linkpendium.com!news.snarked.org!xmission!nnrp.xmission!.POSTED.shell.xmission.com!not-for-mail
From: legalize+jeeves-at-mail.xmission.com (Richard)
Newsgroups: comp.lang.c++
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Thu, 1 Dec 2016 23:57:06 +0000 (UTC)
Organization: multi-cellular, biological
Sender: legalize+jeeves-at-mail.xmission.com
Message-ID:
References:
Reply-To: (Richard) legalize+jeeves-at-mail.xmission.com
Injection-Date: Thu, 1 Dec 2016 23:57:06 +0000 (UTC)
Injection-Info: news.xmission.com; posting-host="shell.xmission.com:2607:fa18:0:beef::4";
logging-data="29160"; mail-complaints-to="abuse-at-xmission.com"
X-Reply-Etiquette: No copy by email, please
Mail-Copies-To: never
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
Originator: legalize-at-shell.xmission.com (Richard)
Xref: panix comp.lang.c++:1125707
[Please do not mail me a copy of your followup]
"Alf P. Steinbach" spake the secret code
thusly:
>On 01.12.2016 22:34, Richard wrote:
>> [...] but the use of auto deduced return types
>> for methods and functions here feels gratuitous.
>There are no deduced return types in this code.
OK, consider that nit picked. s/deduced/trailing/.
>Re consistency, this code is totally consistent:
>
>* `void` for Pascal /procedures/ (no expression result functions).
>* `auto` for Pascal functions (functions that return value).
Again, back to the point of the audience that is reading this code.
The fact that you had to explain your "consistency" is buttressing my
assertion that this style is leading to less clarity and not more.
When I read the code, I see some things using trailing return types
and some things not using trailing return types.
If using auto is good enough for trailing type int, why isn't it
good enough for trailing type void?
If using classic return type without auto is good enough for void,
why isn't it good enough for int?
Etc.
Again, this style just makes me think "someone is all excited about
the new syntax of trailing return types and is using it gratuitously"
instead of using it where it adds clarity as in type deduction of a
return type from an expression using types of input arguments.
--
"The Direct3D Graphics Pipeline" free book
The Terminals Wiki
The Computer Graphics Museum
Legalize Adulthood! (my blog)
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!168.235.88.217.MISMATCH!2.us.feeder.erje.net!feeder.erje.net!1.eu.feeder.erje.net!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Alf P. Steinbach"
Newsgroups: comp.lang.c++
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Fri, 2 Dec 2016 01:14:23 +0100
Organization: A noiseless patient Spider
Message-ID:
References:
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 2 Dec 2016 00:16:02 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="10898c670d21c99e9cd59e8600373116";
logging-data="10508"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX1/tzVes/mtUaYuzPHjN7HDS"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.0
In-Reply-To:
Cancel-Lock: sha1:4C1f7fieNnwpKvb+dUKi952dX0k=
Xref: panix comp.lang.c++:1125708
On 02.12.2016 00:57, Richard wrote:
> [Please do not mail me a copy of your followup]
>
> "Alf P. Steinbach" spake the secret code
> thusly:
>
>> On 01.12.2016 22:34, Richard wrote:
>>> [...] but the use of auto deduced return types
>>> for methods and functions here feels gratuitous.
>
>> There are no deduced return types in this code.
>
> OK, consider that nit picked. s/deduced/trailing/.
There is world of difference.
>> Re consistency, this code is totally consistent:
>>
>> * `void` for Pascal /procedures/ (no expression result functions).
>> * `auto` for Pascal functions (functions that return value).
>
> Again, back to the point of the audience that is reading this code.
> The fact that you had to explain your "consistency" is buttressing my
> assertion that this style is leading to less clarity and not more.
>
> When I read the code, I see some things using trailing return types
> and some things not using trailing return types.
>
> If using auto is good enough for trailing type int, why isn't it
> good enough for trailing type void?
For the very common single case of `void` functions, `auto` just adds
verbosity (for member function implementations it can drastically reduce
verbosity, but for simple `void` functions it adds wordage).
Also, as I see it it's very nice to have this class of functions singled
out visually, as with the Pascal keyword `procedure` (which had that
exact purpose: to single them out). Because in the basic meaning the
`void` functions have a very different purpose, namely to /do/ something
rather than /compute/ something. Of course it's possible to use either
class of function for the opposite purpose, with just more awkward
notation, but that's the basis ? and via the C++11 and later support for
move semantics, C++ now increasingly supports the style where
computations yield function results, used in /expressions/.
Most computer scientist, I believe, view that usage as the ideal, that a
routine that computes something should return that as its function
result, and therefore agree that the C conflation of procedure and
function was a bad choice. In original C one would have to let those
procedures return `int`, either explicitly or via C implicit int. It was
ugly, the code saying something different than the intention.
> If using classic return type without auto is good enough for void,
> why isn't it good enough for int?
Singling out `void`, procedures, is doable and has a reason (which IMO
is strong and good).
Not so for `int`.
But people have argued that `int main()` is so idiomatic that it just
feels wrong and perplexing to see it expressed with `auto`. I do that
for consistency. And also, to introduce the syntax to more people. :)
Cheers!,
- Alf
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!newsswitch.lcs.mit.edu!xmission!nnrp.xmission!.POSTED.shell.xmission.com!not-for-mail
From: legalize+jeeves-at-mail.xmission.com (Richard)
Newsgroups: comp.lang.c++
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Fri, 2 Dec 2016 22:06:06 +0000 (UTC)
Organization: multi-cellular, biological
Sender: legalize+jeeves-at-mail.xmission.com
Message-ID:
References:
Reply-To: (Richard) legalize+jeeves-at-mail.xmission.com
Injection-Date: Fri, 2 Dec 2016 22:06:06 +0000 (UTC)
Injection-Info: news.xmission.com; posting-host="shell.xmission.com:2607:fa18:0:beef::4";
logging-data="7845"; mail-complaints-to="abuse-at-xmission.com"
X-Reply-Etiquette: No copy by email, please
Mail-Copies-To: never
X-Newsreader: trn 4.0-test77 (Sep 1, 2010)
Originator: legalize-at-shell.xmission.com (Richard)
Xref: panix comp.lang.c++:1125737
[Please do not mail me a copy of your followup]
"Alf P. Steinbach" spake the secret code
thusly:
>[...] And also, to introduce the syntax to more people. :)
Yes. Gratuitous use of new syntax.
--
"The Direct3D Graphics Pipeline" free book
The Terminals Wiki
The Computer Graphics Museum
Legalize Adulthood! (my blog)
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
X-Received: by 10.36.123.194 with SMTP id q185mr185314itc.17.1480651962251;
Thu, 01 Dec 2016 20:12:42 -0800 (PST)
X-Received: by 10.157.60.235 with SMTP id t40mr2869028otf.0.1480651962072;
Thu, 01 Dec 2016 20:12:42 -0800 (PST)
Path: reader1.panix.com!reader2.panix.com!panix!bloom-beacon.mit.edu!bloom-beacon.mit.edu!168.235.88.217.MISMATCH!feeder.erje.net!2.us.feeder.erje.net!weretis.net!feeder6.news.weretis.net!news.glorb.com!p16no1055278qta.1!news-out.google.com!j8ni4000qtc.0!nntp.google.com!n6no1056695qtd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail
Newsgroups: comp.lang.c++
Date: Thu, 1 Dec 2016 20:12:41 -0800 (PST)
In-Reply-To:
Complaints-To: groups-abuse-at-google.com
Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=45.72.199.16; posting-account=3E3pbwoAAAAXIx5awOqPnLzD9t84gci2
NNTP-Posting-Host: 45.72.199.16
References:
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <38fa732e-e7ec-4e15-af08-a3eab7bfc66b-at-googlegroups.com>
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
From: Daniel
Injection-Date: Fri, 02 Dec 2016 04:12:42 +0000
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
Xref: panix comp.lang.c++:1125710
On Thursday, December 1, 2016 at 6:35:48 PM UTC-5, Alf P. Steinbach wrote:
>=20
> Dang, there was a good quote about consistency, I've forgotten it...
>=20
One of these?
=E2=80=9CA foolish consistency is the hobgoblin of little minds"
- Ralph Waldo Emerson
"Do I contradict myself? Very well, then I contradict myself, I am large, I=
contain multitudes."
- Walt Whitman
--------------5DBB2C766E4500A288914E29
Content-Type: message/rfc822;
name="Re: Tutorial on threaded binary tree part 1: simple unthreaded
tree.eml"
Content-Transfer-Encoding: 8bit
Content-Disposition: attachment;
filename*0="Re: Tutorial on threaded binary tree part 1: simple unthread";
filename*1="ed tree.eml"
Path: reader1.panix.com!reader2.panix.com!panix!goblin3!goblin1!goblin.stu.neva.ru!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: "Alf P. Steinbach"
Newsgroups: comp.lang.c++
Subject: Re: Tutorial on threaded binary tree part 1: simple unthreaded tree
Date: Fri, 2 Dec 2016 05:53:09 +0100
Organization: A noiseless patient Spider
Message-ID:
References:
<38fa732e-e7ec-4e15-af08-a3eab7bfc66b-at-googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Fri, 2 Dec 2016 04:54:49 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="10898c670d21c99e9cd59e8600373116";
logging-data="25660"; mail-complaints-to="abuse-at-eternal-september.org"; posting-account="U2FsdGVkX18FxAYQP2L4ybZv36QACtlV"
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101
Thunderbird/45.5.1
In-Reply-To: <38fa732e-e7ec-4e15-af08-a3eab7bfc66b-at-googlegroups.com>
Cancel-Lock: sha1:Vw0k3tlUwxXx5vV9GXWh+oiYwME=
Xref: panix comp.lang.c++:1125711
On 02.12.2016 05:12, Daniel wrote:
> On Thursday, December 1, 2016 at 6:35:48 PM UTC-5, Alf P. Steinbach wrote:
>>
>> Dang, there was a good quote about consistency, I've forgotten it...
>>
> One of these?
>
> “A foolish consistency is the hobgoblin of little minds"
>
> - Ralph Waldo Emerson
>
> "Do I contradict myself? Very well, then I contradict myself, I am large, I contain multitudes."
>
> - Walt Whitman
Yep. Thanks!
Cheers!,
- Alf
--------------5DBB2C766E4500A288914E29
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
Learn mailing list
Learn-at-nylxs.com
http://lists.mrbrklyn.com/mailman/listinfo/learn
--------------5DBB2C766E4500A288914E29--
|
|
