当我尝试打印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;
}
型
2条答案
按热度按时间tvokkenx1#
我修复了你的代码中的几个bug。即:
swap
函数。然后修复了LinkedList重载的赋值操作符,以执行正确的复制而不是交换操作。而不是这样:
字符串
这一点:
型
m_size
被递减,但是当这种情况发生时,您忘记将m_head和m_tail设置为nullptr。reserve
方法需要一个快速修复来处理容量最初为零的情况。在这种情况下,简单的修复方法是将大小增加到2。在所有这些之后,你的代码似乎工作。
下面是经过上述修复后的代码。
型
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又调用赋值运算符,依此类推。
字符串
此外,您应该将交换函数编码为
noexcept
,并使用移动操作来实现交换。你的程序中还有其他几个错误。answer by @selbie很好地解释了细节。
无需继承
一个更深层次的问题是整体设计。使用继承来创建类
ArrayList
比你需要的要复杂得多。想想如果你使用的是std::vector
和std::forward_list
,而不是自定义类,你会如何编写这个代码。不会有继承。相反,你会创建一个列表的向量:型
您的自定义类应该以同样的方式 * 可组合 *。
使用
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
。型
从这一点开始,使用类型别名:
Vector
和Forward_List
。例如,这个定义来自函数main
:型
流插入操作符
宏
USE_STD
也可以用来选择要使用的operator<<
版本。型
main
函数源代码这是函数
main
的源代码。因为它使用了类型别名Forward_List
和Vector
,所以它可以与标准库类和它们的自定义替换一起使用。型
Helper函数
函数
main
调用这些辅助函数:型
编写自定义类的技巧
自定义类
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>
。型
模块
tbx.cpp23.Vector
定义类模板tbx::cpp23::Vector<T>
。型
演示程序
这里是文件
main.ixx
的完整源代码。模块Forward_List
和Vector
的源代码已被省略。不得不留下一些乐趣给你!首先,我测试了
USE_STD
设置为1
。后来,我测试了它设置为0
。演示工作的两种方式。型