Friday, June 16, 2017

Digest for comp.lang.c++@googlegroups.com - 16 updates in 4 topics

JiiPee <no@notvalid.com>: Jun 16 08:38PM +0100

On 15/06/2017 15:43, Öö Tiib wrote:
> his career. Player may be interested how well he did in games of the
> past. But if the points are in player then those will be overwritten by
> next game.
 
I guess you mean that better to have points outside the Player class. I
agree that might be a perfect way, but then that would increase the
complexity of the code quite a lot (as I would have to create a
structure to hold the points). thats why I put it there. Other reason
was that because I cannot see the Player being used in this program for
any other purposes than 1) playing a game 2) modifying its data. So I
chose in this case to just put it there to keep it simple as I cannot
see player used in any other ways in this program.
 
My idea was here that the Player contains all the information for the
player, game points being one.
 
If I use the player in more complex way then maybe better to separate in
the future.
 
It nicely walks there "for free" with the player - dont need to worry
that a player gets another players/wrong points.
 
> Interacting with game technically can result that some subset of bits
> of player change but it is not responsibility of game to deal with those
> bits.
 
Where would it go? As currently I have only 2 classes really: Game,
where the whole game is run and Player.
In main I create game-instance and thats it. Everything runs there.
Thats why it also modifies player.
Game means: the game is running. Its like a video game: when you swich
on the video game we can say that the game is running, right? or you
mean that the game only starts when the first move is done? evertyghing
before that does not belong to game (like adding player to the
game/modifying players data etc)?
JiiPee <no@notvalid.com>: Jun 16 08:43PM +0100

On 15/06/2017 15:43, Öö Tiib wrote:
> But if the points are in player then those will be overwritten by
> next game.
 
 
it really should be called:
 
int currentPointsInGame;
 
then there is no question what it is used for. that would solve that
confusion
JiiPee <no@notvalid.com>: Jun 16 09:08PM +0100

On 14/06/2017 08:43, Öö Tiib wrote:
> On such case you could make it so that "player" must be always in
> something "game-like". For example if it leaves some real "chess game"
> then it is some "idle-list" or in "lobby" that follows interface rules of "game".
 
 
Yes I agree better structure would be to separate players info (name,
picture, address etc) from the game data. The reason I started doing
this is because at that time I was "sure" that this program will never
do lobby-kind of things, its only a program running this particular
simple game. So I was kind of thinking keeping it "simple" rather than
creating many different classes etc.
 
 
But its true that if in the future I want to add more games and use the
same base-structure i have here, then I would need to modify a bit that
Player structure to be more general. Although that is not difficult to
do as its a simple game.
 
 
I should be thinking ahead even now (even though the game is very simple)?
Bilal <bilalcisco@googlemail.com>: Jun 16 12:12AM -0700

Hi everyone,
I am a bit confused about using recursion with linked list. Below is the code that I ran which works perfectly (as shown in output) but somehow is confusing for me.
 
Let's say we have a list {1,2,3,4}. When RecursiveReverse(&rest) is called for 1, in Line 9 rest is set to 2. similarly when RecursiveReverse(&rest) is called for 2, in Line 9 rest is set to 3. Then why in Line 25 rest is always 4 also shown in the output? I used printf statements to trace the code/recursion operation.
 
Please help me figure it out. thanks.
-Bilal
 
 
C++ Code:
----------------------------------------------
1 RecursiveReverse(Node **headRef)
2 {
3 // Base case
4 if(*headRef == NULL)
5 return;
6
7 Node *first = *headRef;
8
9 Node *rest = (*headRef)->next;
10
11 if(rest == NULL)
12 {
13 printf("-------------------------------\n");
14 return;
15 }
16 printf("1st CALL: rest is %d \n",rest->data);
17
18 recursiveReverse(&rest);
19
20 first->next->next = first;
21
22 first->next = NULL;
23 printf("2nd CALL: rest is %d \n",rest->data);
24 // rest always point to the last
25 *headRef = rest;
26 }
----------------------------------------------
Output:
1st CALL: rest is 2
1st CALL: rest is 3
1st CALL: rest is 4
--------------------
2nd CALL: rest is 4
2nd CALL: rest is 4 //How? Shouldn't be 3?
2nd CALL: rest is 4 //How? Shouldn't be 2?
Ben Bacarisse <ben.usenet@bsb.me.uk>: Jun 16 09:32AM +0100

> called for 1, in Line 9 rest is set to 2. similarly when
> RecursiveReverse(&rest) is called for 2, in Line 9 rest is set to
> 3. Then why in Line 25 rest is always 4 also shown in the output?
 
Because rest changes as a result of the call on line 18 -- what it was
on line 9 (and at the printf call on line 16) is not the same as what it
has on line 23.
 
> C++ Code:
 
Not quute:
 
> 16 printf("1st CALL: rest is %d \n",rest->data);
> 17
> 18 recursiveReverse(&rest);
 
Is this supposed to be RecursiveReverse? Make sure you cut and paste
code so readers know that a looking at the real thing!
 
> 24 // rest always point to the last
> 25 *headRef = rest;
> 26 }
 
<snip>
--
Ben.
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Jun 16 10:45AM +0200

On 16-Jun-17 9:12 AM, Bilal wrote:
> 2nd CALL: rest is 4
> 2nd CALL: rest is 4 //How? Shouldn't be 3?
> 2nd CALL: rest is 4 //How? Shouldn't be 2?
 
Well, to understand this code I first cleaned it up and placed it in a
complete little program:
 
 
-----------------------------------------------------------------------
struct Node
{
int value;
Node* next;
};
 
void recursive_reverse( Node **head_ref )
{
if( *head_ref == nullptr ) { return; }
 
Node* first = *head_ref;
Node* rest = (*head_ref)->next;
 
if( rest == nullptr ) { return; }
 
recursive_reverse( &rest );
 
first->next->next = first;
first->next = nullptr;
*head_ref = rest;
}
 
#include <iostream>
using namespace std;
 
void display( Node const* const p_list )
{
for( auto p = p_list; p; p = p->next )
{
cout << p->value << ' ';
}
cout << endl;
}
auto main() -> int
{
Node* list = new Node{ 1 };
Node* p = list;
for( int i = 2; i <= 4; ++i ) { p->next = new Node{ i }; p = p->next; }
display( list );
recursive_reverse( &list );
display( list );
}
-----------------------------------------------------------------------
 
 
This proved that the code worked (which I was a bit skeptical about), so
I looked closer at it.
 
Now a key feature that makes it harder than necessary to understand is
that it takes a pointer to pointer argument in order to /modify/ that
original first-node pointer.
 
Instead just make a function that returns the new pointer to first node.
That's in general a much better way to communicate a value back to the
caller. Hm, I need a function result, what should I use? Aha! A C++
function result!
 
Another complicating feature is that it returns for invalid argument, in
every recursive call, as if that could happen.
 
Instead it should just, if that's at all deemed necessary, `assert` that
the argument is valid.
 
 
-----------------------------------------------------------------------
struct Node
{
int value;
Node* next;
};
 
namespace impl {
 
// Returns pointer to first node in the reversed list:
auto recursively_reversed( Node* const first )
-> Node*
{
Node* const rest = first->next;
if( rest == nullptr ) { return first; }
Node* const new_first = recursively_reversed( rest );
 
first->next->next = first;
first->next = nullptr;
 
return new_first;
}
 
} // namespace impl
 
auto reversed( Node* const list )
-> Node*
{
if( list == nullptr)
{
return nullptr;
}
return impl::recursively_reversed( list );
}
 
#include <iostream>
using namespace std;
 
void display( Node const* const p_list )
{
for( auto p = p_list; p; p = p->next )
{
cout << p->value << ' ';
}
cout << endl;
}
auto main() -> int
{
Node* list = new Node{ 1 };
Node* p = list;
for( int i = 2; i <= 4; ++i ) { p->next = new Node{ i }; p = p->next; }
display( list );
list = reversed( list );
display( list );
}
-----------------------------------------------------------------------
 
I'm not sure of a pattern name for the kind of restructuring I did here.
 
I guess it's something to do with delegation and single responsibility.
 
Anyway, in this tidied up code, after impl::recursively_reversed has
called itself to reverse the rest of the list, it changes the next
pointer in the previously second node, now the last node in the reversed
rest of the list, to point to the former first node, which now is last.
 
That's it, essentially.
 
Tip: where you really need an in/out-argument, use a C++ reference
rather than e.g. pointer to pointer.
 
 
Cheers & hth.,
 
- Alf
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Jun 16 04:26PM +0100

On 16/06/2017 09:45, Alf P. Steinbach wrote:
> using namespace std;
 
Egregious.
 
> auto main() -> int
 
Egregious OCD.
 
/Flibble
Tim Rentsch <txr@alumni.caltech.edu>: Jun 16 08:42AM -0700


> I am a bit confused about using recursion with linked list. Below
> is the code [...]
 
The function you wrote has a recursive call "in the middle" of
the function body. That is, the function body does more work
after the recursive call is done, rather than just returning the
result of a recursive call (which would need to be a different
call).
 
In cases like this, where the depth of recursion might be very
large (what if we have a list with 1,000,000 elements in it?),
it's important to write such functions so any recursive call is a
tail call (usually called tail recursion). Often such function
bodies will be optimized during compilation so recursive calls
are turned into loops rather than calls. Here is a short example
of how to implement list reversal using tail recursion:
 
typedef struct list_node *List;
 
struct list_node {
List next;
char value;
};
 
static List
reverse_onto( List s, List r ){
List t;
return s ? t = s->next, s->next = r, reverse_onto( t, s ) : r;
}
 
void
reverse( List &s ){
s = reverse_onto( s, 0 );
}
 
Look at the '?' branch of the conditional expression, which is
taken when 's' is non-null. Notice how the last thing done in
this case, and the value returned from the function, is the
result of the recursive call to reverse_onto().
 
When 's' is null, the return value is just 'r', the list we
are reversing "onto".
 
Here is what reverse() compiles to under gcc -Os (minus some
lines that have unimportant assembly noise):
 
_Z7reverseRP9list_node:
movq (%rdi), %rax
xorl %edx, %edx
.L15:
testq %rax, %rax
je .L14
movq (%rax), %rcx
movq %rdx, (%rax)
movq %rax, %rdx
movq %rcx, %rax
jmp .L15
.L14:
movq %rdx, (%rdi)
ret
 
Using tail recursion has given us a nice compact loop to effect
list reversal.
 
Do you understand how the list reversal functions shown
above work, or is more explanation needed?
Jerry Stuckle <jstucklex@attglobal.net>: Jun 16 12:37PM -0400

On 6/16/2017 11:42 AM, Tim Rentsch wrote:
> list reversal.
 
> Do you understand how the list reversal functions shown
> above work, or is more explanation needed?
 
Whether it is head, middle or tail recursion makes little difference in
the amount of memory consumed. It does, however, make a difference in
the processing. Any work performed before the recursive call (tail
recursion) is done on the way down the recursion; any work performed
after the recursive call (head recursion) is done on the way back. The
result is whatever recursion is being performed is done in opposite order.
 
For instance, if recursing a linked list, tail recursion (performing
work before the recursion) will process the list from front to back.
Head recursion will process the list from back to front.
 
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Jun 16 07:04PM +0100

On Fri, 16 Jun 2017 12:37:50 -0400
 
> For instance, if recursing a linked list, tail recursion (performing
> work before the recursion) will process the list from front to back.
> Head recursion will process the list from back to front.
 
What you say is true but misses the point. Tail recursion, provided
there are no objects in local scope having a non-trivial destructor,
will be optimized into a goto with gcc and -O2 or -O3 optimization,
and apparently -Os also as demonstrated above. Non-tail recursion will
build up results on the stack for the purposes of post-rercursion
processing as you have mentioned, resulting in higher memory usage. With
enough recursion it will bust your stack. Where tail call elimination
is possible, it will not. In functional programming, tail call
recursion is normally described as "iterative", and non-tail recursion
as "recursive".
 
Chris
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Jun 16 07:09PM +0100

On Fri, 16 Jun 2017 19:04:32 +0100
> What you say is true but misses the point. Tail recursion, provided
^^^^
Except as regards your comments about memory usage.
 
Jerry Stuckle <jstucklex@attglobal.net>: Jun 16 03:07PM -0400

On 6/16/2017 2:04 PM, Chris Vine wrote:
> recursion is normally described as "iterative", and non-tail recursion
> as "recursive".
 
> Chris
 
Yes - PROVIDE THERE ARE NO OBJECT... Tail recursion itself does NOT mean
that the function can be optimized into a goto. There are many factors
involved.
 
And "iterative" is not the same as "recursive" - and has not been for
the last 40+ years. Even if the function is optimized to a goto it is
still considered recursive.
 
--
==================
Remove the "x" from my email address
Jerry Stuckle
jstucklex@attglobal.net
==================
Chris Vine <chris@cvine--nospam--.freeserve.co.uk>: Jun 16 08:39PM +0100

On Fri, 16 Jun 2017 15:07:24 -0400
> On 6/16/2017 2:04 PM, Chris Vine wrote:
[snip]
>> What you say is true but misses the point. Tail recursion, provided
^^^^
 
> Yes - PROVIDE THERE ARE NO OBJECT... Tail recursion itself does NOT
> mean that the function can be optimized into a goto. There are many
> factors involved.
 
You misunderstand, and there are no other factors involved, other than
the choice of optimization level. If there is an object in function
scope with a non-trivial destructor, in C++ the function call is not
in tail position: there is still a destructor to execute. If on the
other hand it is in tail position, gcc will optimize the function call
away.
 
There is no point in arguing about it in your usual style. You claimed
that there is "little difference" between tail calls and non-tail calls
as regards stack usage. With gcc and other modern compilers that is
wrong.
 
> And "iterative" is not the same as "recursive" - and has not been for
> the last 40+ years. Even if the function is optimized to a goto it is
> still considered recursive.
 
I prepended the words "in functional programming". You are talking out
of your ass, not for the first time.
Christiano <christiano@engineer.com>: Jun 16 04:41PM -0300

On 06/16/17 04:12, Bilal wrote:
> 2nd CALL: rest is 4
> 2nd CALL: rest is 4 //How? Shouldn't be 3?
> 2nd CALL: rest is 4 //How? Shouldn't be 2?
 
******************
INITIAL STATUS:
Stack:
[ head is 1 ]
Linked List:
1->2->3->4->NULL
******************
 
Calling function
RecursiveReverse(&head);
 
Debugging
Setting breakpoints to line 1 and line 26
 
RUN >>
 
PAUSE line 1 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is ?, rest is ?, position = line 1 ]
Linked List:
1->2->3->4->NULL
---------------------------------------------
 
RUN >>
 
PAUSE line 1 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 2, position = line 18 ]
#3 [ first is ?, rest is ?, position = line 1 ]
Linked List:
1->2->3->4->NULL
---------------------------------------------
 
RUN >>
 
PAUSE line 1 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 2, position = line 18 ]
#3 [ first is 2, rest is 3, position = line 18 ]
#4 [ first is ?, rest is ?, position = line 1 ]
Linked List:
1->2->3->4->NULL
---------------------------------------------
 
RUN >>
 
PAUSE line 1 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 2, position = line 18 ]
#3 [ first is 2, rest is 3, position = line 18 ]
#4 [ first is 3, rest is 4, position = line 18 ]
#5 [ first is ?, rest is ?, position = line 1 ]
Linked List:
1->2->3->4->NULL
---------------------------------------------
 
RUN >>
 
PAUSE line 26 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 2, position = line 18 ]
#3 [ first is 2, rest is 4, position = line 18 ]
#4 [ first is 3, rest is 4, position = line 26 ]
Linked List:
1->2->3<-4
`-->NULL
---------------------------------------------
 
RUN >>
 
PAUSE line 26 ||
---------------------------------------------
Stack:
#1 [ head is 1 ]
#2 [ first is 1, rest is 4, position = line 18 ]
#3 [ first is 2, rest is 4, position = line 26 ]
Linked List:
1->2<-3<-4
`-->NULL
---------------------------------------------
 
RUN >>
 
PAUSE line 26 ||
---------------------------------------------
Stack:
#1 [ head is 4 ]
#2 [ first is 1, rest is 4, position = line 26 ]
Linked List:
NULL<-1<-2<-3<-4
---------------------------------------------
 
******************
FINAL STATUS:
Stack:
#1 [ head is 4 ]
Linked List:
NULL<-1<-2<-3<-4
******************
Cholo Lennon <chololennon@hotmail.com>: Jun 16 11:45AM -0300

On 15/06/17 04:41, David Brown wrote:
 
> <https://en.wikipedia.org/wiki/Indent_style>
 
> If you want other people to use your code, it makes a lot of sense to
> use a formatting style that is popular with many people.
 
Not the same, but related, this was posted yesterday on comp.lang.python:
 
https://stackoverflow.blog/2017/06/15/developers-use-spaces-make-money-use-tabs/
 
 
--
Cholo Lennon
Bs.As.
ARG
Jorgen Grahn <grahn+nntp@snipabacken.se>: Jun 16 05:35AM

On Fri, 2017-06-09, Fred.Zwarts wrote:
 
>>I now encounter a problem with the wait_for function of the
>>condition_variable_any class. I was able to reduce it to a small program,
>>see below.
...
> --no-as-needed -lpthread
> in programs where the C++ multi-threading classes are used, unexpected
> behavior pops up.
 
Nice!
 
Could you please post an URL for the bug too, for the benefit of
others who encounter this problem?
 
(I'm not affected myself, but it's always good to "anchor" a
discussion like the one above in an official bug report.)
 
/Jorgen
 
--
// Jorgen Grahn <grahn@ Oo o. . .
\X/ snipabacken.se> O o .
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)