Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c++ > #46996 > unrolled thread

Tutorial on threaded binary tree part 1: simple unthreaded tree

Back to article view | Back to comp.lang.c++

Contents

  Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-01 10:32 +0100
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-01 20:23 +0000
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-01 16:54 -0500
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 03:15 +0100
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree leigh.v.johnston@googlemail.com - 2016-12-02 05:45 -0800
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Öö Tiib <ootiib@hot.ee> - 2016-12-02 08:30 -0800
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 15:32 +0000
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 16:15 +0000
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-02 15:55 +0000
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 00:58 +0100
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Melzzzzz <mel@zzzzz.com> - 2016-12-03 01:51 +0100
              Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 03:04 +0100
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 01:54 +0000
              Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 02:07 +0000
                Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-03 03:11 +0100
                  Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-03 02:17 +0000
                    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Öö Tiib <ootiib@hot.ee> - 2016-12-03 01:31 -0800
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:39 -0500
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-01 21:34 +0000
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk> - 2016-12-01 22:23 +0000
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 00:32 +0100
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-01 23:57 +0000
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 01:14 +0100
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree legalize+jeeves@mail.xmission.com (Richard) - 2016-12-02 22:06 +0000
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Daniel <danielaparker@gmail.com> - 2016-12-01 20:12 -0800
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> - 2016-12-02 05:53 +0100
      Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:45 -0500
        Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Ian Collins <ian-news@hotmail.com> - 2016-12-03 11:48 +1300
          Re: Tutorial on threaded binary tree part 1: simple unthreaded tree ruben safir <ruben@mrbrklyn.com> - 2016-12-02 17:49 -0500
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Ian Collins <ian-news@hotmail.com> - 2016-12-03 11:52 +1300
            Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Jerry Stuckle <jstucklex@attglobal.net> - 2016-12-02 19:44 -0500
    Re: Tutorial on threaded binary tree part 1: simple unthreaded tree Tim Rentsch <txr@alumni.caltech.edu> - 2016-12-09 22:05 -0800

Page 1 of 2  [1] 2  Next page →

#46996 — Tutorial on threaded binary tree part 1: simple unthreaded tree

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 <iostream>
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

[toc] | [next] | [standalone]

#47002

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 <iostream>
> 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

[toc] | [prev] | [next] | [standalone]

#47004

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@attglobal.net
==================

[toc] | [prev] | [next] | [standalone]

#47009

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

[toc] | [prev] | [next] | [standalone]

#47012

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

[toc] | [prev] | [next] | [standalone]

#47016

On Friday, 2 December 2016 15:46:18 UTC+2, leigh.v....@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.

[toc] | [prev] | [next] | [standalone]

#47013

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

[toc] | [prev] | [next] | [standalone]

#47015

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

[toc] | [prev] | [next] | [standalone]

#47014

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

[toc] | [prev] | [next] | [standalone]

#47048

On 02.12.2016 16:55, Mr Flibble wrote:
>>
[snip]
>> 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.

Hm, the above two sentences contradict each other. :)

The last sentence even contradicts itself.

As you note in the last part of that sentence, with a multimap multiple 
occurrences of the same key need to be distinguished, because they can 
be associated with different values.

Therefore, contrary to the assertion in the first part of that sentence, 
they do not naturally have “identical structures”. There are 
interpretations where this assertion holds, but they are meaningless. 
For example, one structure can be implemented in terms of the other, 
they can both be implemented in terms of arrays, and so on etc.; there 
is no meaning in that, and it does not relate to the bullet points.

With a multiset you only need a count of each value.

With a multimap you need to distinguish each value, even identical ones, 
because they can have different associated information.


Cheers & hth.,

- Alf

[toc] | [prev] | [next] | [standalone]

#47053

On Sat, 3 Dec 2016 00:58:19 +0100
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> wrote:

> On 02.12.2016 16:55, Mr Flibble wrote:
> >>  
> [snip]
> >> 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.  
> 
> Hm, the above two sentences contradict each other. :)
> 
> The last sentence even contradicts itself.
> 
> As you note in the last part of that sentence, with a multimap
> multiple occurrences of the same key need to be distinguished,
> because they can be associated with different values.

You are wrong. Value is completely non essential for that data
structure. With that said, I can't figure out purpose of multiset at
all... but generally you are right. multiset does not needs to store
actual nodes. count and key are enough.




-- 
press any key to continue or any other to quit

[toc] | [prev] | [next] | [standalone]

#47057

On 03.12.2016 01:51, Melzzzzz wrote:
> On Sat, 3 Dec 2016 00:58:19 +0100
> "Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com> wrote:
>
>> On 02.12.2016 16:55, Mr Flibble wrote:
>>>>
>> [snip]
>>>> 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.
>>
>> Hm, the above two sentences contradict each other. :)
>>
>> The last sentence even contradicts itself.
>>
>> As you note in the last part of that sentence, with a multimap
>> multiple occurrences of the same key need to be distinguished,
>> because they can be associated with different values.
>
> You are wrong. Value is completely non essential for that data
> structure.

A map data structure is a collection of (key, value) pairs. For example, 
the keys can be student id's, and the values can be the grades they have 
in some course. Or the keys can be main country codes, and the values 
codes for the languages spoken there, like ("NO", "NB") and ("NO", "NN").

The “multi” in /multimap/ means that the same key can occur twice or 
more, then generally with different associated values for each 
occurrence, as in the country/language code example.

For more details see <url: 
http://en.cppreference.com/w/cpp/container/multimap>.


> With that said, I can't figure out purpose of multiset at
> all...

:) See above.


> but generally you are right. multiset does not needs to store
> actual nodes. count and key are enough.

Well, that depends.

I was referring to concepts and common usage.

However, `std::multiset`, as opposed to the mathematical idea of 
multiset, guarantees that the order of the keys that compare equivalent 
is the order of insertion and does not change, i.e. it provides a stable 
sort. To make sense of that  --  the /order/ of equivalent key values, 
what?  --  you need to know that `std::multiset` can work with a custom 
comparison function that can use only part of the value stored, as key. 
And for this case Mr. Flibble would be right, if that was what he meant. 
But then I think he would have mentioned it.

A count is not sufficient for the general functionality of `std::multiset`.

But a tree with just a count for each value, can implement a multiset 
(although not the full general `std::multiset` in the C++ standard 
library), and can not implement a multimap of any kind.


Cheers!,

- Alf

[toc] | [prev] | [next] | [standalone]

#47055

On 02/12/2016 23:58, Alf P. Steinbach wrote:
> On 02.12.2016 16:55, Mr Flibble wrote:
>>>
> [snip]
>>> 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.
>
> Hm, the above two sentences contradict each other. :)
>
> The last sentence even contradicts itself.
>
> As you note in the last part of that sentence, with a multimap multiple
> occurrences of the same key need to be distinguished, because they can
> be associated with different values.
>
> Therefore, contrary to the assertion in the first part of that sentence,
> they do not naturally have “identical structures”. There are
> interpretations where this assertion holds, but they are meaningless.
> For example, one structure can be implemented in terms of the other,
> they can both be implemented in terms of arrays, and so on etc.; there
> is no meaning in that, and it does not relate to the bullet points.
>
> With a multiset you only need a count of each value.
>
> With a multimap you need to distinguish each value, even identical ones,
> because they can have different associated information.

Wrong; again multiset and multimap are identical data structures both 
being a binary search tree with a node for each element irregardless of 
whether there are any duplicate keys.  The only difference between 
multiset and multimap is the key is part of a pair for multimap.

/Flibble

[toc] | [prev] | [next] | [standalone]

#47056

On 03/12/2016 01:54, Mr Flibble wrote:
> On 02/12/2016 23:58, Alf P. Steinbach wrote:
>> On 02.12.2016 16:55, Mr Flibble wrote:
>>>>
>> [snip]
>>>> 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.
>>
>> Hm, the above two sentences contradict each other. :)
>>
>> The last sentence even contradicts itself.
>>
>> As you note in the last part of that sentence, with a multimap multiple
>> occurrences of the same key need to be distinguished, because they can
>> be associated with different values.
>>
>> Therefore, contrary to the assertion in the first part of that sentence,
>> they do not naturally have “identical structures”. There are
>> interpretations where this assertion holds, but they are meaningless.
>> For example, one structure can be implemented in terms of the other,
>> they can both be implemented in terms of arrays, and so on etc.; there
>> is no meaning in that, and it does not relate to the bullet points.
>>
>> With a multiset you only need a count of each value.
>>
>> With a multimap you need to distinguish each value, even identical ones,
>> because they can have different associated information.
>
> Wrong; again multiset and multimap are identical data structures both
> being a binary search tree with a node for each element irregardless of
> whether there are any duplicate keys.  The only difference between
> multiset and multimap is the key is part of a pair for multimap.

Basically for a std::multiset the key_type is ALSO the value_type; if 
the multiset has 10 equivalent keys it must have 10 equivalent values 
(elements) i.e. NOT a single value (element) with a count of 10.  Keys 
that are equivalent do not have to be identical (comparable with == 
rather than <) and indeed can be complex objects with mutable state that 
does not contribute to order.

I am surprised Alf that someone with your experience doesn't know how 
std::multiset works or how it needs to be implemented.

/Flibble

[toc] | [prev] | [next] | [standalone]

#47058

On 03.12.2016 03:07, Mr Flibble wrote:
>
> I am surprised Alf that someone with your experience doesn't know how
> std::multiset works or how it needs to be implemented.

Oh, thanks for compliment. :)

But I wasn't referring to `std::multiset` specifically: I wasn't 
considering what data structure you need to implement `std::multiset`.

After listing three possibilities I noted that with the middle one, with 
(only) a count for each value, the most you can use that tree for, or at 
least the natural application, is /a multiset/.

That's general, programming language-independent terminology.


Cheers & hth.,

- Alf

[toc] | [prev] | [next] | [standalone]

#47060

On 03/12/2016 02:11, Alf P. Steinbach wrote:
> On 03.12.2016 03:07, Mr Flibble wrote:
>>
>> I am surprised Alf that someone with your experience doesn't know how
>> std::multiset works or how it needs to be implemented.
>
> Oh, thanks for compliment. :)
>
> But I wasn't referring to `std::multiset` specifically: I wasn't
> considering what data structure you need to implement `std::multiset`.
>
> After listing three possibilities I noted that with the middle one, with
> (only) a count for each value, the most you can use that tree for, or at
> least the natural application, is /a multiset/.
>
> That's general, programming language-independent terminology.

This is a C++ newsgroup not a mathematics newsgroup so if someone uses 
the terms "multiset" and "multimap" it is a fair assumption that they 
are actually referring to the C++ Standard Library containers rather 
than the mathematical concepts: you should have been more clear about 
what you meant by providing appropriate qualifications.

/Flibble

[toc] | [prev] | [next] | [standalone]

#47067

On Saturday, 3 December 2016 04:17:57 UTC+2, Mr Flibble  wrote:
> On 03/12/2016 02:11, Alf P. Steinbach wrote:
> > On 03.12.2016 03:07, Mr Flibble wrote:
> >>
> >> I am surprised Alf that someone with your experience doesn't know how
> >> std::multiset works or how it needs to be implemented.
> >
> > Oh, thanks for compliment. :)
> >
> > But I wasn't referring to `std::multiset` specifically: I wasn't
> > considering what data structure you need to implement `std::multiset`.
> >
> > After listing three possibilities I noted that with the middle one, with
> > (only) a count for each value, the most you can use that tree for, or at
> > least the natural application, is /a multiset/.
> >
> > That's general, programming language-independent terminology.
> 
> This is a C++ newsgroup not a mathematics newsgroup so if someone uses 
> the terms "multiset" and "multimap" it is a fair assumption that they 
> are actually referring to the C++ Standard Library containers rather 
> than the mathematical concepts: you should have been more clear about 
> what you meant by providing appropriate qualifications.

Thanks guys for interesting sub-thread about different ways how to
organize the bucket of values that compare equal in a tree. Slight 
miscommunication is unfortunately inevitable since it is impossible
to be precise in human language without becoming unreadable. 

[toc] | [prev] | [next] | [standalone]

#47039

On 12/01/2016 03:23 PM, Mr Flibble wrote:
>> [/code]
> 
> Without balancing your tree is as good as useless; your post was totally
> pointless.

not true

[toc] | [prev] | [next] | [standalone]

#47003

[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, <https://en.wikiquote.org/wiki/Albert_Einstein#1920s>)

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 <http://tinyurl.com/d3d-pipeline>
            The Terminals Wiki <http://terminals-wiki.org>
     The Computer Graphics Museum <http://computergraphicsmuseum.org>
  Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com>

[toc] | [prev] | [next] | [standalone]

#47005

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, <https://en.wikiquote.org/wiki/Albert_Einstein#1920s>)
>
> 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

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.c++

csiph-web