Односвязный список , где- то портится память

[gorbovsky]

Добрый день, уважаемые.
Реализуем динамический массив на простом односвязном списке.
При удалении нулевого элемента теряются данные, возможно ломается память.
Не могу понять что за засада.
онлайн компилятор https://www.onlinegdb.com/, с++14

#include <iostream>
 
 
 
struct userdata
{
  int a;
    userdata ():a (0)
  {            
  }
  int get () const
  {
    return a;
  }
  void set (const int val)
  {
    a = val;
  }
};
 
 
 
template <class T> class dynarray
{
  unsigned len;
  struct elem
  {
    T *data;
    elem *next;
  };
  elem *first, *last;
  inline bool is_empty () const
  {
    return first == nullptr;
  }
public:
  typedef void (*for_each_func) (T *);
  for_each_func func;
  int for_each (unsigned Begin, unsigned End, for_each_func Func)   //  for_each function
  {
    int retval = 0;
    for (; Begin <= End; ++Begin)
      {
    Func (operator[](Begin));
 
    retval++;
      }
    return retval;
  }
dynarray ():first (nullptr), last (nullptr), len (0){}  // default constructor
 
  unsigned Length () const
  {
    return len;
  }
  void push_back (T * obj)  //  push_back function
  {
    if (is_empty ())
      {
    first = new elem;
    last = new elem;
    first->next = last;
    first->data = obj;
    len++;
    return;
      }
    else
      {
    elem *temp = new elem;
    last->next = temp;
    last = temp;
    last->data = obj;
    len++;
      }
 
  }
  T *operator[] (const unsigned Index) const    // operator [] function
  {
    if (is_empty ())
      return nullptr;
    if (Index >= len)
      return nullptr;
    if (Index == 0)
      return first->data;
    elem *stack = first->next;
    for (auto i = 0; i < Index; ++i)
      {
    if (stack->next == nullptr)
      return nullptr;
    stack = stack->next;
      }
    return stack->data;
 
  }
  T *Delete (unsigned Index)    //  Delete element function
  {
 
    if (is_empty ())
      return nullptr;
    T *retval;
    if (len == 1)       // only one element in array
      {
    retval = first->data;
    delete first;
    delete last;
    len = 0;
    first = nullptr;
    last = nullptr;
    return retval;
      }
    elem *temp;
    if (Index == 0)     //  deleting first element
      {
    retval = first->data;  // проблема где- то здесь, все остальное функционирует
    temp = first;
    first=first->next;
    delete temp;
    len--;
    return retval;
      }
 
    elem *stack = first;
    for (unsigned i = 0; i < Index; ++i)
      stack = stack->next;
    temp = stack->next->next;
    retval = stack->next->data;
    delete stack->next;
    stack->next = temp;
    len--;
    return retval;
  }
 
};
 
using namespace std;
 
int
main ()
{
  dynarray < userdata > d;
  userdata *obj;
  for (auto i = 0; i < 10; ++i)
    {
      obj = new userdata;
      obj->set (i);
      d.push_back (obj);
 
    }
  userdata *ud=d.Delete (0);
cout << d[1]->get() << endl;  //  Работает
  cout << d[0]->get ();       //  Падает
 
  return 0;
}

[Majestio]

Цитата gorbovsky @ 24.07.23, 22:51

Не могу понять что за засада.

Немного подправил твой код, надеюсь не накосячил, лови-разбирайся:

#include <iostream>
 
// userdata - - -
 
struct userdata {
    int a;
 
    userdata(int i): a(i) {
    }
 
    int get() const {
        return a;
    }
 
    void set(const int val) {
        a = val;
    }
 
    friend std::ostream& operator<<(std::ostream& os, const userdata& obj) {
        os << obj.a << std::endl;
        return os;
    }
 
};
 
// dynarray - - -
 
template <typename T> class dynarray {
        unsigned len;
 
        struct elem {
            T *data;
            elem *next;
            elem(T *init) : data(init) {}
        };
 
        elem *first, *last;
 
        inline bool is_empty() const {
            return first == nullptr;
        }
 
    public:
 
        // default constructor
 
        dynarray(): len(0), first(nullptr), last(nullptr), func(nullptr) {}
 
        // default destructor
 
        ~dynarray() {
            while (first) {
                auto tmp = first;
                delete first->data; // нужно ли чистить данные или оставлять их висеть в памяти - я х3 чё надо
                first = (first == last) ? nullptr : first->next;
                delete tmp;
            }
        }
 
        // operator [] function
 
        T *operator[](const unsigned Index) const {
            if (is_empty() || Index >= len) return nullptr;
            T *ret = nullptr;
            auto tmp = first;
            for (unsigned i = 0; i <= Index; ++i) {
                if (i == Index) {
                    ret = tmp->data;
                    break;
                }
                tmp = tmp->next;
            }
            return ret;
        }
 
        //  for_each function
 
        typedef void (*for_each_func)(T *);
        for_each_func func;
 
        int for_each(unsigned Begin, unsigned End, for_each_func Func) {
            int ret = 0;
            if (End <= len) {
                for (; Begin < End; ++Begin) {
                    Func(operator[](Begin));
                    ret++;
                }
            }
            return ret;
        }
 
        unsigned Length() const {
            return len;
        }
 
        //  push_back function
 
        void push_back(T *obj) {
            elem *ins = new elem(obj);
            elem *tmp = last;
            if (tmp == nullptr) {
                first = ins;
                last = ins;
                first->next = last;
            } else {
                last->next = ins;
                last = ins;
            }
            len++;
        }
 
        //  Delete element function
 
        void Delete(unsigned Index) {
            if (Index >= len) return;
            elem *prev =  nullptr;
            elem *curr =  first;
            for (unsigned i = 0; i <= Index; ++i) {
                if (i == Index) {
                    if (curr == first) first = (len > 1) ? first->next : nullptr;
                    if (curr == last) last = (len > 1) ? prev : nullptr;
                    if (prev) prev->next = curr->next;
                    delete curr->data;
                    delete curr;
                    len--;
                    break;
                } else {
                    prev = curr;
                    curr = curr->next;
                }
            }
        }
 
        // For dump
 
        friend std::ostream& operator<<(std::ostream& os, const dynarray<T>& obj) {
            os << "Current number of items:  " << obj.Length() << std::endl << "---------------------------------" << std::endl;
            elem *tmp = obj.first;
            for (unsigned i = 0; i < obj.Length(); ++i) {
                os << "  " << *(tmp->data);
                tmp = tmp->next;
            }
            os << "---------------------------------\nDone." << std::endl;
            return os;
        }
 
};
 
using namespace std;
 
int main() {
    // создаем и печатаем пустой список
    dynarray < userdata > d;
    std::cout << d << std::endl;
    // заполняем список 5-ю элементами и печатаем список
    for (auto i = 0; i < 5; ++i) d.push_back(new userdata(i));
    std::cout << d << std::endl;
    // печатаем второй элемент по индексу
    std::cout << "Item #2: " << *(d[2]) << std::endl;
    // Удаляем нулевой элемент (из 5-ти) и печатаем список
    d.Delete(0);
    std::cout << d << std::endl;
    // Удаляем первый элемент (из 4-х) и печатаем список
    d.Delete(1);
    std::cout << d << std::endl;
    // Удаляем второй элемент (из 3-х) и печатаем список
    d.Delete(2);
    std::cout << d << std::endl;
    // Удаляем первый элемент (из 2-х) и печатаем список
    d.Delete(1);
    std::cout << d << std::endl;
    // Удаляем нулевой элемент (из 1-го) и печатаем список
    d.Delete(0);
    std::cout << d << std::endl;
    // Удаляем нулевой элемент (из пустого списка) и печатаем список
    d.Delete(0);
    std::cout << d << std::endl;
    return 0;
}

Исполнение в онлайн компиляторе тут.

P.S. Метод Delete я немного изменил, мне не нравится когда название одно, а от метода ждут еще чего-то. Удалить - значит удалить. А удалить из списка, но не удалять данные ... скорее всего лучше подходит название Shift. Ну это так - мои заморочки.

[gorbovsky]

Победил.
Косяк в методе push_back.
Majestio спасибо за труд.

#include <iostream>
 
 
 
struct userdata
{
  int a;
    userdata ():a (0)
  {            
  }
  int get () const
  {
    return a;
  }
  void set (const int val)
  {
    a = val;
  }
};
 
 
 
template <class T> class dynarray
{
  unsigned len;
  struct elem
  {
    T *data;
    elem *next;
  };
  elem *first, *last;
  inline bool is_empty () const
  {
    return first == nullptr;
  }
public:
  typedef void (*for_each_func) (T *);
  for_each_func func;
  int for_each (unsigned Begin, unsigned End, for_each_func Func)   //  for_each function
  {
    int retval = 0;
    for (; Begin <= End; ++Begin)
      {
    Func (operator[](Begin));
 
    retval++;
      }
    return retval;
  }
dynarray ():first (nullptr), last (nullptr), len (0){}  // default constructor
 
  unsigned Length () const
  {
    return len;
  }
  void push_back (T * obj)  //  push_back function
  {
    if (is_empty ())
      {
    first = new elem;
    last = new elem;
    first->next = last;
    first->data = obj;
    len++;
    return;
      }
  
    last->data=obj;
    last->next=new elem;
    last=last->next;
    len++;
  }
  T *operator[] (unsigned Index) const    // operator [] function
  {
    if (is_empty ())
      return nullptr;
    if (Index >= len)
      return nullptr;
    if (Index == 0)
      return first->data;
    elem *stack = first;
    do
    stack = stack->next;
    while(--Index);
    
    return stack->data;
 
  }
  T *Delete (const unsigned Index)    //  Delete element function
  {
 
    if (is_empty ())
      return nullptr;
    T *retval=first->data;
    if (len == 1)       // only one element in array
      {
    
    delete first;
    delete last;
    len = 0;
    first =last= nullptr;
    //last = nullptr;
    return retval;
      }
    elem *temp=first;
    if (Index == 0)     //  deleting first element
      {
    first=first->next;
    delete temp;
    len--;
    return retval;
      }
     elem *stack=first;
    for (unsigned i = 0; i < Index; ++i)
      stack = stack->next;
    temp = stack->next->next;
    retval = stack->next->data;
    delete stack->next;
    stack->next = temp;
    len--;
    return retval;
  }
 
};
 
using namespace std;
 
int
main ()
{
  dynarray < userdata > d;
  userdata *obj;
  for (auto i = 0; i < 10; ++i)
    {
      obj = new userdata;
      obj->set (i);
      d.push_back (obj);
      cout << d[i]->get()<< endl;
 
    }
 userdata *ud=d.Delete (0);
 delete d.Delete(d.Length()-1);
for(auto i=0;i<d.Length();++i)
cout << d[i]->get()<<endl;
 
  return 0;
}

Теперь как- то надо покурить на тему итератора к этому кадавру.

[gorbovsky]

Привинтил итератор, оказалось и несложно, даже справка не потребовалась, компилятор все подсказал.
dynarray.h

template <class T> class dynarray
{
    unsigned len;
    struct elem
    {
        T* data;
        elem* next;
    };
    elem* first, * last;
    inline bool is_empty() const
    {
        return first == nullptr;
    }
    //--------------------------------------------------------
public:
    class Iterator
    {
 
        dynarray* obj;
    public:
        unsigned index;
        Iterator() : obj(nullptr), index(0) {}
        Iterator(dynarray* Obj, unsigned Index) : obj(Obj), index(Index) {}
 
        bool operator == (const Iterator val)
        {
            return index == val.index;
        }
        Iterator& operator=(Iterator val)
        {
            index = val.index;
            obj = val.obj;
            return *this;
        }
 
        bool operator !=(const Iterator val)
        {
            return(index != val.index);
        }
        Iterator& operator ++ ()
        {
            index++;
            return *this;
        }
        Iterator operator++(int)
        {
            index++;
            return Iterator(obj, index);
        }
 
        T* operator *()
        {
            return (obj->operator[](index));
        }
 
    };
 
    //--------------------------------------------------------
public:
 
    typedef void (*for_each_func) (T*);
    // for_each_func func;
    int for_each(unsigned Begin, unsigned End, for_each_func Func)   //  for_each function
    {
        int retval = 0;
        for (; Begin <= End; ++Begin)
        {
            Func(operator[](Begin));
 
            retval++;
        }
        return retval;
    }
    dynarray() :first(nullptr), last(nullptr), len(0) {}  // default constructor
 
    //--------------------------------------------------------
    Iterator begin() { return Iterator(this, 0); }
    Iterator end() { return Iterator(this, len); }
    //--------------------------------------------------------
    unsigned Length() const
    {
        return len;
    }
    void push_back(T* obj)  //  push_back function
    {
        if (is_empty())
        {
            first = new elem;
            last = new elem;
            first->next = last;
            first->data = obj;
            len++;
            return;
        }
 
        last->data = obj;
        last->next = new elem;
        last = last->next;
        len++;
    }
    T* operator[] (unsigned Index) const    // operator [] function
    {
        if (is_empty())
            return nullptr;
        if (Index >= len)
            return nullptr;
        if (Index == 0)
            return first->data;
        elem* stack = first;
        do
            stack = stack->next;
        while (--Index);
 
        return stack->data;
 
    }
    T* Delete(const unsigned Index)    //  Delete element function
    {
 
        if (is_empty())
            return nullptr;
        T* retval = first->data;
        if (len == 1)       // only one element in array
        {
 
            delete first;
            delete last;
            len = 0;
            first = last = nullptr;
            //last = nullptr;
            return retval;
        }
        elem* temp = first;
        if (Index == 0)     //  deleting first element
        {
 
            first = first->next;
            delete temp;
            len--;
            return retval;
        }
        elem* stack = first;
        for (unsigned i = 0; i < Index; ++i)
            stack = stack->next;
        temp = stack->next->next;
        retval = stack->next->data;
        delete stack->next;
        stack->next = temp;
        len--;
        return retval;
    }
 
};

main.cpp

int main()
{
    #include <iostream>
    #include <algorithm>
    dynarray<userdata> d;
    for (auto i = 0; i < 10; ++i)
        d.push_back(new userdata(i));
 
    for_each(d.begin(), d.end(), [](userdata* i) {cout << i->get() << ","; });
 
    dynarray<userdata>::Iterator iter(&d, 7);
    auto iter2(iter);
    iter2++;
    cout << "   " << (*iter2)->get() << endl;
    for (auto p : d) { cout << p->get() << " ; "; } // Прикольный for, не знал раньше, только итератор разыменовывает зачем- то
    return 0;
}

Сообщение отредактировано: gorbovsky - 27.07.23, 15:06