c++ 交换和赋值运算符在链表类中调用自身，导致堆栈溢出

xggvc2p6  于 8个月前  发布在  其他
关注(0)|答案(2)|浏览(107)

当我尝试打印ArrayList的项目时，我从Visual Studio中得到了这个错误：

Unhandled exception at 0x00007FF9E8AF8739 (ucrtbased.dll) in List.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x0000007E50C13FF8).

字符串
我不知道这是怎么回事。我试图实现复制和交换的习惯用法。
我正在阅读一个数字文件，将它的数字添加到一个链表中。然后将该链表附加到一个动态数组中并打印其内容。LinkedList和ArrayList都重载了operator<<。
LinkedList.hpp:

#ifndef LINKEDLIST_HPP
#define LINKEDLIST_HPP

#include "List.hpp"
#include "Node.hpp"

#include <iostream> // operator<<

template <typename T>
class LinkedList: public List<T>
{
private:
    Node<T>* m_head{nullptr};
    Node<T>* m_tail{nullptr};

    int m_size{};

    void swap(T& a, T& b)
    {
        auto temp = a;
        a = b;
        b = temp;
    }

    void swap(LinkedList<T>& a, LinkedList<T>& b)
    {
        LinkedList<T> temp = a;
        a = b;
        b = temp;
    }

public:
    LinkedList() = default;

    LinkedList(std::initializer_list<T> i_list)
    {
        for (const auto& item : i_list)
        {
            append(item);
        }
    }

    // Copy constructor.
    LinkedList(const LinkedList<T>& other) : List<T>{}
    {
        auto temp = other.m_head;

        while (temp != nullptr)
        {
            append(temp->data);
            temp = temp->next;
        }
    }

    ~LinkedList()
    {
        // Start from the beginning.
        Node<T>* temp = m_head;

        // Traverse the list while deleting previous elements.
        while (temp != nullptr)
        {
            temp = temp->next; // Move forward.
            delete m_head;     // Delete the previous element.
            m_head = temp;     // m_head moved one forward.
        }
    }

    // Assignment operator using copy-and-swap idiom.
    LinkedList& operator=(const LinkedList<T>& other)
    {
        if (&other != this)
        {
            LinkedList<T> temp(other);

            /*Unhandled exception at 0x00007FF9DEC58739 (ucrtbased.dll) in List.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x0000009A1D6F3FE8).*/
            swap(*this, temp);
        }

        return *this;
    }

    auto head() const
    {
        return m_head;
    }

    auto tail() const
    {
        return m_tail;
    }

    bool empty() const
    {
        return m_size == 0;
    }

    int size() const
    {
        return m_size;
    }

    void prepend(const T& item)
    {
        // Create a node holding our item and pointing to the head.
        auto new_item = new Node<T>{item, m_head};

        // If the head is the last element
        // (meaning it is the only element),
        // it'll be the tail.
        if (m_head == nullptr)
        {
            m_tail = m_head;
        }

        m_head = new_item;
        m_size++;
    }

    void append(const T& item)
    {
        // Create a node with no pointer.
        auto new_item = new Node<T>{item};

        if (m_tail == nullptr)
        {
            // If the list is empty, set the new item as the head as well.
            m_head = new_item;
            m_tail = new_item;
        }
        else
        {
            // Otherwise, update the current tail's next pointer to the new item and move the tail.
            m_tail->next = new_item;
            m_tail = new_item;
        }

        m_size++;
    }

    // Avoid illegal indexes by making pos unsigned.
    void insert(const unsigned pos, const T& item)
    {
        // If the position is the beginning of the list, prepend the new node.
        if (pos == 0)
        {
            prepend(item);
        }
        // If the position is beyond the end of the list, append the new node.
        else if (static_cast<int>(pos) >= m_size)
        {
            append(item);
        }
        else
        {
            // Create a new node.
            auto new_item = new Node<T>{item};

            // Starting from the head, go to the one past the position.
            auto temp = m_head;
            for (int i{}; i < static_cast<int>(pos) - 1; ++i)
            {
                temp = temp->next;
            }

            new_item->next = temp->next; // Link the new_item to the one after the temp.
            temp->next = new_item;       // Link temp to the new_item.

            m_size++;
        }
    }

    void remove_front()
    {
        Node<T>* temp = m_head;

        // If there's no element, exit.
        if (m_head == nullptr)
        {
            return;
        }

        m_head = m_head->next; // Move m_head one element forward.
        delete temp;           // Get rid of the previous element.

        m_size--;
    }

    void remove_back()
    {
        Node<T>* temp = m_head;

        if (temp == nullptr)
        {
            return;
        }

        // If the list's size is 1.
        if (temp == m_tail)
        {
            delete temp;
            m_head = m_tail = nullptr;

            --m_size;

            return;
        }

        // Traverse to one before the end.
        while (temp->next != m_tail)
        {
            temp = temp->next;
        }

        m_tail = temp;
        //temp = temp->next;
        delete temp->next;

        m_tail->next = nullptr;

        --m_size;
    }

    // Avoid illegal indexes by making pos unsigned.
    T remove(const unsigned pos)
    {
        Node<T>* temp = m_head;

        // Go to the one past the pos.
        for (int i{}; i < static_cast<int>(pos) - 1; ++i)
        {
            temp = temp->next;
        }

        // The element to be removed.
        auto to_removed = temp->next;
        // Link the current node one after the to_removed.
        temp->next = temp->next->next;

        T removed_data = to_removed->data; // Retrieve the data before deleting the node.

        delete to_removed; // Delete the to_removed.
        m_size--;          // Don't forget to decrement the size.

        return removed_data;
    }

    T& operator[](const int pos)
    {
        Node<T>* temp = m_head;

        for (int i{}; i != pos; ++i)
        {
            temp = temp->next;
        }

        return temp->data;
    }

    const T& operator[](const int pos) const
    {
        Node<T>* temp = m_head;

        for (int i{}; i != pos; ++i)
        {
            temp = temp->next;
        }

        return temp->data;
    }
};

template <typename T>
std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list)
{
    for (auto begin = list.head(); begin != nullptr; begin = begin->next)
    {
        os << begin->data << ' ';
    }
    return os;
}

#endif // LINKEDLIST_HPP

型
ArrayList.hpp:

// An array-based approach of list.
#ifndef ARRAYLIST_HPP
#define ARRAYLIST_HPP

#include "List.hpp"
#include <cassert>

const int GROWTH_FACTOR = 2;

template <typename T>
class ArrayList: public List<T>
{
private:
    int m_capacity{};     // Maximum size of list.
    int m_size{};         // Current number of list elements.
    T*  m_list_array{};   // Array holding list of elements.

    void reserve()
    {
        m_capacity *= GROWTH_FACTOR;
        T* temp = new T[m_capacity];   // Allocate new array in the heap.

        for (int i{}; i < m_size; ++i)
        {
            temp[i] = m_list_array[i]; // Copy all items of original array.
        }
        
        delete[] m_list_array;         // Get rid of the original array.
        m_list_array = temp;           // "temp" is our new array now.
    }

public:
    ArrayList() = default;

    ArrayList(int size)
        : m_capacity{size*GROWTH_FACTOR},
        m_size{size},
        m_list_array{new T[m_capacity] {}} // ArrayList elements are zero initialized by default.
    {
    }

    ArrayList(std::initializer_list<T> i_list)
        : ArrayList(static_cast<int>(i_list.size())) 
        // Don't use braces as initializer_list constructor uses it.
        // Otherwise this constructor would call itself.
    {
        int count{};
        for (const auto& item : i_list)
        {
            m_list_array[count] = item;
            count++;
        }
    }

    // Copy constructor.
    /*
     * Rule of Three:
     * If a class requires a user-defined destructor, 
     * a user-defined copy constructor, 
     * or a user-defined copy assignment operator, 
     * it almost certainly requires all three.
     */
    ArrayList(const ArrayList& other)
        : List<T>{},
        m_capacity{other.m_capacity},
        m_size{other.m_size},
        m_list_array{new T[other.m_capacity] {}}
    {
        for (int i{}; i < m_size; ++i)
        {
            m_list_array[i] = other.m_list_array[i];
        }
    }

    ~ArrayList()
    {
        delete[] m_list_array;
    }

    ArrayList& operator=(const ArrayList& other)
    {
        // Check for self-assignment.
        if (this != &other)
        {
            // Deallocate the existing array.
            delete[] m_list_array;

            // Copy the capacity and size.
            m_capacity = other.m_capacity;
            m_size = other.m_size;

            // Allocate a new array.
            m_list_array = new T[m_capacity];

            // Copy the elements from the other ArrayList.
            for (int i{}; i < m_size; ++i)
            {
                m_list_array[i] = other.m_list_array[i];
            }
        }
        return *this;
    }

    // initializer_list assignment.
    ArrayList& operator=(std::initializer_list<T> i_list)
    {
        // Array's new size is the i_list's size now.
        m_size = static_cast<int>(i_list.size());

        // reserve(), but without copying items because they'll been assigned from i_list.
        if (m_capacity < m_size)
        {
            m_capacity *= GROWTH_FACTOR;
            T* temp = new T[m_capacity] {};   // Allocate new array in the heap, with zero values.

            delete[] m_list_array;            // Get rid of the original array.
            m_list_array = temp;              // "temp" is our new array now.
        }

        // Copy the i_list's items to our array's.
        int count{};
        for (const auto& item : i_list)
        {
            m_list_array[count] = item;
            count++;
        }

        return *this;
    }

    void clear()
    {
        delete[] m_list_array;              // Remove the array.
        //m_size = 0;                         // Reset the size.

        m_list_array = new T[m_capacity] {}; // Recreate array.
    }

    // Insert "item" at given position.
    void insert(const unsigned pos, const T& item)// override
    {
        if (m_size == m_capacity)
        {
            reserve();
        }
        assert(static_cast<int>(pos) < m_size && "Out of range.\n");

        for (int s{m_size}; static_cast<int>(pos) < s; --s)        // Shift elements up...
        {
            m_list_array[s] = m_list_array[s - 1]; // ...to make room.
        }
        ///DEMONSTRATION
        //┌────┬────┬────┬────┬────┬────┬────┐
        //│i[0]│i[1]│i[2]│i[3]│i[4]│i[5]│i[6]│     // INDEXES
        //├────┼────┼────┼────┼────┼────┼────┤
        //│10  │20  │30  │40  │50  │60  │    │     // ITEMS
        //├────┼────┼────┼────┼────┼────┼────┤
        //│    │10  │20  │30  │40  │50  │60  │     // SHIFT ELEMENTS UP
        //├────┼────┼────┼────┼────┼────┼────┤
        //│item│10  │20  │30  │40  │50  │60  │     // INSERT "item"
        //└────┴────┴────┴────┴────┴────┴────┘
        //
        m_list_array[pos] = item;

        m_size++;                                  // Increment list size.
    }

    // Append "item".
    void append(const T& item) override
    {
        if (m_size == m_capacity)
        {
            reserve();
        }
        //assert(m_size < m_capacity && "List capacity exceeded.\n");

        m_list_array[m_size] = item;
        m_size++;
    }

    // Remove and return the current element.
    T remove(const unsigned pos) override
    {
        assert(static_cast<int>(pos) < m_size && "No element.\n");

        T item = m_list_array[pos];                // Copy the item.

        // m_size - 1, because we're dealing with array indexes (array[size] is out of bounds).
        for (int i{static_cast<int>(pos)}; i < m_size - 1; ++i)
        {
            m_list_array[i] = m_list_array[i + 1]; // Shift elements down.
        }
        ///DEMONSTRATION
        //┌────┬────┬────┬────┬────┬────┬────┐
        //│i[0]│i[1]│i[2]│i[3]│i[4]│i[5]│i[6]│     // INDEXES
        //├────┼────┼────┼────┼────┼────┼────┤
        //│10  │item│20  │30  │40  │50  │60  │     // ITEMS
        //├────┼────┼────┼────┼────┼────┼────┤
        //│10  │20  │30  │40  │50  │60  │... │     // SHIFT ELEMENTS DOWN
        //└────┴────┴────┴────┴────┴────┴────┘
        //
        m_size--;                                  // Decrement size.

        return item;
    }

    // Return list size.
    int size() const override
    {
        return m_size;
    }

    bool empty() const
    {
        return size() == 0;
    }

    T& operator[](const int pos) override
    {
        assert(!empty() && "No current element.\n");
        return m_list_array[pos];
    }

    const T& operator[](const int pos) const override
    {
        assert(!empty() && "No current element.\n");
        return m_list_array[pos];
    }
};
#endif // ARRAYLIST_HPP

型
List.hpp:

// This is a blueprint for all list-like data structures.
// It won't specify how the operations are carried out.
#ifndef LIST_HPP
#define LIST_HPP

#include <initializer_list>

template <typename T>
class List
{
public:
    List()
    {}

    virtual ~List()
    {}

    List(const List&)
    {}

    virtual void insert(unsigned pos, const T& item) = 0;
    virtual void append(const T& item) = 0;

    virtual T remove(const unsigned pos) = 0;

    virtual int size() const = 0;

    virtual T& operator[](const int pos) = 0;
    // The const overload is called only when used on const object.
    virtual const T& operator[](const int pos) const = 0;

};
#endif // LIST_HPP

型
Node.hpp:

#ifndef NODE_HPP
#define NODE_HPP

template <typename T>
struct Node
{
    T data{};            // Value of the node.
    Node* next{nullptr}; // Pointer to the next node.

    Node(const T& dat, Node* nxt = nullptr)
        : data{dat}, next{nxt}
    {}
};

#endif // NODE_HPP

型
Source.cpp:

#include "LinkedList.hpp"
#include "ArrayList.hpp"

#include <fstream>
#include <iostream>
#include <string>

#define TO_DIGIT(x) (x) - ('0')

template <typename T>
std::ostream& operator<<(std::ostream& os, const List<T>& list)
{
    for (int i{}, s{list.size()}; i < s; ++i)
    {
        os << list[i] << ' ';
    }
    return os;
}

int main()
{
    std::ifstream fin("number.txt");

    if (!fin.good())
    {
        return -1;
    }

    std::string num{};
    ArrayList<LinkedList<int>> arr{};

    while (fin >> num)
    {
        LinkedList<int> list{};
        for (const char& ch : num)
        {
            list.prepend(TO_DIGIT(ch));
        }

        arr.append(list);
    }

    std::cout << arr;
}

型

c++

2条答案

按热度按时间
tvokkenx

tvokkenx1#

我修复了你的代码中的几个bug。即：

  • 从LinkedList中删除了那些swap函数。然后修复了LinkedList重载的赋值操作符，以执行正确的复制而不是交换操作。

而不是这样：

// Assignment operator using copy-and-swap idiom.
    LinkedList& operator=(const LinkedList<T>& other)
    {
        if (&other != this)
        {
            LinkedList<T> temp(other);
            swap(*this, temp);
        }

        return *this;
    }

字符串
这一点：

LinkedList& operator=(const LinkedList<T>& other)
    {
        if (&other != this)
        {
            while (m_size > 0) {
                remove_back();
            }

            auto other_head = other.m_head;
            while (other_head != nullptr) {
                append(other_head->data);
                other_head = other_head->next;
            }
        }

        return *this;
    }

型

  • 在LinkedList中的几个地方，m_size被递减，但是当这种情况发生时，您忘记将m_head和m_tail设置为nullptr。
  • ArrayList中的reserve方法需要一个快速修复来处理容量最初为零的情况。在这种情况下，简单的修复方法是将大小增加到2。
  • 删除了ArrayList中大部分重载的复制构造函数和赋值运算符。它们没有被使用，我不相信它们是必要的。你可以把它们加回去，但我不相信这不是一个bug的来源。

在所有这些之后，你的代码似乎工作。
下面是经过上述修复后的代码。

template <typename T>
class List
{
public:
    List()
    {}

    virtual ~List()
    {}

    List(const List&)
    {}

    virtual void insert(unsigned pos, const T& item) = 0;
    virtual void append(const T& item) = 0;

    virtual T remove(const unsigned pos) = 0;

    virtual int size() const = 0;

    virtual T& operator[](const int pos) = 0;
    // The const overload is called only when used on const object.
    virtual const T& operator[](const int pos) const = 0;

};

template <typename T>
struct Node
{
    T data{};            // Value of the node.
    Node* next{ nullptr }; // Pointer to the next node.

    Node(const T& dat, Node* nxt = nullptr)
        : data{ dat }, next{ nxt }
    {}
};

const int GROWTH_FACTOR = 2;

template <typename T>
class ArrayList : public List<T>
{
private:
    int m_capacity{};     // Maximum size of list.
    int m_size{};         // Current number of list elements.
    T* m_list_array{};   // Array holding list of elements.

    void reserve()
    {
        m_capacity *= GROWTH_FACTOR;
        if (m_capacity == 0) {
            m_capacity = 2;
        }
        T* temp = new T[m_capacity];   // Allocate new array in the heap.

        for (int i{}; i < m_size; ++i)
        {
            temp[i] = m_list_array[i]; // Copy all items of original array.
        }

        delete[] m_list_array;         // Get rid of the original array.
        m_list_array = temp;           // "temp" is our new array now.
    }

public:
    ArrayList() = default;

    ~ArrayList()
    {
        delete[] m_list_array;
    }

    void clear()
    {
        delete[] m_list_array;
        m_list_array = nullptr;
        m_capacity = 0;
        m_size = 0;
    }

    // Insert "item" at given position.
    void insert(const unsigned pos, const T& item)// override
    {
        if (m_size == m_capacity)
        {
            reserve();
        }
        assert(static_cast<int>(pos) < m_size && "Out of range.\n");

        for (int s{ m_size }; static_cast<int>(pos) < s; --s)        // Shift elements up...
        {
            m_list_array[s] = m_list_array[s - 1]; // ...to make room.
        }
        ///DEMONSTRATION
        //┌────┬────┬────┬────┬────┬────┬────┐
        //│i[0]│i[1]│i[2]│i[3]│i[4]│i[5]│i[6]│     // INDEXES
        //├────┼────┼────┼────┼────┼────┼────┤
        //│10  │20  │30  │40  │50  │60  │    │     // ITEMS
        //├────┼────┼────┼────┼────┼────┼────┤
        //│    │10  │20  │30  │40  │50  │60  │     // SHIFT ELEMENTS UP
        //├────┼────┼────┼────┼────┼────┼────┤
        //│item│10  │20  │30  │40  │50  │60  │     // INSERT "item"
        //└────┴────┴────┴────┴────┴────┴────┘
        //
        m_list_array[pos] = item;

        m_size++;                                  // Increment list size.
    }

    // Append "item".
    void append(const T& item) override
    {
        if (m_size == m_capacity)
        {
            reserve();
        }
        //assert(m_size < m_capacity && "List capacity exceeded.\n");

        m_list_array[m_size] = item;
        m_size++;
    }

    // Remove and return the current element.
    T remove(const unsigned pos) override
    {
        assert(static_cast<int>(pos) < m_size && "No element.\n");

        T item = m_list_array[pos];                // Copy the item.

        // m_size - 1, because we're dealing with array indexes (array[size] is out of bounds).
        for (int i{ static_cast<int>(pos) }; i < m_size - 1; ++i)
        {
            m_list_array[i] = m_list_array[i + 1]; // Shift elements down.
        }
        ///DEMONSTRATION
        //┌────┬────┬────┬────┬────┬────┬────┐
        //│i[0]│i[1]│i[2]│i[3]│i[4]│i[5]│i[6]│     // INDEXES
        //├────┼────┼────┼────┼────┼────┼────┤
        //│10  │item│20  │30  │40  │50  │60  │     // ITEMS
        //├────┼────┼────┼────┼────┼────┼────┤
        //│10  │20  │30  │40  │50  │60  │... │     // SHIFT ELEMENTS DOWN
        //└────┴────┴────┴────┴────┴────┴────┘
        //
        m_size--;                                  // Decrement size.

        return item;
    }

    // Return list size.
    int size() const override
    {
        return m_size;
    }

    bool empty() const
    {
        return size() == 0;
    }

    T& operator[](const int pos) override
    {
        assert(!empty() && "No current element.\n");
        return m_list_array[pos];
    }

    const T& operator[](const int pos) const override
    {
        assert(!empty() && "No current element.\n");
        return m_list_array[pos];
    }
};

template <typename T>
class LinkedList : public List<T>
{
private:
    Node<T>* m_head{ nullptr };
    Node<T>* m_tail{ nullptr };

    int m_size{};

public:
    LinkedList() = default;

    LinkedList(std::initializer_list<T> i_list)
    {
        for (const auto& item : i_list)
        {
            append(item);
        }
    }

    // Copy constructor.
    LinkedList(const LinkedList<T>& other) : List<T>{}
    {
        auto temp = other.m_head;

        while (temp != nullptr)
        {
            append(temp->data);
            temp = temp->next;
        }
    }

    ~LinkedList()
    {
        // Start from the beginning.
        Node<T>* temp = m_head;

        // Traverse the list while deleting previous elements.
        while (temp != nullptr)
        {
            temp = temp->next; // Move forward.
            delete m_head;     // Delete the previous element.
            m_head = temp;     // m_head moved one forward.
        }
    }

    // Assignment operator using copy-and-swap idiom.
    LinkedList& operator=(const LinkedList<T>& other)
    {
        if (&other != this)
        {
            while (m_size > 0) {
                remove_back();
            }

            auto other_head = other.m_head;
            while (other_head != nullptr) {
                append(other_head->data);
                other_head = other_head->next;
            }
        }

        return *this;
    }

    auto head() const
    {
        return m_head;
    }

    auto tail() const
    {
        return m_tail;
    }

    bool empty() const
    {
        return m_size == 0;
    }

    int size() const
    {
        return m_size;
    }

    void prepend(const T& item)
    {
        // Create a node holding our item and pointing to the head.
        auto new_item = new Node<T>{ item, m_head };

        // If the head is the last element
        // (meaning it is the only element),
        // it'll be the tail.
        if (m_head == nullptr)
        {
            m_tail = m_head;
        }

        m_head = new_item;
        m_size++;
    }

    void append(const T& item)
    {
        // Create a node with no pointer.
        auto new_item = new Node<T>{ item };

        if (m_tail == nullptr)
        {
            // If the list is empty, set the new item as the head as well.
            m_head = new_item;
            m_tail = new_item;
        }
        else
        {
            // Otherwise, update the current tail's next pointer to the new item and move the tail.
            m_tail->next = new_item;
            m_tail = new_item;
        }

        m_size++;
    }

    // Avoid illegal indexes by making pos unsigned.
    void insert(const unsigned pos, const T& item)
    {
        // If the position is the beginning of the list, prepend the new node.
        if (pos == 0)
        {
            prepend(item);
        }
        // If the position is beyond the end of the list, append the new node.
        else if (static_cast<int>(pos) >= m_size)
        {
            append(item);
        }
        else
        {
            // Create a new node.
            auto new_item = new Node<T>{ item };

            // Starting from the head, go to the one past the position.
            auto temp = m_head;
            for (int i{}; i < static_cast<int>(pos) - 1; ++i)
            {
                temp = temp->next;
            }

            new_item->next = temp->next; // Link the new_item to the one after the temp.
            temp->next = new_item;       // Link temp to the new_item.

            m_size++;
        }
    }

    void remove_front()
    {
        Node<T>* temp = m_head;

        // If there's no element, exit.
        if (m_head == nullptr)
        {
            return;
        }

        m_head = m_head->next; // Move m_head one element forward.
        delete temp;           // Get rid of the previous element.

        m_size--;

        if (m_size == 0) {
            m_head = nullptr;
            m_tail = nullptr;
        }
    }

    void remove_back()
    {
        Node<T>* temp = m_head;

        if (temp == nullptr)
        {
            return;
        }

        // If the list's size is 1.
        if (temp == m_tail)
        {
            delete temp;
            m_head = m_tail = nullptr;

            --m_size;

            return;
        }

        // Traverse to one before the end.
        while (temp->next != m_tail)
        {
            temp = temp->next;
        }

        m_tail = temp;
        //temp = temp->next;
        delete temp->next;

        m_tail->next = nullptr;

        --m_size;
    }

    // Avoid illegal indexes by making pos unsigned.
    T remove(const unsigned pos)
    {
        Node<T>* temp = m_head;

        // Go to the one past the pos.
        for (int i{}; i < static_cast<int>(pos) - 1; ++i)
        {
            temp = temp->next;
        }

        // The element to be removed.
        auto to_removed = temp->next;
        // Link the current node one after the to_removed.
        temp->next = temp->next->next;

        T removed_data = to_removed->data; // Retrieve the data before deleting the node.

        delete to_removed; // Delete the to_removed.
        m_size--;          // Don't forget to decrement the size.

        if (m_size == 0) {
            m_head = nullptr;
            m_tail = nullptr;
        }

        return removed_data;
    }

    T& operator[](const int pos)
    {
        Node<T>* temp = m_head;

        for (int i{}; i != pos; ++i)
        {
            temp = temp->next;
        }

        return temp->data;
    }

    const T& operator[](const int pos) const
    {
        Node<T>* temp = m_head;

        for (int i{}; i != pos; ++i)
        {
            temp = temp->next;
        }

        return temp->data;
    }
};

型

赞(0）分享  回复(0）举报  8个月前
col17t5w

col17t5w2#

我从Visual Studio得到这个错误：
List.exe中0x 00007 FF 9 E8 AF 8739（ucrtbased.dll）处的未处理异常：0xC 00000 FD：堆栈溢出（参数：0x 0000000000001，0x0000007E 50 C13 FF 8）。
我不知道这是怎么回事。我试图实现复制和交换的习惯用法。
swap函数需要重写。它应该交换LinkedList类的 * 成员 *，而不是LinkedList对象本身。
就目前的情况而言，swap函数调用赋值运算符，赋值运算符又调用swap，swap又调用赋值运算符，依此类推。

void swap(LinkedList<T>& a, LinkedList<T>& b)
    {
        // ERROR - Infinite recursion
        LinkedList<T> temp = a;
        a = b;
        b = temp;
    }

字符串
此外，您应该将交换函数编码为noexcept，并使用移动操作来实现交换。
你的程序中还有其他几个错误。answer by @selbie很好地解释了细节。

无需继承

一个更深层次的问题是整体设计。使用继承来创建类ArrayList比你需要的要复杂得多。想想如果你使用的是std::vector和std::forward_list，而不是自定义类，你会如何编写这个代码。不会有继承。相反，你会创建一个列表的向量：

std::vector<std::forward_list<int>> arr;

型
您的自定义类应该以同样的方式 * 可组合 *。

使用std::vector和std::forward_list编写函数main

解决这个问题的一种方法是使用std::vector和std::forward_list编写一个解决方案。当你可以使用它时，你可以用你自己设计的类来替换它们。
在下面的代码片段中，宏USE_STD允许您在标准库类和自定义替换之间进行选择。

  • 当USE_STD == 1时，程序使用std::vector和std::forward_list。
  • 当USE_STD == 0时，程序使用tbx::cpp23::Vector和tbx::cpp23::Forward_List。
// main.ixx
module;
#define USE_STD 0
export module main;
import std;

#if USE_STD
    template< typename T >
    using Forward_List = std::forward_list<T>;

    template< typename T >
    using Vector = std::vector<T>;
#else
    import tbx.cpp23.Forward_List;
    import tbx.cpp23.Vector;

    template< typename T >
    using Forward_List = tbx::cpp23::Forward_List<T>;

    template< typename T >
    using Vector = tbx::cpp23::Vector<T>;
#endif

// ...

型
从这一点开始，使用类型别名：Vector和Forward_List。例如，这个定义来自函数main：

Vector<Forward_List<int>> arr;

型

流插入操作符

宏USE_STD也可以用来选择要使用的operator<<版本。

#if USE_STD
    std::ostream& operator<< (
        std::ostream& ost,
        Forward_List<int> const list)
    {
        for (auto const& item : list)
            ost << item << ' ';
        ost << '\n';
        return ost;
    }
#else
    // The implementation of `tbx::cpp23::Forward_List<T>` defines 
    // `operator<<` as a hidden friend. No definition is needed here.
#endif

std::ostream& operator<< (
    std::ostream& ost,
    Vector<Forward_List<int>> const vec)
{
    for (auto const& list : vec)
        ost << list;
    ost.put('\n');
    return ost;
}

型

main函数源代码

这是函数main的源代码。因为它使用了类型别名Forward_List和Vector，所以它可以与标准库类和它们的自定义替换一起使用。

export int main()
{
    enum : int { no_errors, create_error, open_error, skipped_number };
    int exit_code = no_errors;

    // numbers.txt
    // This is the input file.
    std::string file_name_numbers{ "number.txt" };

    // skipped.txt
    // Invalid "numbers" are written to this file.
    std::string file_name_skipped_numbers{ "skipped.txt" };

    if (!create_file_numbers(file_name_numbers, 3))
    {
        std::cerr << "ERROR - Could not create file: \""
            + file_name_numbers + '"';
        return create_error;
    }

    std::ifstream ist(file_name_numbers);
    if (!ist.is_open())
    {
        std::cerr << "ERROR - Could not open file: \""
            + file_name_numbers + '"';
        return open_error;
    }

    std::ofstream log(file_name_skipped_numbers);
    if (!log.is_open())
    {
        std::cerr << "ERROR - Could not open file: \""
            + file_name_skipped_numbers + '"';
        return open_error;
    }

    Vector<Forward_List<int>> arr;

    std::string num{};
    while (ist >> num)
    {
        if (is_digit_string(num))
        {
            // Note: This loop duplicates the action of the OP.
            // It reverses the order of the digits. Thus, the MSD
            // is pushed onto the front of the list first, followed 
            // by the other digits. It would be easy to parse string 
            // `num` in reverse order, and thereby create a list with 
            // the digits in their original order.
            Forward_List<int> list;
            for (const char& ch : num)
                list.push_front(digit_to_int(ch));
            arr.push_back(list);
        }
        else
        {
            std::cerr
                << "ERROR - Skipping invalid number in input file: "
                << num
                << '\n';
            log << num << '\n';
            exit_code = skipped_number;
        }
    }
    ist.close();
    log.close();
    std::cout << arr;
    return exit_code;
}

型

Helper函数

函数main调用这些辅助函数：

bool create_file_numbers(
    std::string const& file_name,
    int n = 5)
{
    // This file is not described in the OP at StackOverflow.
    // Judging by how it is used, the file is comprised of a series 
    // of non-negative integer values (without any sign, + or -), 
    // separated by whitespace. 
    // 
    // For convenience, let's suppose there is one number per line.

    std::ofstream ost{ file_name };
    if (!ost.is_open())
        return false;
    std::mt19937 mt{ std::random_device{}() };
    std::uniform_int_distribution<int> dist{ 0, 99'999 };
    while (n--)
        ost << dist(mt) << '\n';
    ost.close();
    return true;
}

int digit_to_int(char const c) {
    return c - '0';
}

bool is_digit_string(std::string_view sv) noexcept
{
    for (char const& c : sv)
        if (!std::isdigit(static_cast<unsigned char const>(c)))
            return false;
    return !sv.empty();
}

型

编写自定义类的技巧

自定义类Forward_List和Vector都应该遵循Rule of Five。
除此之外，您可以通过只编写您使用的成员函数来简化任务。不需要实现std::forward_list和std::vector的完整接口。

  • 函数main调用列表上的push_front和向量上的push_back。不使用其他成员函数。
  • 对于向量，operator<<使用了一个 * 基于范围的for循环 *。为了使其工作，必须编写成员函数cbegin和cend。在我的实现中，它们只是返回指针，而不是完整的迭代器。
  • 对于列表，operator<<还需要实现成员函数cbegin和cend。
  • 该列表还有一个补充的Node类，它在内部使用，但不向客户端公开。
  • 对于这个列表，我写了一个迭代器类。在内部，迭代器类存储一个指向Node的指针。当你递增迭代器时，指针也会递增。然而，当你解引用迭代器时，它不会返回Node;它返回一个对结构Node中value字段的引用。

我使用import和模块编写了演示程序，但同样的解决方案也可以使用常规的#include指令编写。
模块tbx.cpp23.Forward_List定义类模板tbx::cpp23::Forward_List<T>。

// Forward_List.ixx
export module tbx.cpp23.Forward_List;
export namespace tbx::cpp23
{
    template< typename T >
    class Forward_List
    {
    public:
        using value_type = T;

    private:
        struct Node
        {
            value_type value{};
            Node* next{ nullptr };
            bool operator== (Node const& that) const {
                return this->value == that.value;
            }
        };

        Node *head{}, *tail{};

    public:
        struct Iterator
        {
            // ...
        };
        // ...
    };
}

型
模块tbx.cpp23.Vector定义类模板tbx::cpp23::Vector<T>。

// Vector.ixx
export module tbx.cpp23.Vector;
export namespace tbx::cpp23
{
    template< typename T >
    class Vector
    {
    public:
        using value_type = T;
        using size_type = std::size_t;
        using iterator = value_type*;
        using const_iterator = value_type const*;

    private:
        size_type capacity_{};
        size_type size_{};
        value_type* data_{ nullptr };
        enum : size_type { zero, one, two };

    public:
        // ...
    };
}

型

演示程序

这里是文件main.ixx的完整源代码。模块Forward_List和Vector的源代码已被省略。不得不留下一些乐趣给你！
首先，我测试了USE_STD设置为1。后来，我测试了它设置为0。演示工作的两种方式。

// main.ixx
module;
#define USE_STD 0
export module main;
import std;

#if USE_STD
    template< typename T >
    using Forward_List = std::forward_list<T>;

    template< typename T >
    using Vector = std::vector<T>;
#else
    import tbx.cpp23.Forward_List;
    import tbx.cpp23.Vector;

    template< typename T >
    using Forward_List = tbx::cpp23::Forward_List<T>;

    template< typename T >
    using Vector = tbx::cpp23::Vector<T>;
#endif

#if USE_STD
    std::ostream& operator<< (
        std::ostream& ost,
        Forward_List<int> const list)
    {
        for (auto const& item : list)
            ost << item << ' ';
        ost << '\n';
        return ost;
    }
#else
    // The implementation of `tbx::cpp23::Forward_List<T>` defines 
    // `operator<<` as a hidden friend. No definition is needed here.
#endif

std::ostream& operator<< (
    std::ostream& ost,
    Vector<Forward_List<int>> const vec)
{
    for (auto const& list : vec)
        ost << list;
    ost.put('\n');
    return ost;
}

bool create_file_numbers(
    std::string const& file_name,
    int n = 5)
{
    // This file is not described in the OP at StackOverflow.
    // Judging by how it is used, the file is comprised of a series 
    // of non-negative integer values (without any sign, + or -), 
    // separated by whitespace. 
    // 
    // For convenience, let's suppose there is one number per line.

    std::ofstream ost{ file_name };
    if (!ost.is_open())
        return false;
    std::mt19937 mt{ std::random_device{}() };
    std::uniform_int_distribution<int> dist{ 0, 99'999 };
    while (n--)
        ost << dist(mt) << '\n';
    ost.close();
    return true;
}

int digit_to_int(char const c) {
    return c - '0';
}

bool is_digit_string(std::string_view sv) noexcept
{
    for (char const& c : sv)
        if (!std::isdigit(static_cast<unsigned char const>(c)))
            return false;
    return !sv.empty();
}

export int main()
{
    enum : int { no_errors, create_error, open_error, skipped_number };
    int exit_code = no_errors;

    // numbers.txt
    // This is the input file.
    std::string file_name_numbers{ "number.txt" };

    // skipped.txt
    // Invalid "numbers" are written to this file.
    std::string file_name_skipped_numbers{ "skipped.txt" };

    if (!create_file_numbers(file_name_numbers, 3))
    {
        std::cerr << "ERROR - Could not create file: \""
            + file_name_numbers + '"';
        return create_error;
    }

    std::ifstream ist(file_name_numbers);
    if (!ist.is_open())
    {
        std::cerr << "ERROR - Could not open file: \""
            + file_name_numbers + '"';
        return open_error;
    }

    std::ofstream log(file_name_skipped_numbers);
    if (!log.is_open())
    {
        std::cerr << "ERROR - Could not open file: \""
            + file_name_skipped_numbers + '"';
        return open_error;
    }

    Vector<Forward_List<int>> arr;

    std::string num{};
    while (ist >> num)
    {
        if (is_digit_string(num))
        {
            // Note: This loop duplicates the action of the OP.
            // It reverses the order of the digits. Thus, the MSD
            // is pushed onto the front of the list first, followed 
            // by the other digits. It would be easy to parse string 
            // `num` in reverse order, and thereby create a list with 
            // the digits in their original order.
            Forward_List<int> list;
            for (const char& ch : num)
                list.push_front(digit_to_int(ch));
            arr.push_back(list);
        }
        else
        {
            std::cerr
                << "ERROR - Skipping invalid number in input file: "
                << num
                << '\n';
            log << num << '\n';
            exit_code = skipped_number;
        }
    }
    ist.close();
    log.close();
    std::cout << arr;
    return exit_code;
}
// end file: main.ixx

型

赞(0）分享  回复(0）举报  8个月前
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com