Iterating over templated list

Question

I am facing issue about declaring an iterator over a template list. Given below is the code.

#include<iostream>
#include<vector>
#include<list>
using namespace std;

template<typename T>
struct Node
{
    T data;
    Node<T> *left,*right;
};

template<typename T>
Node<T>* newNode(T data)
{
    Node<T>* root = new Node<T>();
    root->data = data;
    root->left = NULL;
    root->right = NULL;
    return root;
}

template<typename T>
void createMinBST(Node<T>*& root,T arr[],int start,int end)
{
    if(start>end)
        return;
    int mid = (start+end)/2;
    if (root == NULL)
    {
        root = newNode(arr[mid]);
        createMinBST(root->left, arr,start , mid-1);
        createMinBST(root->right, arr,mid+1 , end);
    }
}

template<typename T>
void levelLinkedLists(vector<list<Node<T>*> >& res,Node<T>* root)
{
    list<Node<T>*>li;
    li.push_back(root);
    res.push_back(li);
    int depth = 0;
    while(!res[depth].empty())
    {
        list<Node<T>*>l;
        typename list<Node<T>*>::iterator iter;
        for(iter = res[depth].begin();iter != res[depth].end(); iter++)
        {
            if(iter->left)
                l.push_back(*iter->left);
            if(iter->right)
                l.push_back(*iter->right);
        }
        depth++;
        res.push_back(l);
    }
}

template<typename T>
void printLevelLinkedLists(vector<list<Node<T>*> > res)
{
    typename vector<list<Node<T>*> >::iterator iter;
    for (iter = res.begin(); iter!= res.end();iter++)
    {
        list<Node<T>*>li = *iter;
        typename list<Node<T>*>::iterator it;
        for (it = li.begin(); it != li.end(); it++ )
        {
            cout << (*it)->data <<" ";
        }
        cout<<endl;
    }
}

int main()
{
     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
     Node<int>* root;
     root = NULL;
     createMinBST(root, arr, 0, 8);
     vector<list<Node<int>*> > res;
     levelLinkedLists(res, root);
     printLevelLinkedLists(res);

}

error:

4_4.cpp:50:20: error: member reference base type 'Node<int> *' is not a structure or union
        if(iter->left)
           ~~~~^ ~~~~

4_4.cpp:83:8: note: in instantiation of function template specialization 'levelLinkedLists' requested here levelLinkedLists(res, root); ^ 4_4.cpp:52:20: error: member reference base type 'Node *' is not a structure or union if(iter->right) ~~~~^ ~~~~~ 2 errors generated.

Finally got the correct working code .. thanks to everyone for their quick inputs

#include<iostream>
#include<vector>
#include<list>
using namespace std;

template<typename T>
struct Node
{
    T data;
    Node<T> *left,*right;
};

template<typename T>
Node<T>* newNode(T data)
{
    Node<T>* root = new Node<T>();
    root->data = data;
    root->left = NULL;
    root->right = NULL;
    return root;
}

template<typename T>
void createMinBST(Node<T>*& root,T arr[],int start,int end)
{
    if(start>end)
        return;
    int mid = (start+end)/2;
    if (root == NULL)
    {
        root = newNode(arr[mid]);
        createMinBST(root->left, arr,start , mid-1);
        createMinBST(root->right, arr,mid+1 , end);
    }
}

template<typename T>
void levelLinkedLists(vector<list<Node<T>*> >& res,Node<T>* root)
    list<Node<T>*>li;
    li.push_back(root);
    res.push_back(li);
    int depth = 0;
    while(!res[depth].empty())
    {
        list<Node<T>*>l;
        typename list<Node<T>*>::iterator iter;
        for(iter = res[depth].begin();iter != res[depth].end(); iter++)
        {
            if((*iter)->left)
                l.push_back((*iter)->left);
            if((*iter)->right)
                l.push_back((*iter)->right);
        }
        depth++;
        res.push_back(l);
    }
}

template<typename T>
void printLevelLinkedLists(vector<list<Node<T>*> > res)
{
    typename vector<list<Node<T>*> >::iterator iter;
    for (iter = res.begin(); iter!= res.end();iter++)
    {
        list<Node<T>*>li = *iter;
        typename list<Node<T>*>::iterator it;
        for (it = li.begin(); it != li.end(); it++ )
        {
            cout << (*it)->data <<" ";
        }
        cout<<endl;
    }
}

int main()
{     int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
     Node<int>* root;
     root = NULL;
     createMinBST(root, arr, 0, 8);
     vector<list<Node<int>*> > res;
     levelLinkedLists(res, root);
     printLevelLinkedLists(res);

}

[Do not use `using namespace std;` for your own sake!](http://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) — Baum mit Augen, Jan 17 '15 at 12:05
Look close at this statement: `cout<<" "<<*iter->data;`, what is `iter` here? And then learn about [operator precedence](http://en.cppreference.com/w/cpp/language/operator_precedence). — Some programmer dude, Jan 17 '15 at 12:11
C++11 features like `auto` and ranged-based for loops might make your life easier, e.g: `for (auto node : res[depth]){ if (node->left) ...` — Chris Drew, Jan 17 '15 at 12:28
Thanks.. Corrected all bugs.. please find revised code and new error — Peter_pk, Jan 17 '15 at 12:42
I don't believe you have corrected _all_ bugs otherwise you would not have an error, See comment from @JoachimPileborg . — Chris Drew, Jan 17 '15 at 12:48
@Chris Drew : Corrected all bugs and uploaded the soln as well.Thanks so much everyone for your valuable comments.. — Peter_pk, Jan 17 '15 at 13:03

mip · Accepted Answer · 2015-01-17T12:29:18.713

3

You have quite a lot of bugs in the code.

To avoid mentioned error add typename before iterators

typename list<Node<T>*>::iterator it;

Then you have typos in one of the for loops

for (it = li.begin(); it != li.end();it+++)
//should be:
for (auto it = li.begin(); it != li.end();it++)

Wrong number of parameters passed to levelLinkedLists in main

levelLinkedLists(res, root);

should be 3.

Use of undefined function.

createMinimalBst(root, arr, 0, 8);

You have defined function createMinBST, so probably a typo again.

edited Jan 17 '15 at 12:29

answered Jan 17 '15 at 12:16

mip

8,355
6
53
72

doc ! The solution you suggested has removed the error generated but isn't solving the purpose as after removing all bugs I am facing new errors given below: – Peter_pk Jan 17 '15 at 12:37
4_4.cpp:50:20: error: member reference base type 'Node *' is not a structure or union if(iter->left) ~~~~^ ~~~~ 4_4.cpp:83:8: note: in instantiation of function template specialization 'levelLinkedLists' requested here levelLinkedLists(res, root); ^ 4_4.cpp:52:20: error: member reference base type 'Node *' is not a structure or union if(iter->right) ~~~~^ ~~~~~ 2 errors generated. – Peter_pk Jan 17 '15 at 12:37
2

@Peter_pk If `iter` is an iterator of `list*>` then you can't write `iter->left`. You need to dereference the iterator and also the contained pointer so write `(*iter)->left`. Or use a ranged-based for loop. – Chris Drew Jan 17 '15 at 12:45

Iterating over templated list

1 Answers1