iterator

[ЫукпШ]

Цитата shm @ 08.07.16, 18:21

Я конечно не знаю, после 8ми часов поиска КЗ на новой плате я уже не сильно соображаю,

Режь её, как льва в Африке, чего столько времени терпеть.
Мы для платы, или плата для нас ?
Если поиски такие долгие, ножом всё и закончится..

[Cfon]

Цитата Qraizer @ 08.07.16, 18:34

Внутри цикла ты делаешь delete узлу списка, а позже в инкременте итератора обращаешься к его полю next.

да это я уже понял

Добавлено 08.07.16, 18:41

Цитата shm @ 08.07.16, 18:32

for (NodeIterator tmp; headIterator != NodeIterator(); )
{
   tmp = headIterator;  
   ++headIterator;
   delete tmp.getNode();
}

бинго shm работает

Добавлено 08.07.16, 18:41
спс

[shm]

Цитата Cfon @ 08.07.16, 18:29

что то не соображу можно ли как то код там изменить чтоб было ОК?

Когда-то делал я свой список с итераторами. До дома дойду, выложу решение. Скажу лишь, что у меня есть обертка для элемента списка (шаблонный класс с пользовательским полем data) и отдельно класс списка, который всем этим рулит.

Добавлено 08.07.16, 18:43

Цитата ЫукпШ @ 08.07.16, 18:39

Режь её, как льва в Африке, чего столько времени терпеть.

Да нашел уже. Методом пайки-выпайки элементов.

Сообщение отредактировано: shm - 08.07.16, 18:43

[Cfon]

мля сам же это решение выше написал а вот перевести на итератор не смог

Добавлено 08.07.16, 18:44
спс shm выручил а то башка уже болит

[shm]

Как и обещал выкладываю свою реализацию из ядра своей игрушечной ОС. Не претендую на правильность реализации. Писал это дело очень давно я (еще в школе учился ), качество кода так себе. Но у меня удаление объекта (если мы храним в списке указатели на него) не рушит ссылки.

template< typename T >
class klist
{
    struct _node_item
    {
        T item;
        _node_item *next;
        _node_item *prev;
    };
public:
    class iterator
    {
        _node_item *_pitem;
        friend class klist;
    public:
        const bool operator!=(const iterator &it) const
        {
            return (_pitem != it._pitem);
        }
        T& operator*() const
        {
            return _pitem->item;
        }
        const iterator& operator++(int)
        {
            _pitem = _pitem->next;
            return *this;
        }      
        const iterator& operator++()
        {
            _pitem = _pitem->next;
            return *this;
        }  
    };
private:
    static const size_t _default_alloc_areas_size = 4;
    static const size_t _default_max_size = 0x100000;
    static const size_t _default_base_size = 0x10;
    kvector<_node_item*> _alloc_areas;
    _node_item *_free_list;
    iterator    _begin_item;
    iterator    _end_item;
    iterator    _end_item_ret;
    size_t _cur_ar_size;
    size_t _max_size;
    
    void _add_free_region(size_t ar_size)
    {
        _node_item *ar = new _node_item[_cur_ar_size];
        _node_item *it, *end = ar + ar_size - 1, *tmp;
        for(it = ar; it < end; )
        {
            tmp = it++;
            tmp->next = it;
        }
        it->next = NULL;
        _free_list = ar;
        _alloc_areas.push_back(ar);
    }
    
    void _init(size_t base_size, size_t max_size)
    {
        _cur_ar_size = base_size;
        _max_size = max_size;
        _begin_item._pitem = NULL;
        _end_item._pitem = NULL;
        _end_item_ret._pitem = NULL;
        _add_free_region(_cur_ar_size);
    }
    
    _node_item *_alloc_item()
    {
        if(_free_list == NULL)
        {
            _cur_ar_size <<= 1;
            if(_cur_ar_size > _max_size)
                _cur_ar_size = _max_size;
            _add_free_region(_cur_ar_size);
        }
        _node_item *item = _free_list;
        _free_list = item->next;
        return item;
    }
public:
    klist()
        : _alloc_areas(_default_alloc_areas_size)
    {
        _init(_default_base_size, _default_max_size);
    }
    
    ~klist()
    {
        typename kvector<_node_item*>::iterator it = _alloc_areas.begin();
        for( ; it < _alloc_areas.end(); it++)
            delete[] *it;
    }
    
    klist(size_t base_size, size_t max_size = _default_max_size)
        : _alloc_areas(_default_alloc_areas_size)
    {
        _init(base_size, max_size);
    }
    
    void push_back(const T &item)
    {
        _node_item *pitem = _alloc_item();
        pitem->item = item;
        if(_end_item._pitem == NULL)
        {
            pitem->prev = NULL;
            pitem->next = NULL;
            _end_item._pitem = pitem;
            _begin_item._pitem = pitem;
        }
        else
        {
            pitem->next = NULL;
            pitem->prev = _end_item._pitem;
            _end_item._pitem->next = pitem;
            _end_item._pitem = pitem;
        }
    }
    
    const iterator& begin() const
    {
        return _begin_item;
    }
    
    iterator& begin()
    {
        return _begin_item;
    }
    
    const iterator& end() const
    {
        return _end_item_ret;
    }
    
    iterator erase(iterator &it)
    {
        _node_item *cur = it._pitem;
        _node_item *next = cur->next;
        cur->next = _free_list;
        _free_list = cur;
        if(_end_item._pitem == cur)
            _end_item._pitem = NULL;
        if(it._pitem == _begin_item._pitem)
        {
            _begin_item._pitem = next;
            return _begin_item;
        }
        else
        {
            _node_item *prev = cur->prev;
            prev->next = next;
            if(next != NULL)
                next->prev = prev;
            iterator next_it;
            next_it._pitem = next;
            return next_it;
        }
    }
    
    void clear()
    {
        for(_node_item *area : _alloc_areas)
            delete[] area;
        _alloc_areas.clear();
        _init(_default_base_size, _default_max_size);
    }
    
    void clear_no_free()
    {
        for(auto it = begin(); it != end(); it = erase(it));
    }
};

Сообщение отредактировано: shm - 08.07.16, 20:08

[Cfon]

Цитата shm @ 08.07.16, 20:07

Как и обещал выкладываю свою реализацию из ядра своей игрушечной ОС. Не претендую на правильность реализации. Писал это дело очень давно я (еще в школе учился ), качество кода так себе. Но у меня удаление объекта (если мы храним в списке указатели на него) не рушит ссылки.

shm
будет чем заняться на досуге

Добавлено 09.07.16, 05:08
немного изменил код
добавил operator++(int) и т.о. вызов упростился до

while (nodeIterator != NodeIterator()){
        delete (nodeIterator++).getNode();
}

[Cfon]

что то с std::for_each я туплю

std::for_each(nodeIterator, NodeIterator(),
        [&nodeIterator](const Node& ){
            delete (nodeIterator++).getNode();
        });

не работает иксепщн ловит

Добавлено 09.07.16, 05:28
вот так пробовал тоже иксепшен

std::for_each(nodeIterator, NodeIterator(),
        []( Node& node){
        Node* tmp = node.next;
        delete &node;
        node = *tmp;
    });

[shm]

Цитата Cfon @ 09.07.16, 05:21

delete (nodeIterator++).getNode();

Это тоже самое, что:

delete nodeIterator.getNode()
++nodeIterator;

Добавлено 09.07.16, 12:49

Цитата Cfon @ 09.07.16, 05:21

вот так пробовал тоже иксепшен

А это вообще не должно работать, т.к.

Цитата Cfon @ 09.07.16, 05:21

for_each

идет по твоему самодельному итератору, а не по ссылке на node.

[Cfon]

Цитата shm @ 09.07.16, 12:37

Цитата Cfon @ 09.07.16, 05:21

delete (nodeIterator++).getNode();

Это тоже самое, что:

delete nodeIterator.getNode()
++nodeIterator;

нет не тоже
в operator++(int) возвращается копия предыдущего NodeIterator

NodeIterator operator++(int) {
        NodeIterator tmp(*this);
        node = node->next; return tmp;
    }

Добавлено 09.07.16, 15:29

Цитата shm @ 09.07.16, 12:37

А это вообще не должно работать, т.к.

Цитата Cfon @ 09.07.16, 05:21

for_each

идет по твоему самодельному итератору, а не по ссылке на node.

тогда как надо то?

Добавлено 09.07.16, 15:33
вот так цикл висит

while (nodeIterator != NodeIterator()){
        delete nodeIterator.getNode();
        ++nodeIterator;
    }

Сообщение отредактировано: Cfon - 09.07.16, 15:39

[shm]

Цитата Cfon @ 09.07.16, 15:27

нет не тоже

for_each каждый раз дергает operator++ со своим внутренним итератором, который к твоему nodeIterator отношения не имеет.

Добавлено 09.07.16, 22:56

Цитата Cfon @ 09.07.16, 15:27

тогда как надо то?

Я не знаю, что ты хочешь.

Добавлено 09.07.16, 23:00

Цитата simsergey @ 09.07.16, 15:44

Как там оказалось два - это вопрос интересный!

Человек, который разводил плату, не знал какую модель памяти использовать, поэтому "предусмотрел" два варианта. Но в итоге все благополучно забылось и запаяли оба.

[Cfon]

shm я тебе говорил про то что след вариант тоже удаляет и все работает нормально!

while (nodeIterator != NodeIterator()){
        delete (nodeIterator++).getNode();
    }

ты мне написал что это тоже самое что

while (nodeIterator != NodeIterator()){
        delete nodeIterator.getNode();
        ++nodeIterator;
    }

но это не так

Добавлено 10.07.16, 02:19

Цитата shm @ 09.07.16, 22:55

Я не знаю, что ты хочешь.

ОМГ
shm я хочу тоже что и раньше удалить эти ноды но уже через алгоритм std::for_each

Добавлено 10.07.16, 02:22
вот такой вариант не работает

std::for_each(nodeIterator, NodeIterator(),
        []( Node& node){
        Node* tmp = node.next;
        delete &node;
        node = *tmp;
    });

Добавлено 10.07.16, 02:26
вот этот вариант не надо больше обсуждать

std::for_each(nodeIterator, NodeIterator(),
        [&nodeIterator](const Node& ){
            delete (nodeIterator++).getNode();
        });

я уже понял что

Цитата shm @ 09.07.16, 22:55

for_each каждый раз дергает operator++ со своим внутренним итератором, который к твоему nodeIterator отношения не имеет.

Сообщение отредактировано: Cfon - 10.07.16, 02:28

[Cfon]

Цитата Cfon @ 10.07.16, 02:14

вот такой вариант не работает

std::for_each(nodeIterator, NodeIterator(),
        []( Node& node){
        Node* tmp = node.next;
        delete &node;
        node = *tmp; // <-- тут не верно
    });

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

for_each(nodeIterator, NodeIterator(),
        []( Node& node){            
            Node* tmp = node.next;
            delete &node;
            &node = tmp; //<-- тут
        });

но и это не корректно т.к. происходит попытка изменить ссылку node чего делать нельзя
делаю вывод что удалить через std::for_each не получиться по причине передачи node по ссылке!

Сообщение отредактировано: Cfon - 10.07.16, 04:55

[shm]

Цитата Cfon @ 10.07.16, 02:14

ты мне написал что это тоже самое что

Во-первых я про цикл не упоминал. Во-вторых да, некорректно я написал. Я имел ввиду все целиком с for_each. Если будешь дальше из себя строить шибко умного, то подсказывать не буду.

Добавлено 10.07.16, 09:55

Цитата Cfon @ 10.07.16, 02:14

shm я хочу тоже что и раньше

Я понятия не имею, что ты хотел раньше.

Цитата Cfon @ 10.07.16, 02:14

удалить эти ноды но уже через алгоритм std::for_each

Удалить можно, но хороших решений не вижу.

Добавлено 10.07.16, 10:01

Node *old = nullptr;
std::for_each(nodeIterator, NodeIterator(),
    [&old]( Node& node) {
    delete old;
    old = &node;
});
delete old;

Сообщение отредактировано: shm - 10.07.16, 10:59

[shm]

Ну извратов много можно придумать:

struct FakeIterator : public  NodeIterator
{
    FakeIterator() : NodeIterator() { }
    FakeIterator(Node* _node): NodeIterator(_node) { }
    FakeIterator& operator++()
    {
        auto node = getNode();
        NodeIterator::operator++();
        delete node;
        return *this;
    }
};
//...
FakeIterator nodeIterator(head);
    std::for_each(nodeIterator, FakeIterator(),
        []( Node& node) {
    });

[Cfon]

Цитата shm @ 10.07.16, 09:38

Во-первых я про цикл не упоминал. Во-вторых да, некорректно я написал. Я имел ввиду все целиком с for_each. Если будешь дальше из себя строить шибко умного, то подсказывать не буду.

shm сори

Добавлено 10.07.16, 11:35

Цитата shm @ 10.07.16, 09:38

Удалить можно, но хороших решений не вижу.

Node *old = nullptr;
std::for_each(nodeIterator, NodeIterator(),
    [&old]( Node& node) {
    delete old;
    old = &node;
});
delete old;
 
 
struct FakeIterator : public  NodeIterator
{
    FakeIterator() : NodeIterator() { }
    FakeIterator(Node* _node): NodeIterator(_node) { }
    FakeIterator& operator++()
    {
        auto node = getNode();
        NodeIterator::operator++();
        delete node;
        return *this;
    }
};
 
//...
 
FakeIterator nodeIterator(head);
    std::for_each(nodeIterator, FakeIterator(),
        []( Node& node) {
    });;

да уж изврат

Добавлено 10.07.16, 11:38
тогда по стринке в цикле

Добавлено 10.07.16, 11:43

Цитата shm @ 10.07.16, 11:10

Qraizer, если не лень, то перенеси в отдельную тему.

не лень.. это его обязаность

Сообщение отредактировано: Cfon - 10.07.16, 11:43