Диапазон на основе цикла для связанного списка - PullRequest
Новая
       36

Диапазон на основе цикла для связанного списка

0 голосов
/ 02 октября 2018

У меня есть функция, которая работает с вложенным связанным списком.Функция выглядит следующим образом: 

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;
        }    
}

Поскольку итерации такого типа встречаются в моем коде несколько раз, я ищу способ сделать итерацию более компактной и выразительной.Я читал, что в C ++ 11 есть ранжирование, основанное на циклах, которые повторяются в наборе.Будет ли эта конструкция применима в этой ситуации?Или есть другие возможные способы выполнения этих итераций?

Ответы [ 2 ]

0 голосов
/ 11 октября 2018

Чтобы прокомментировать комментарий Сержа Баллесты , вы можете немедленно использовать ванильные петли for, заменив петли while.Таким образом, ваш пример кода станет: 

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);
            }
        }
    }
}

Это сокращает код и добавляет местность и, возможно, удобочитаемость.А также поддерживает совместимость с C, если это является преимуществом.

0 голосов
/ 02 октября 2018

Да, вы можете определить соответствующие функции для этого.

Поскольку ою предоставили очень мало деталей.Давайте сделаем некоторые предположения. 

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;

Чтобы сделать эту работу с указателями, вам нужно определить соответствующие методы begin() и end() для ваших указателей. 

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>();}

В зависимости от диапазонаfor ищет функции begin() и end(), которые можно использовать с вашим типом.Теперь в стандарте есть значения по умолчанию std::begin() и std::end(), которые вызывают методы begin() и end() для переданных объектов.Но вы можете предоставить свой собственный (как вышеописанный) для особого случая для вашего типа / указателя.

Теперь, так как ваши указатели используют p = p->next; для продвижения, нам нужен объект итератор, который выполняет эту часть работы,В приведенном выше коде я назвал это NextIterator.Его относительно легко определить. 

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>{};}

Теперь мы можем переписать ваши циклы, используя диапазон, основанный на. 

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;
        }
}

Или вы можете просто использовать стандартный цикл for !! 

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);
                }
            }
        }
}

Кодировать все в одном месте (в правильном порядке для компиляции). 

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;
        }
}
...