Sunday, August 2, 2015

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

Paul <pepstein5@gmail.com>: Aug 02 02:46AM -0700

The below code was copied from a book. Is there any reason to use lists instead of using a vector throughout? Also, are there any other issues with the code?
 
Thanks a lot,
 
Paul
 
 
#include <stdio.h>
#include <list>
#include <vector>
 
using namespace std;
 
struct TreeNode
{
int m_nValue;
std::vector<TreeNode*> m_vChildren;
};
 
bool GetNodePath(TreeNode* pRoot, TreeNode* pNode, list<TreeNode*>& path)
{
if(pRoot == pNode)
return true;
 
path.push_back(pRoot);
 
bool found = false;
 
vector<TreeNode*>::iterator i = pRoot->m_vChildren.begin();
while(!found && i < pRoot->m_vChildren.end())
{
found = GetNodePath(*i, pNode, path);
++i;
}
 
if(!found)
path.pop_back();
 
return found;
}
 
TreeNode* GetLastCommonNode
(
const list<TreeNode*>& path1,
const list<TreeNode*>& path2
)
{
list<TreeNode*>::const_iterator iterator1 = path1.begin();
list<TreeNode*>::const_iterator iterator2 = path2.begin();
 
TreeNode* pLast = NULL;
 
while(iterator1 != path1.end() && iterator2 != path2.end())
{
if(*iterator1 == *iterator2)
pLast = *iterator1;
 
iterator1++;
iterator2++;
}
 
return pLast;
}
 
TreeNode* GetLastCommonParent(TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2)
{
if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
 
list<TreeNode*> path1;
GetNodePath(pRoot, pNode1, path1);
 
list<TreeNode*> path2;
GetNodePath(pRoot, pNode2, path2);
 
return GetLastCommonNode(path1, path2);
}
 
// ==================== Code for Trees ====================
TreeNode* CreateTreeNode(int value)
{
TreeNode* pNode = new TreeNode();
pNode->m_nValue = value;
 
return pNode;
}
 
void ConnectTreeNodes(TreeNode* pParent, TreeNode* pChild)
{
if(pParent != NULL)
{
pParent->m_vChildren.push_back(pChild);
}
}
 
void PrintTreeNode(TreeNode* pNode)
{
if(pNode != NULL)
{
printf("value of this node is: %d.\n", pNode->m_nValue);
 
printf("its children is as the following:\n");
std::vector<TreeNode*>::iterator i = pNode->m_vChildren.begin();
while(i < pNode->m_vChildren.end())
{
if(*i != NULL)
printf("%d\t", (*i)->m_nValue);
}
 
printf("\n");
}
else
{
printf("this node is null.\n");
}
 
printf("\n");
}
 
void PrintTree(TreeNode* pRoot)
{
PrintTreeNode(pRoot);
 
if(pRoot != NULL)
{
std::vector<TreeNode*>::iterator i = pRoot->m_vChildren.begin();
while(i < pRoot->m_vChildren.end())
{
PrintTree(*i);
++i;
}
}
}
 
void DestroyTree(TreeNode* pRoot)
{
if(pRoot != NULL)
{
std::vector<TreeNode*>::iterator i = pRoot->m_vChildren.begin();
while(i < pRoot->m_vChildren.end())
{
DestroyTree(*i);
++i;
}
 
delete pRoot;
}
}
 
// ==================== Test Code ====================
 
void Test(char* testName, TreeNode* pRoot, TreeNode* pNode1, TreeNode* pNode2, TreeNode* pExpected)
{
if(testName != NULL)
printf("%s begins: \n", testName);
 
TreeNode* pResult = GetLastCommonParent(pRoot, pNode1, pNode2);
 
if((pExpected == NULL && pResult == NULL) ||
(pExpected != NULL && pResult != NULL && pResult->m_nValue == pExpected->m_nValue))
printf("Passed.\n");
else
printf("Failed.\n");
}
 
// 1
// / \
// 2 3
// / \
// 4 5
// / \ / | \
// 6 7 8 9 10
void Test1()
{
TreeNode* pNode1 = CreateTreeNode(1);
TreeNode* pNode2 = CreateTreeNode(2);
TreeNode* pNode3 = CreateTreeNode(3);
TreeNode* pNode4 = CreateTreeNode(4);
TreeNode* pNode5 = CreateTreeNode(5);
TreeNode* pNode6 = CreateTreeNode(6);
TreeNode* pNode7 = CreateTreeNode(7);
TreeNode* pNode8 = CreateTreeNode(8);
TreeNode* pNode9 = CreateTreeNode(9);
TreeNode* pNode10 = CreateTreeNode(10);
 
ConnectTreeNodes(pNode1, pNode2);
ConnectTreeNodes(pNode1, pNode3);
 
ConnectTreeNodes(pNode2, pNode4);
ConnectTreeNodes(pNode2, pNode5);
 
ConnectTreeNodes(pNode4, pNode6);
ConnectTreeNodes(pNode4, pNode7);
 
ConnectTreeNodes(pNode5, pNode8);
ConnectTreeNodes(pNode5, pNode9);
ConnectTreeNodes(pNode5, pNode10);
 
Test("Test1", pNode1, pNode6, pNode8, pNode2);
 
DestroyTree(pNode1);
}
 
// 1
// / \
// 2 3
// / \
// 4 5
// / \ / | \
// 6 7 8 9 10
void Test2()
{
TreeNode* pNode1 = CreateTreeNode(1);
TreeNode* pNode2 = CreateTreeNode(2);
TreeNode* pNode3 = CreateTreeNode(3);
TreeNode* pNode4 = CreateTreeNode(4);
TreeNode* pNode5 = CreateTreeNode(5);
TreeNode* pNode6 = CreateTreeNode(6);
TreeNode* pNode7 = CreateTreeNode(7);
TreeNode* pNode8 = CreateTreeNode(8);
TreeNode* pNode9 = CreateTreeNode(9);
TreeNode* pNode10 = CreateTreeNode(10);
 
ConnectTreeNodes(pNode1, pNode2);
ConnectTreeNodes(pNode1, pNode3);
 
ConnectTreeNodes(pNode2, pNode4);
ConnectTreeNodes(pNode2, pNode5);
 
ConnectTreeNodes(pNode4, pNode6);
ConnectTreeNodes(pNode4, pNode7);
 
ConnectTreeNodes(pNode5, pNode8);
ConnectTreeNodes(pNode5, pNode9);
ConnectTreeNodes(pNode5, pNode10);
 
Test("Test2", pNode1, pNode7, pNode3, pNode1);
 
DestroyTree(pNode1);
}
 
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
void Test3()
{
TreeNode* pNode1 = CreateTreeNode(1);
TreeNode* pNode2 = CreateTreeNode(2);
TreeNode* pNode3 = CreateTreeNode(3);
TreeNode* pNode4 = CreateTreeNode(4);
TreeNode* pNode5 = CreateTreeNode(5);
 
ConnectTreeNodes(pNode1, pNode2);
ConnectTreeNodes(pNode2, pNode3);
ConnectTreeNodes(pNode3, pNode4);
ConnectTreeNodes(pNode4, pNode5);
 
Test("Test3", pNode1, pNode5, pNode4, pNode3);
DestroyTree(pNode1);
}
 
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
void Test4()
{
TreeNode* pNode1 = CreateTreeNode(1);
TreeNode* pNode2 = CreateTreeNode(2);
TreeNode* pNode3 = CreateTreeNode(3);
TreeNode* pNode4 = CreateTreeNode(4);
TreeNode* pNode5 = CreateTreeNode(5);
 
ConnectTreeNodes(pNode1, pNode2);
ConnectTreeNodes(pNode2, pNode3);
ConnectTreeNodes(pNode3, pNode4);
ConnectTreeNodes(pNode4, pNode5);
 
// pNode6 is not in the tree
TreeNode* pNode6 = CreateTreeNode(6);
 
Test("Test4", pNode1, pNode5, pNode6, NULL);
DestroyTree(pNode1);
DestroyTree(pNode6);
}
 
// Empty Tree
void Test5()
{
Test("Test5", NULL, NULL, NULL, NULL);
}
 
// 1
// /
// 2
// /
// 3
// /
// 4
// /
// 5
void Test6()
{
TreeNode* pNode1 = CreateTreeNode(1);
TreeNode* pNode2 = CreateTreeNode(2);
TreeNode* pNode3 = CreateTreeNode(3);
TreeNode* pNode4 = CreateTreeNode(4);
TreeNode* pNode5 = CreateTreeNode(5);
 
ConnectTreeNodes(pNode1, pNode2);
ConnectTreeNodes(pNode2, pNode3);
ConnectTreeNodes(pNode3, pNode4);
ConnectTreeNodes(pNode4, pNode5);
 
Test("Test6", pNode1, pNode5, pNode1, NULL);
DestroyTree(pNode1);
}
 
int main(int argc, char* argv[])
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
 
return 0;
}
"Öö Tiib" <ootiib@hot.ee>: Aug 02 03:19PM -0700

On Sunday, 2 August 2015 12:47:21 UTC+3, Paul wrote:
> The below code was copied from a book.
 
What book?
 
> Is there any reason to use lists instead of using a vector throughout?
 
The whole 'GetNodePath' itself searching all of tree elements and
pushing and popping 'std::list' for each element visited is just *awful*
performance sink. A tree with million of leaves will make half a million
pushes and pops just to find a path from trunk to particular branch.
 
> Also, are there any other issues with the code?
 
Naive Design.
The vector of pointers in nodes is clearly suboptimal for tree.
Vector itself is 3 pointers pointing at a dynamic array of pointers.
Result is a tree navigable only towards leafs. Wasted.
If to think of it a bit then 4 pointers in a node should be enough to
make a tree navigable in whatever direction thinkable. For example one
pointer towards leaves, one pointer towards trunk and 2 for siblings.
Other schemes are possible ... but it is hard to think how more than
4 pointers per node are needed for navigating in a tree.
 
Inconvenient Interface.
It feels like hacking with pointers of nodes, not building a tree.
 
Inconsistent style of code.
Usage of 'std::list' and 'std::vector' in mix with 'vector' and 'list'.
Even usage of braces of 'if' are inconsistent.
 
Perhaps you need a better book.
 
If you need a tree example written in C++ then take Adobe Forest:
http://stlab.adobe.com/classadobe_1_1forest.html
Ready made generic tree. Fairly decent implementation.
It beats the posted code anytime for anything. Its interface is similar
enough to interface of standard library containers.
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Aug 02 02:19PM +0200

On 02-Aug-15 11:58 AM, Stefan Ram wrote:
> in the declaration of the fields with braces but not
> with parentheses?
 
> Does it have the same semantics as the MIL?
 
Essentially.
 
 
> Which of the two styles is better?
 
For the case of a single constructor, I'd say it's mostly a matter of
personal preference.
 
With multiple constructors repeating the initializers in every
constructor can be verbose, unclear and problematic for maintainance, as
with any kind of redundant specification.
 
However, constructor delegation, or a base or data member, might be an
alternative.
 
 
Cheers & hth.,
 
- Alf
 
--
Using Thunderbird as Usenet client, Eternal September as NNTP server.
Victor Bazarov <v.bazarov@comcast.invalid>: Aug 02 08:29AM -0400

On 8/2/2015 5:58 AM, Stefan Ram wrote:
 
> Is there a rationale for allowing the initialization
> in the declaration of the fields with braces but not
> with parentheses?
 
I think the idea is to avoid the confusion between
 
int a();
 
and
 
int a{};
 
(and I trust you do know the difference).
 
Yes, in the case of 'rng' or 'uni', no problem exists. But to make it
consistent, I think, it is worth the imposition of a limitation.
 
> Does it have the same semantics as the MIL?
 
Yes, except you probably can't use 'this' pointer. Why can't you look
it up?
 
> Which of the two styles is better?
 
I prefer the initialization list, all in one place, easy to follow,
dependencies are neatly stacked... Not to mention that to make use of
arguments passed to the constructor you need to use that, and it forms a
good habit.
 
A combination of the two is probably recommended. I imagine that all
members that are initialized with the same value (or expression) don't
need to be repeated in all the initialization lists, and instead can use
their declarations with initializers.
 
V
--
I do not respond to top-posted replies, please don't ask
Paul <pepstein5@gmail.com>: Aug 02 05:59AM -0700

On Sunday, August 2, 2015 at 1:30:17 PM UTC+1, Victor Bazarov wrote:
...
 
> int a();
 
> and
 
> int a{};
 
...
 
I can guess the difference but I'm far from sure so I'd like some feedback. int a(); declares a function a which takes a void and returns an int (I am quite confident of this one).
 
int a{}; value initialises a and is therefore equivalent to int a = 0; (I'm not sure on this one.)
 
Paul
ram@zedat.fu-berlin.de (Stefan Ram): Aug 02 09:58AM

The following program uses a member-initialization list (MIL):
 
#include <iostream>
#include <ostream>
#include <random>
 
struct circle
{ ::std::random_device rd;
::std::mt19937 rng;
::std::uniform_int_distribution< int >uni;
circle(): rd(), rng( rd() ), uni( 0, 11 ) {}
int rnd(){ return uni( rng ); }};
 
int main ()
{ circle circle;
for( int i = 0; i < 9; ++i )
::std::cout << circle.rnd() << '\n'; }
 
The following programm does not use a MIL:
 
#include <iostream>
#include <ostream>
#include <random>
 
struct circle
{ ::std::random_device rd{};
::std::mt19937 rng{ rd() };
::std::uniform_int_distribution< int >uni{ 0, 11 };
 
int rnd(){ return uni( rng ); }};
 
int main ()
{ circle circle;
for( int i = 0; i < 9; ++i )
::std::cout << circle.rnd() << '\n'; }
 
Is there a rationale for allowing the initialization
in the declaration of the fields with braces but not
with parentheses?
 
Does it have the same semantics as the MIL?
 
Which of the two styles is better?
Bo Persson <bop@gmb.dk>: Aug 02 10:43AM +0200

On 2015-08-02 00:23, Alf P. Steinbach wrote:
> tricks for `std::string` and `std::ostringstream`, but for that, the
> details elude me completely -- possibly something to do with `append`
> for strings?
 
Probably with streams, where you couldn't use tempories with the free
operator<<.
 
std::ostringstream() << x;
 
would fail, but
 
std::ostringstream().flush() << x;
 
would compile, as the flush member function would return an ostream&
that << x could use.
 
 
Has of course been fixed with an rvalue overload in later C++ versions.
 
 
Bo Persson
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)