Range based for loop for linked list

Question

I have a function which operates on a nested linked list. The function is the following:

void DoLiana(void) {

    PlotPointer plot;
    TreePointer tree;

        plot = FirstPlot;
        while (plot != nullptr) {
            tree = plot->FirstTree;
            while (tree != nullptr) {
                if (tree->isLiana) {
                    if (tree->attachedTree == nullptr && TestForLianaAttach(plot, tree))
                    DoLianaAttachement(plot, tree);
                }
                tree = tree->next;
            }
            plot = plot->next;
        }    
}

Because this type of iterations happen multiple times in my code I am looking for a way to make the iteration more compact and expressive. I read that in C++11 there are ranged based for loops that iterate over a set. Would this construct be applicable in this situation? Or are there other possible ways to perform these iterations?

The range based for loop is mostly syntactic sugar and requires that you have a begin / end (more details here). So you just need to provide the required interface somehow. — Borgleader
– Borgleader, Commented Oct 2, 2018 at 13:58
range-for loop can iterate over anything that provides a pair of iterators. So, make your class support iteration. Or, just use std::list or std::slist for your linked-list needs - these classes already provide the necessary scaffolding. — Igor Tandetnik
– Igor Tandetnik, Commented Oct 2, 2018 at 14:00
It should be no problem. You need to provide begin and end method to your container, which would return object with operator++() and operator== defined. I think a simple pointer fits the bill. @IgorTandetnik I don't think the type returned by begin/end even needs to be an iterator formally. — luk32
– luk32, Commented Oct 2, 2018 at 14:01
But you could immediately use vanilla loops here: for (PlotPointer plot = FirstPlot; plot != nullptr; plot=plot.next) { for (TreePointer tree = plot->FirstTree, tree!= nullptr; tree=tree->next) { ... }} — Serge Ballesta
– Serge Ballesta, Commented Oct 2, 2018 at 14:02
@luk32 I'm not sure that a simple pointer would fit the bill: codereview.stackexchange.com/questions/74609/… — Bob__
– Bob__, Commented Oct 2, 2018 at 15:02

Loki Astari · Accepted Answer · 2018-10-02 15:31:05Z

3

Yes you can define the appropriate functions for this.

Since oyu have given very few details. Lets make some assumptions.

struct Tree
{
    bool  isLiana;
    void* attachedTree;
    Tree* next;
};

using TreePointer = Tree*;

struct Plot
{
    TreePointer FirstTree;
    Plot*       next;
};

using PlotPointer = Plot*;

bool TestForLianaAttach(PlotPointer, TreePointer);
void DoLianaAttachement(PlotPointer, TreePointer);

PlotPointer FirstPlot;

To make this work with pointers you need to define the appropriate begin() and end() methods for your pointers.

NextIterator<Plot> begin(PlotPointer ptr)  {return make_NextIterator(ptr);}
NextIterator<Plot> end(PlotPointer)        {return make_NextIterator<Plot>();}

NextIterator<Tree> begin(TreePointer ptr)  {return make_NextIterator(ptr);}
NextIterator<Tree> end(TreePointer)        {return make_NextIterator<Tree>();}

The range based for looks for begin() and end() functions that can be used with your type. Now the standard has default std::begin() and std::end() that call the begin() and end() methods on the objects passed. But you can provide your own (like the above) to do a special case for your type/pointer.

Now since your pointers use p = p->next; to advance we need an iterator object that does this part of the work. In the above code I have called this NextIterator. It is relatively easy to define.

template<typename T>
struct NextIterator
{
    T* p;

    NextIterator():       p(nullptr) {}
    NextIterator(T* ptr): p(ptr)     {}

    NextIterator& operator++(){p = p->next;return *this;}

    T const& operator*() const  {return *p;}
    T&       operator*()        {return *p;}
    T const* operator->() const {return p;}
    T*       operator->()       {return p;}

    bool operator==(NextIterator const& rhs) const {return p == rhs.p;}
    bool operator!=(NextIterator const& rhs) const {return p != rhs.p;}
};
template<typename T>
NextIterator<T> make_NextIterator(T* val)   {return NextIterator<T>(val);}
template<typename T>
NextIterator<T> make_NextIterator()         {return NextIterator<T>{};}

Now we can re-write your loops using the range based for.

void DoLianaRange(void) {

        for(auto& plot: FirstPlot) {
            for(auto& tree: plot.FirstTree) {
                if (tree.isLiana) {
                    if (tree.attachedTree == nullptr && TestForLianaAttach(&plot, &tree))
                    DoLianaAttachement(&plot, &tree);
                }
            }
        }
}

Original version for comparison.

void DoLiana(void) {

    PlotPointer plot;
    TreePointer tree;

        plot = FirstPlot;
        while (plot != nullptr) {
            tree = plot->FirstTree;
            while (tree != nullptr) {
                if (tree->isLiana) {
                    if (tree->attachedTree == nullptr && TestForLianaAttach(plot, tree))
                    DoLianaAttachement(plot, tree);
                }
                tree = tree->next;
            }
            plot = plot->next;
        }
}

Or you could simply use the standard for loop!!

void DoLianaForLoop(void) {

        for (PlotPointer plot = FirstPlot; plot != nullptr; plot = plot->next) {
            for (TreePointer tree= plot->FirstTree; tree != nullptr; tree = tree->next) {
                if (tree->isLiana) {
                    if (tree->attachedTree == nullptr && TestForLianaAttach(plot, tree))
                    DoLianaAttachement(plot, tree);
                }
            }
        }
}

Code all in one place (in the correct order to compile).

struct Tree
{
    bool  isLiana;
    void* attachedTree;
    Tree* next;
};

using TreePointer = Tree*;

struct Plot
{
    TreePointer FirstTree;
    Plot*       next;
};

using PlotPointer = Plot*;

template<typename T>
struct NextIterator
{
    T* p;

    NextIterator():       p(nullptr) {}
    NextIterator(T* ptr): p(ptr)     {}

    NextIterator& operator++(){p = p->next;return *this;}

    T const& operator*() const  {return *p;}
    T&       operator*()        {return *p;}
    T const* operator->() const {return p;}
    T*       operator->()       {return p;}

    bool operator==(NextIterator const& rhs) const {return p == rhs.p;}
    bool operator!=(NextIterator const& rhs) const {return p != rhs.p;}
};

template<typename T>
NextIterator<T> make_NextIterator(T* val)   {return NextIterator<T>(val);}
template<typename T>
NextIterator<T> make_NextIterator()         {return NextIterator<T>{};}

NextIterator<Plot> begin(PlotPointer ptr)  {return make_NextIterator(ptr);}
NextIterator<Plot> end(PlotPointer)        {return make_NextIterator<Plot>();}

NextIterator<Tree> begin(TreePointer ptr)  {return make_NextIterator(ptr);}
NextIterator<Tree> end(TreePointer)        {return make_NextIterator<Tree>();}

bool TestForLianaAttach(PlotPointer, TreePointer);
void DoLianaAttachement(PlotPointer, TreePointer);

PlotPointer FirstPlot;

void DoLianaRange(void) {

        for(auto& plot: FirstPlot) {
            for(auto& tree: plot.FirstTree) {
                if (tree.isLiana) {
                    if (tree.attachedTree == nullptr && TestForLianaAttach(&plot, &tree))
                    DoLianaAttachement(&plot, &tree);
                }
            }
        }
}
void DoLiana(void) {

    PlotPointer plot;
    TreePointer tree;

        plot = FirstPlot;
        while (plot != nullptr) {
            tree = plot->FirstTree;
            while (tree != nullptr) {
                if (tree->isLiana) {
                    if (tree->attachedTree == nullptr && TestForLianaAttach(plot, tree))
                    DoLianaAttachement(plot, tree);
                }
                tree = tree->next;
            }
            plot = plot->next;
        }
}

edited Oct 2, 2018 at 15:31

answered Oct 2, 2018 at 15:03

Loki Astari

266k87 gold badges344 silver badges575 bronze badges

Sign up to request clarification or add additional context in comments.

9 Comments

Caleth Over a year ago

NextIterator should be DefaultConstructible, which is as easy as putting ` = nullptr` in the current constructor's argument list. The end iterator can then just be {}

Loki Astari Over a year ago

@Caleth: If you want to make NextIterator match the Iterator Concept. The range based for does not require that types be iterators.

Caleth Over a year ago

It also gets rid of the ugly make_NextIterator(static_cast<Tree*>(nullptr))

Caleth Over a year ago

Actually, make_NextIterator seems to be more trouble than it is worth. NextIterator<Plot> begin(PlotPointer ptr) {return ptr;} NextIterator<Plot> end(PlotPointer ) {return nullptr; } do better

Loki Astari Over a year ago

@Caleth But it fits a nice pattern (started by the standard). So yes the code is a bit cumbersome to write initially, but it provides mental clues and adds to the documentation of what is expected.

|

Joseph Quinsey · Accepted Answer · 2018-10-11 14:26:02Z

0

To follow up on Serge Ballesta's comment, you could immediately use vanilla for loops here, replacing the while loops. So your sample code will become:

void DoLiana(void) {

    for (PlotPointer plot = FirstPlot; plot; plot = plot->next) { 
        for (TreePointer tree = plot->FirstTree; tree; tree = tree->next) {
            if (tree->isLiana && !tree->attachedTree && TestForLianaAttach(plot, tree)) {
                DoLianaAttachement(plot, tree);
            }
        }
    }
}

This shortens the code, and adds locality and perhaps readability. And also maintains compatibility with C, if this is an advantage.

answered Oct 11, 2018 at 14:26

Joseph Quinsey

9,99210 gold badges58 silver badges83 bronze badges

Collectives™ on Stack Overflow

Range based for loop for linked list

2 Answers 2

9 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

9 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related