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

xggvc2p6  于 2024-01-09  发布在  其他
关注(0)|答案(2)|浏览(158)

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

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

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

  1. #ifndef LINKEDLIST_HPP
  2. #define LINKEDLIST_HPP
  3. #include "List.hpp"
  4. #include "Node.hpp"
  5. #include <iostream> // operator<<
  6. template <typename T>
  7. class LinkedList: public List<T>
  8. {
  9. private:
  10. Node<T>* m_head{nullptr};
  11. Node<T>* m_tail{nullptr};
  12. int m_size{};
  13. void swap(T& a, T& b)
  14. {
  15. auto temp = a;
  16. a = b;
  17. b = temp;
  18. }
  19. void swap(LinkedList<T>& a, LinkedList<T>& b)
  20. {
  21. LinkedList<T> temp = a;
  22. a = b;
  23. b = temp;
  24. }
  25. public:
  26. LinkedList() = default;
  27. LinkedList(std::initializer_list<T> i_list)
  28. {
  29. for (const auto& item : i_list)
  30. {
  31. append(item);
  32. }
  33. }
  34. // Copy constructor.
  35. LinkedList(const LinkedList<T>& other) : List<T>{}
  36. {
  37. auto temp = other.m_head;
  38. while (temp != nullptr)
  39. {
  40. append(temp->data);
  41. temp = temp->next;
  42. }
  43. }
  44. ~LinkedList()
  45. {
  46. // Start from the beginning.
  47. Node<T>* temp = m_head;
  48. // Traverse the list while deleting previous elements.
  49. while (temp != nullptr)
  50. {
  51. temp = temp->next; // Move forward.
  52. delete m_head; // Delete the previous element.
  53. m_head = temp; // m_head moved one forward.
  54. }
  55. }
  56. // Assignment operator using copy-and-swap idiom.
  57. LinkedList& operator=(const LinkedList<T>& other)
  58. {
  59. if (&other != this)
  60. {
  61. LinkedList<T> temp(other);
  62. /*Unhandled exception at 0x00007FF9DEC58739 (ucrtbased.dll) in List.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x0000009A1D6F3FE8).*/
  63. swap(*this, temp);
  64. }
  65. return *this;
  66. }
  67. auto head() const
  68. {
  69. return m_head;
  70. }
  71. auto tail() const
  72. {
  73. return m_tail;
  74. }
  75. bool empty() const
  76. {
  77. return m_size == 0;
  78. }
  79. int size() const
  80. {
  81. return m_size;
  82. }
  83. void prepend(const T& item)
  84. {
  85. // Create a node holding our item and pointing to the head.
  86. auto new_item = new Node<T>{item, m_head};
  87. // If the head is the last element
  88. // (meaning it is the only element),
  89. // it'll be the tail.
  90. if (m_head == nullptr)
  91. {
  92. m_tail = m_head;
  93. }
  94. m_head = new_item;
  95. m_size++;
  96. }
  97. void append(const T& item)
  98. {
  99. // Create a node with no pointer.
  100. auto new_item = new Node<T>{item};
  101. if (m_tail == nullptr)
  102. {
  103. // If the list is empty, set the new item as the head as well.
  104. m_head = new_item;
  105. m_tail = new_item;
  106. }
  107. else
  108. {
  109. // Otherwise, update the current tail's next pointer to the new item and move the tail.
  110. m_tail->next = new_item;
  111. m_tail = new_item;
  112. }
  113. m_size++;
  114. }
  115. // Avoid illegal indexes by making pos unsigned.
  116. void insert(const unsigned pos, const T& item)
  117. {
  118. // If the position is the beginning of the list, prepend the new node.
  119. if (pos == 0)
  120. {
  121. prepend(item);
  122. }
  123. // If the position is beyond the end of the list, append the new node.
  124. else if (static_cast<int>(pos) >= m_size)
  125. {
  126. append(item);
  127. }
  128. else
  129. {
  130. // Create a new node.
  131. auto new_item = new Node<T>{item};
  132. // Starting from the head, go to the one past the position.
  133. auto temp = m_head;
  134. for (int i{}; i < static_cast<int>(pos) - 1; ++i)
  135. {
  136. temp = temp->next;
  137. }
  138. new_item->next = temp->next; // Link the new_item to the one after the temp.
  139. temp->next = new_item; // Link temp to the new_item.
  140. m_size++;
  141. }
  142. }
  143. void remove_front()
  144. {
  145. Node<T>* temp = m_head;
  146. // If there's no element, exit.
  147. if (m_head == nullptr)
  148. {
  149. return;
  150. }
  151. m_head = m_head->next; // Move m_head one element forward.
  152. delete temp; // Get rid of the previous element.
  153. m_size--;
  154. }
  155. void remove_back()
  156. {
  157. Node<T>* temp = m_head;
  158. if (temp == nullptr)
  159. {
  160. return;
  161. }
  162. // If the list's size is 1.
  163. if (temp == m_tail)
  164. {
  165. delete temp;
  166. m_head = m_tail = nullptr;
  167. --m_size;
  168. return;
  169. }
  170. // Traverse to one before the end.
  171. while (temp->next != m_tail)
  172. {
  173. temp = temp->next;
  174. }
  175. m_tail = temp;
  176. //temp = temp->next;
  177. delete temp->next;
  178. m_tail->next = nullptr;
  179. --m_size;
  180. }
  181. // Avoid illegal indexes by making pos unsigned.
  182. T remove(const unsigned pos)
  183. {
  184. Node<T>* temp = m_head;
  185. // Go to the one past the pos.
  186. for (int i{}; i < static_cast<int>(pos) - 1; ++i)
  187. {
  188. temp = temp->next;
  189. }
  190. // The element to be removed.
  191. auto to_removed = temp->next;
  192. // Link the current node one after the to_removed.
  193. temp->next = temp->next->next;
  194. T removed_data = to_removed->data; // Retrieve the data before deleting the node.
  195. delete to_removed; // Delete the to_removed.
  196. m_size--; // Don't forget to decrement the size.
  197. return removed_data;
  198. }
  199. T& operator[](const int pos)
  200. {
  201. Node<T>* temp = m_head;
  202. for (int i{}; i != pos; ++i)
  203. {
  204. temp = temp->next;
  205. }
  206. return temp->data;
  207. }
  208. const T& operator[](const int pos) const
  209. {
  210. Node<T>* temp = m_head;
  211. for (int i{}; i != pos; ++i)
  212. {
  213. temp = temp->next;
  214. }
  215. return temp->data;
  216. }
  217. };
  218. template <typename T>
  219. std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list)
  220. {
  221. for (auto begin = list.head(); begin != nullptr; begin = begin->next)
  222. {
  223. os << begin->data << ' ';
  224. }
  225. return os;
  226. }
  227. #endif // LINKEDLIST_HPP


ArrayList.hpp:

  1. // An array-based approach of list.
  2. #ifndef ARRAYLIST_HPP
  3. #define ARRAYLIST_HPP
  4. #include "List.hpp"
  5. #include <cassert>
  6. const int GROWTH_FACTOR = 2;
  7. template <typename T>
  8. class ArrayList: public List<T>
  9. {
  10. private:
  11. int m_capacity{}; // Maximum size of list.
  12. int m_size{}; // Current number of list elements.
  13. T* m_list_array{}; // Array holding list of elements.
  14. void reserve()
  15. {
  16. m_capacity *= GROWTH_FACTOR;
  17. T* temp = new T[m_capacity]; // Allocate new array in the heap.
  18. for (int i{}; i < m_size; ++i)
  19. {
  20. temp[i] = m_list_array[i]; // Copy all items of original array.
  21. }
  22. delete[] m_list_array; // Get rid of the original array.
  23. m_list_array = temp; // "temp" is our new array now.
  24. }
  25. public:
  26. ArrayList() = default;
  27. ArrayList(int size)
  28. : m_capacity{size*GROWTH_FACTOR},
  29. m_size{size},
  30. m_list_array{new T[m_capacity] {}} // ArrayList elements are zero initialized by default.
  31. {
  32. }
  33. ArrayList(std::initializer_list<T> i_list)
  34. : ArrayList(static_cast<int>(i_list.size()))
  35. // Don't use braces as initializer_list constructor uses it.
  36. // Otherwise this constructor would call itself.
  37. {
  38. int count{};
  39. for (const auto& item : i_list)
  40. {
  41. m_list_array[count] = item;
  42. count++;
  43. }
  44. }
  45. // Copy constructor.
  46. /*
  47. * Rule of Three:
  48. * If a class requires a user-defined destructor,
  49. * a user-defined copy constructor,
  50. * or a user-defined copy assignment operator,
  51. * it almost certainly requires all three.
  52. */
  53. ArrayList(const ArrayList& other)
  54. : List<T>{},
  55. m_capacity{other.m_capacity},
  56. m_size{other.m_size},
  57. m_list_array{new T[other.m_capacity] {}}
  58. {
  59. for (int i{}; i < m_size; ++i)
  60. {
  61. m_list_array[i] = other.m_list_array[i];
  62. }
  63. }
  64. ~ArrayList()
  65. {
  66. delete[] m_list_array;
  67. }
  68. ArrayList& operator=(const ArrayList& other)
  69. {
  70. // Check for self-assignment.
  71. if (this != &other)
  72. {
  73. // Deallocate the existing array.
  74. delete[] m_list_array;
  75. // Copy the capacity and size.
  76. m_capacity = other.m_capacity;
  77. m_size = other.m_size;
  78. // Allocate a new array.
  79. m_list_array = new T[m_capacity];
  80. // Copy the elements from the other ArrayList.
  81. for (int i{}; i < m_size; ++i)
  82. {
  83. m_list_array[i] = other.m_list_array[i];
  84. }
  85. }
  86. return *this;
  87. }
  88. // initializer_list assignment.
  89. ArrayList& operator=(std::initializer_list<T> i_list)
  90. {
  91. // Array's new size is the i_list's size now.
  92. m_size = static_cast<int>(i_list.size());
  93. // reserve(), but without copying items because they'll been assigned from i_list.
  94. if (m_capacity < m_size)
  95. {
  96. m_capacity *= GROWTH_FACTOR;
  97. T* temp = new T[m_capacity] {}; // Allocate new array in the heap, with zero values.
  98. delete[] m_list_array; // Get rid of the original array.
  99. m_list_array = temp; // "temp" is our new array now.
  100. }
  101. // Copy the i_list's items to our array's.
  102. int count{};
  103. for (const auto& item : i_list)
  104. {
  105. m_list_array[count] = item;
  106. count++;
  107. }
  108. return *this;
  109. }
  110. void clear()
  111. {
  112. delete[] m_list_array; // Remove the array.
  113. //m_size = 0; // Reset the size.
  114. m_list_array = new T[m_capacity] {}; // Recreate array.
  115. }
  116. // Insert "item" at given position.
  117. void insert(const unsigned pos, const T& item)// override
  118. {
  119. if (m_size == m_capacity)
  120. {
  121. reserve();
  122. }
  123. assert(static_cast<int>(pos) < m_size && "Out of range.\n");
  124. for (int s{m_size}; static_cast<int>(pos) < s; --s) // Shift elements up...
  125. {
  126. m_list_array[s] = m_list_array[s - 1]; // ...to make room.
  127. }
  128. ///DEMONSTRATION
  129. //┌────┬────┬────┬────┬────┬────┬────┐
  130. //│i[0]│i[1]│i[2]│i[3]│i[4]│i[5]│i[6]│ // INDEXES
  131. //├────┼────┼────┼────┼────┼────┼────┤
  132. //│10 │20 │30 │40 │50 │60 │ │ // ITEMS
  133. //├────┼────┼────┼────┼────┼────┼────┤
  134. //│ │10 │20 │30 │40 │50 │60 │ // SHIFT ELEMENTS UP
  135. //├────┼────┼────┼────┼────┼────┼────┤
  136. //│item│10 │20 │30 │40 │50 │60 │ // INSERT "item"
  137. //└────┴────┴────┴────┴────┴────┴────┘
  138. //
  139. m_list_array[pos] = item;
  140. m_size++; // Increment list size.
  141. }
  142. // Append "item".
  143. void append(const T& item) override
  144. {
  145. if (m_size == m_capacity)
  146. {
  147. reserve();
  148. }
  149. //assert(m_size < m_capacity && "List capacity exceeded.\n");
  150. m_list_array[m_size] = item;
  151. m_size++;
  152. }
  153. // Remove and return the current element.
  154. T remove(const unsigned pos) override
  155. {
  156. assert(static_cast<int>(pos) < m_size && "No element.\n");
  157. T item = m_list_array[pos]; // Copy the item.
  158. // m_size - 1, because we're dealing with array indexes (array[size] is out of bounds).
  159. for (int i{static_cast<int>(pos)}; i < m_size - 1; ++i)
  160. {
  161. m_list_array[i] = m_list_array[i + 1]; // Shift elements down.
  162. }
  163. ///DEMONSTRATION
  164. //┌────┬────┬────┬────┬────┬────┬────┐
  165. //│i[0]│i[1]│i[2]│i[3]│i[4]│i[5]│i[6]│ // INDEXES
  166. //├────┼────┼────┼────┼────┼────┼────┤
  167. //│10 │item│20 │30 │40 │50 │60 │ // ITEMS
  168. //├────┼────┼────┼────┼────┼────┼────┤
  169. //│10 │20 │30 │40 │50 │60 │... │ // SHIFT ELEMENTS DOWN
  170. //└────┴────┴────┴────┴────┴────┴────┘
  171. //
  172. m_size--; // Decrement size.
  173. return item;
  174. }
  175. // Return list size.
  176. int size() const override
  177. {
  178. return m_size;
  179. }
  180. bool empty() const
  181. {
  182. return size() == 0;
  183. }
  184. T& operator[](const int pos) override
  185. {
  186. assert(!empty() && "No current element.\n");
  187. return m_list_array[pos];
  188. }
  189. const T& operator[](const int pos) const override
  190. {
  191. assert(!empty() && "No current element.\n");
  192. return m_list_array[pos];
  193. }
  194. };
  195. #endif // ARRAYLIST_HPP


List.hpp:

  1. // This is a blueprint for all list-like data structures.
  2. // It won't specify how the operations are carried out.
  3. #ifndef LIST_HPP
  4. #define LIST_HPP
  5. #include <initializer_list>
  6. template <typename T>
  7. class List
  8. {
  9. public:
  10. List()
  11. {}
  12. virtual ~List()
  13. {}
  14. List(const List&)
  15. {}
  16. virtual void insert(unsigned pos, const T& item) = 0;
  17. virtual void append(const T& item) = 0;
  18. virtual T remove(const unsigned pos) = 0;
  19. virtual int size() const = 0;
  20. virtual T& operator[](const int pos) = 0;
  21. // The const overload is called only when used on const object.
  22. virtual const T& operator[](const int pos) const = 0;
  23. };
  24. #endif // LIST_HPP


Node.hpp:

  1. #ifndef NODE_HPP
  2. #define NODE_HPP
  3. template <typename T>
  4. struct Node
  5. {
  6. T data{}; // Value of the node.
  7. Node* next{nullptr}; // Pointer to the next node.
  8. Node(const T& dat, Node* nxt = nullptr)
  9. : data{dat}, next{nxt}
  10. {}
  11. };
  12. #endif // NODE_HPP


Source.cpp:

  1. #include "LinkedList.hpp"
  2. #include "ArrayList.hpp"
  3. #include <fstream>
  4. #include <iostream>
  5. #include <string>
  6. #define TO_DIGIT(x) (x) - ('0')
  7. template <typename T>
  8. std::ostream& operator<<(std::ostream& os, const List<T>& list)
  9. {
  10. for (int i{}, s{list.size()}; i < s; ++i)
  11. {
  12. os << list[i] << ' ';
  13. }
  14. return os;
  15. }
  16. int main()
  17. {
  18. std::ifstream fin("number.txt");
  19. if (!fin.good())
  20. {
  21. return -1;
  22. }
  23. std::string num{};
  24. ArrayList<LinkedList<int>> arr{};
  25. while (fin >> num)
  26. {
  27. LinkedList<int> list{};
  28. for (const char& ch : num)
  29. {
  30. list.prepend(TO_DIGIT(ch));
  31. }
  32. arr.append(list);
  33. }
  34. std::cout << arr;
  35. }

tvokkenx

tvokkenx1#

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

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

而不是这样:

  1. // Assignment operator using copy-and-swap idiom.
  2. LinkedList& operator=(const LinkedList<T>& other)
  3. {
  4. if (&other != this)
  5. {
  6. LinkedList<T> temp(other);
  7. swap(*this, temp);
  8. }
  9. return *this;
  10. }

字符串
这一点:

  1. LinkedList& operator=(const LinkedList<T>& other)
  2. {
  3. if (&other != this)
  4. {
  5. while (m_size > 0) {
  6. remove_back();
  7. }
  8. auto other_head = other.m_head;
  9. while (other_head != nullptr) {
  10. append(other_head->data);
  11. other_head = other_head->next;
  12. }
  13. }
  14. return *this;
  15. }

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

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

  1. template <typename T>
  2. class List
  3. {
  4. public:
  5. List()
  6. {}
  7. virtual ~List()
  8. {}
  9. List(const List&)
  10. {}
  11. virtual void insert(unsigned pos, const T& item) = 0;
  12. virtual void append(const T& item) = 0;
  13. virtual T remove(const unsigned pos) = 0;
  14. virtual int size() const = 0;
  15. virtual T& operator[](const int pos) = 0;
  16. // The const overload is called only when used on const object.
  17. virtual const T& operator[](const int pos) const = 0;
  18. };
  19. template <typename T>
  20. struct Node
  21. {
  22. T data{}; // Value of the node.
  23. Node* next{ nullptr }; // Pointer to the next node.
  24. Node(const T& dat, Node* nxt = nullptr)
  25. : data{ dat }, next{ nxt }
  26. {}
  27. };
  28. const int GROWTH_FACTOR = 2;
  29. template <typename T>
  30. class ArrayList : public List<T>
  31. {
  32. private:
  33. int m_capacity{}; // Maximum size of list.
  34. int m_size{}; // Current number of list elements.
  35. T* m_list_array{}; // Array holding list of elements.
  36. void reserve()
  37. {
  38. m_capacity *= GROWTH_FACTOR;
  39. if (m_capacity == 0) {
  40. m_capacity = 2;
  41. }
  42. T* temp = new T[m_capacity]; // Allocate new array in the heap.
  43. for (int i{}; i < m_size; ++i)
  44. {
  45. temp[i] = m_list_array[i]; // Copy all items of original array.
  46. }
  47. delete[] m_list_array; // Get rid of the original array.
  48. m_list_array = temp; // "temp" is our new array now.
  49. }
  50. public:
  51. ArrayList() = default;
  52. ~ArrayList()
  53. {
  54. delete[] m_list_array;
  55. }
  56. void clear()
  57. {
  58. delete[] m_list_array;
  59. m_list_array = nullptr;
  60. m_capacity = 0;
  61. m_size = 0;
  62. }
  63. // Insert "item" at given position.
  64. void insert(const unsigned pos, const T& item)// override
  65. {
  66. if (m_size == m_capacity)
  67. {
  68. reserve();
  69. }
  70. assert(static_cast<int>(pos) < m_size && "Out of range.\n");
  71. for (int s{ m_size }; static_cast<int>(pos) < s; --s) // Shift elements up...
  72. {
  73. m_list_array[s] = m_list_array[s - 1]; // ...to make room.
  74. }
  75. ///DEMONSTRATION
  76. //┌────┬────┬────┬────┬────┬────┬────┐
  77. //│i[0]│i[1]│i[2]│i[3]│i[4]│i[5]│i[6]│ // INDEXES
  78. //├────┼────┼────┼────┼────┼────┼────┤
  79. //│10 │20 │30 │40 │50 │60 │ │ // ITEMS
  80. //├────┼────┼────┼────┼────┼────┼────┤
  81. //│ │10 │20 │30 │40 │50 │60 │ // SHIFT ELEMENTS UP
  82. //├────┼────┼────┼────┼────┼────┼────┤
  83. //│item│10 │20 │30 │40 │50 │60 │ // INSERT "item"
  84. //└────┴────┴────┴────┴────┴────┴────┘
  85. //
  86. m_list_array[pos] = item;
  87. m_size++; // Increment list size.
  88. }
  89. // Append "item".
  90. void append(const T& item) override
  91. {
  92. if (m_size == m_capacity)
  93. {
  94. reserve();
  95. }
  96. //assert(m_size < m_capacity && "List capacity exceeded.\n");
  97. m_list_array[m_size] = item;
  98. m_size++;
  99. }
  100. // Remove and return the current element.
  101. T remove(const unsigned pos) override
  102. {
  103. assert(static_cast<int>(pos) < m_size && "No element.\n");
  104. T item = m_list_array[pos]; // Copy the item.
  105. // m_size - 1, because we're dealing with array indexes (array[size] is out of bounds).
  106. for (int i{ static_cast<int>(pos) }; i < m_size - 1; ++i)
  107. {
  108. m_list_array[i] = m_list_array[i + 1]; // Shift elements down.
  109. }
  110. ///DEMONSTRATION
  111. //┌────┬────┬────┬────┬────┬────┬────┐
  112. //│i[0]│i[1]│i[2]│i[3]│i[4]│i[5]│i[6]│ // INDEXES
  113. //├────┼────┼────┼────┼────┼────┼────┤
  114. //│10 │item│20 │30 │40 │50 │60 │ // ITEMS
  115. //├────┼────┼────┼────┼────┼────┼────┤
  116. //│10 │20 │30 │40 │50 │60 │... │ // SHIFT ELEMENTS DOWN
  117. //└────┴────┴────┴────┴────┴────┴────┘
  118. //
  119. m_size--; // Decrement size.
  120. return item;
  121. }
  122. // Return list size.
  123. int size() const override
  124. {
  125. return m_size;
  126. }
  127. bool empty() const
  128. {
  129. return size() == 0;
  130. }
  131. T& operator[](const int pos) override
  132. {
  133. assert(!empty() && "No current element.\n");
  134. return m_list_array[pos];
  135. }
  136. const T& operator[](const int pos) const override
  137. {
  138. assert(!empty() && "No current element.\n");
  139. return m_list_array[pos];
  140. }
  141. };
  142. template <typename T>
  143. class LinkedList : public List<T>
  144. {
  145. private:
  146. Node<T>* m_head{ nullptr };
  147. Node<T>* m_tail{ nullptr };
  148. int m_size{};
  149. public:
  150. LinkedList() = default;
  151. LinkedList(std::initializer_list<T> i_list)
  152. {
  153. for (const auto& item : i_list)
  154. {
  155. append(item);
  156. }
  157. }
  158. // Copy constructor.
  159. LinkedList(const LinkedList<T>& other) : List<T>{}
  160. {
  161. auto temp = other.m_head;
  162. while (temp != nullptr)
  163. {
  164. append(temp->data);
  165. temp = temp->next;
  166. }
  167. }
  168. ~LinkedList()
  169. {
  170. // Start from the beginning.
  171. Node<T>* temp = m_head;
  172. // Traverse the list while deleting previous elements.
  173. while (temp != nullptr)
  174. {
  175. temp = temp->next; // Move forward.
  176. delete m_head; // Delete the previous element.
  177. m_head = temp; // m_head moved one forward.
  178. }
  179. }
  180. // Assignment operator using copy-and-swap idiom.
  181. LinkedList& operator=(const LinkedList<T>& other)
  182. {
  183. if (&other != this)
  184. {
  185. while (m_size > 0) {
  186. remove_back();
  187. }
  188. auto other_head = other.m_head;
  189. while (other_head != nullptr) {
  190. append(other_head->data);
  191. other_head = other_head->next;
  192. }
  193. }
  194. return *this;
  195. }
  196. auto head() const
  197. {
  198. return m_head;
  199. }
  200. auto tail() const
  201. {
  202. return m_tail;
  203. }
  204. bool empty() const
  205. {
  206. return m_size == 0;
  207. }
  208. int size() const
  209. {
  210. return m_size;
  211. }
  212. void prepend(const T& item)
  213. {
  214. // Create a node holding our item and pointing to the head.
  215. auto new_item = new Node<T>{ item, m_head };
  216. // If the head is the last element
  217. // (meaning it is the only element),
  218. // it'll be the tail.
  219. if (m_head == nullptr)
  220. {
  221. m_tail = m_head;
  222. }
  223. m_head = new_item;
  224. m_size++;
  225. }
  226. void append(const T& item)
  227. {
  228. // Create a node with no pointer.
  229. auto new_item = new Node<T>{ item };
  230. if (m_tail == nullptr)
  231. {
  232. // If the list is empty, set the new item as the head as well.
  233. m_head = new_item;
  234. m_tail = new_item;
  235. }
  236. else
  237. {
  238. // Otherwise, update the current tail's next pointer to the new item and move the tail.
  239. m_tail->next = new_item;
  240. m_tail = new_item;
  241. }
  242. m_size++;
  243. }
  244. // Avoid illegal indexes by making pos unsigned.
  245. void insert(const unsigned pos, const T& item)
  246. {
  247. // If the position is the beginning of the list, prepend the new node.
  248. if (pos == 0)
  249. {
  250. prepend(item);
  251. }
  252. // If the position is beyond the end of the list, append the new node.
  253. else if (static_cast<int>(pos) >= m_size)
  254. {
  255. append(item);
  256. }
  257. else
  258. {
  259. // Create a new node.
  260. auto new_item = new Node<T>{ item };
  261. // Starting from the head, go to the one past the position.
  262. auto temp = m_head;
  263. for (int i{}; i < static_cast<int>(pos) - 1; ++i)
  264. {
  265. temp = temp->next;
  266. }
  267. new_item->next = temp->next; // Link the new_item to the one after the temp.
  268. temp->next = new_item; // Link temp to the new_item.
  269. m_size++;
  270. }
  271. }
  272. void remove_front()
  273. {
  274. Node<T>* temp = m_head;
  275. // If there's no element, exit.
  276. if (m_head == nullptr)
  277. {
  278. return;
  279. }
  280. m_head = m_head->next; // Move m_head one element forward.
  281. delete temp; // Get rid of the previous element.
  282. m_size--;
  283. if (m_size == 0) {
  284. m_head = nullptr;
  285. m_tail = nullptr;
  286. }
  287. }
  288. void remove_back()
  289. {
  290. Node<T>* temp = m_head;
  291. if (temp == nullptr)
  292. {
  293. return;
  294. }
  295. // If the list's size is 1.
  296. if (temp == m_tail)
  297. {
  298. delete temp;
  299. m_head = m_tail = nullptr;
  300. --m_size;
  301. return;
  302. }
  303. // Traverse to one before the end.
  304. while (temp->next != m_tail)
  305. {
  306. temp = temp->next;
  307. }
  308. m_tail = temp;
  309. //temp = temp->next;
  310. delete temp->next;
  311. m_tail->next = nullptr;
  312. --m_size;
  313. }
  314. // Avoid illegal indexes by making pos unsigned.
  315. T remove(const unsigned pos)
  316. {
  317. Node<T>* temp = m_head;
  318. // Go to the one past the pos.
  319. for (int i{}; i < static_cast<int>(pos) - 1; ++i)
  320. {
  321. temp = temp->next;
  322. }
  323. // The element to be removed.
  324. auto to_removed = temp->next;
  325. // Link the current node one after the to_removed.
  326. temp->next = temp->next->next;
  327. T removed_data = to_removed->data; // Retrieve the data before deleting the node.
  328. delete to_removed; // Delete the to_removed.
  329. m_size--; // Don't forget to decrement the size.
  330. if (m_size == 0) {
  331. m_head = nullptr;
  332. m_tail = nullptr;
  333. }
  334. return removed_data;
  335. }
  336. T& operator[](const int pos)
  337. {
  338. Node<T>* temp = m_head;
  339. for (int i{}; i != pos; ++i)
  340. {
  341. temp = temp->next;
  342. }
  343. return temp->data;
  344. }
  345. const T& operator[](const int pos) const
  346. {
  347. Node<T>* temp = m_head;
  348. for (int i{}; i != pos; ++i)
  349. {
  350. temp = temp->next;
  351. }
  352. return temp->data;
  353. }
  354. };

展开查看全部
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又调用赋值运算符,依此类推。

  1. void swap(LinkedList<T>& a, LinkedList<T>& b)
  2. {
  3. // ERROR - Infinite recursion
  4. LinkedList<T> temp = a;
  5. a = b;
  6. b = temp;
  7. }

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

无需继承

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

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


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

使用std::vectorstd::forward_list编写函数main

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

  • USE_STD == 1时,程序使用std::vectorstd::forward_list
  • USE_STD == 0时,程序使用tbx::cpp23::Vectortbx::cpp23::Forward_List
  1. // main.ixx
  2. module;
  3. #define USE_STD 0
  4. export module main;
  5. import std;
  6. #if USE_STD
  7. template< typename T >
  8. using Forward_List = std::forward_list<T>;
  9. template< typename T >
  10. using Vector = std::vector<T>;
  11. #else
  12. import tbx.cpp23.Forward_List;
  13. import tbx.cpp23.Vector;
  14. template< typename T >
  15. using Forward_List = tbx::cpp23::Forward_List<T>;
  16. template< typename T >
  17. using Vector = tbx::cpp23::Vector<T>;
  18. #endif
  19. // ...


从这一点开始,使用类型别名:VectorForward_List。例如,这个定义来自函数main

  1. Vector<Forward_List<int>> arr;

流插入操作符

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

  1. #if USE_STD
  2. std::ostream& operator<< (
  3. std::ostream& ost,
  4. Forward_List<int> const list)
  5. {
  6. for (auto const& item : list)
  7. ost << item << ' ';
  8. ost << '\n';
  9. return ost;
  10. }
  11. #else
  12. // The implementation of `tbx::cpp23::Forward_List<T>` defines
  13. // `operator<<` as a hidden friend. No definition is needed here.
  14. #endif
  15. std::ostream& operator<< (
  16. std::ostream& ost,
  17. Vector<Forward_List<int>> const vec)
  18. {
  19. for (auto const& list : vec)
  20. ost << list;
  21. ost.put('\n');
  22. return ost;
  23. }

main函数源代码

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

  1. export int main()
  2. {
  3. enum : int { no_errors, create_error, open_error, skipped_number };
  4. int exit_code = no_errors;
  5. // numbers.txt
  6. // This is the input file.
  7. std::string file_name_numbers{ "number.txt" };
  8. // skipped.txt
  9. // Invalid "numbers" are written to this file.
  10. std::string file_name_skipped_numbers{ "skipped.txt" };
  11. if (!create_file_numbers(file_name_numbers, 3))
  12. {
  13. std::cerr << "ERROR - Could not create file: \""
  14. + file_name_numbers + '"';
  15. return create_error;
  16. }
  17. std::ifstream ist(file_name_numbers);
  18. if (!ist.is_open())
  19. {
  20. std::cerr << "ERROR - Could not open file: \""
  21. + file_name_numbers + '"';
  22. return open_error;
  23. }
  24. std::ofstream log(file_name_skipped_numbers);
  25. if (!log.is_open())
  26. {
  27. std::cerr << "ERROR - Could not open file: \""
  28. + file_name_skipped_numbers + '"';
  29. return open_error;
  30. }
  31. Vector<Forward_List<int>> arr;
  32. std::string num{};
  33. while (ist >> num)
  34. {
  35. if (is_digit_string(num))
  36. {
  37. // Note: This loop duplicates the action of the OP.
  38. // It reverses the order of the digits. Thus, the MSD
  39. // is pushed onto the front of the list first, followed
  40. // by the other digits. It would be easy to parse string
  41. // `num` in reverse order, and thereby create a list with
  42. // the digits in their original order.
  43. Forward_List<int> list;
  44. for (const char& ch : num)
  45. list.push_front(digit_to_int(ch));
  46. arr.push_back(list);
  47. }
  48. else
  49. {
  50. std::cerr
  51. << "ERROR - Skipping invalid number in input file: "
  52. << num
  53. << '\n';
  54. log << num << '\n';
  55. exit_code = skipped_number;
  56. }
  57. }
  58. ist.close();
  59. log.close();
  60. std::cout << arr;
  61. return exit_code;
  62. }

Helper函数

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

  1. bool create_file_numbers(
  2. std::string const& file_name,
  3. int n = 5)
  4. {
  5. // This file is not described in the OP at StackOverflow.
  6. // Judging by how it is used, the file is comprised of a series
  7. // of non-negative integer values (without any sign, + or -),
  8. // separated by whitespace.
  9. //
  10. // For convenience, let's suppose there is one number per line.
  11. std::ofstream ost{ file_name };
  12. if (!ost.is_open())
  13. return false;
  14. std::mt19937 mt{ std::random_device{}() };
  15. std::uniform_int_distribution<int> dist{ 0, 99'999 };
  16. while (n--)
  17. ost << dist(mt) << '\n';
  18. ost.close();
  19. return true;
  20. }
  21. int digit_to_int(char const c) {
  22. return c - '0';
  23. }
  24. bool is_digit_string(std::string_view sv) noexcept
  25. {
  26. for (char const& c : sv)
  27. if (!std::isdigit(static_cast<unsigned char const>(c)))
  28. return false;
  29. return !sv.empty();
  30. }

编写自定义类的技巧

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

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

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

  1. // Forward_List.ixx
  2. export module tbx.cpp23.Forward_List;
  3. export namespace tbx::cpp23
  4. {
  5. template< typename T >
  6. class Forward_List
  7. {
  8. public:
  9. using value_type = T;
  10. private:
  11. struct Node
  12. {
  13. value_type value{};
  14. Node* next{ nullptr };
  15. bool operator== (Node const& that) const {
  16. return this->value == that.value;
  17. }
  18. };
  19. Node *head{}, *tail{};
  20. public:
  21. struct Iterator
  22. {
  23. // ...
  24. };
  25. // ...
  26. };
  27. }


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

  1. // Vector.ixx
  2. export module tbx.cpp23.Vector;
  3. export namespace tbx::cpp23
  4. {
  5. template< typename T >
  6. class Vector
  7. {
  8. public:
  9. using value_type = T;
  10. using size_type = std::size_t;
  11. using iterator = value_type*;
  12. using const_iterator = value_type const*;
  13. private:
  14. size_type capacity_{};
  15. size_type size_{};
  16. value_type* data_{ nullptr };
  17. enum : size_type { zero, one, two };
  18. public:
  19. // ...
  20. };
  21. }

演示程序

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

  1. // main.ixx
  2. module;
  3. #define USE_STD 0
  4. export module main;
  5. import std;
  6. #if USE_STD
  7. template< typename T >
  8. using Forward_List = std::forward_list<T>;
  9. template< typename T >
  10. using Vector = std::vector<T>;
  11. #else
  12. import tbx.cpp23.Forward_List;
  13. import tbx.cpp23.Vector;
  14. template< typename T >
  15. using Forward_List = tbx::cpp23::Forward_List<T>;
  16. template< typename T >
  17. using Vector = tbx::cpp23::Vector<T>;
  18. #endif
  19. #if USE_STD
  20. std::ostream& operator<< (
  21. std::ostream& ost,
  22. Forward_List<int> const list)
  23. {
  24. for (auto const& item : list)
  25. ost << item << ' ';
  26. ost << '\n';
  27. return ost;
  28. }
  29. #else
  30. // The implementation of `tbx::cpp23::Forward_List<T>` defines
  31. // `operator<<` as a hidden friend. No definition is needed here.
  32. #endif
  33. std::ostream& operator<< (
  34. std::ostream& ost,
  35. Vector<Forward_List<int>> const vec)
  36. {
  37. for (auto const& list : vec)
  38. ost << list;
  39. ost.put('\n');
  40. return ost;
  41. }
  42. bool create_file_numbers(
  43. std::string const& file_name,
  44. int n = 5)
  45. {
  46. // This file is not described in the OP at StackOverflow.
  47. // Judging by how it is used, the file is comprised of a series
  48. // of non-negative integer values (without any sign, + or -),
  49. // separated by whitespace.
  50. //
  51. // For convenience, let's suppose there is one number per line.
  52. std::ofstream ost{ file_name };
  53. if (!ost.is_open())
  54. return false;
  55. std::mt19937 mt{ std::random_device{}() };
  56. std::uniform_int_distribution<int> dist{ 0, 99'999 };
  57. while (n--)
  58. ost << dist(mt) << '\n';
  59. ost.close();
  60. return true;
  61. }
  62. int digit_to_int(char const c) {
  63. return c - '0';
  64. }
  65. bool is_digit_string(std::string_view sv) noexcept
  66. {
  67. for (char const& c : sv)
  68. if (!std::isdigit(static_cast<unsigned char const>(c)))
  69. return false;
  70. return !sv.empty();
  71. }
  72. export int main()
  73. {
  74. enum : int { no_errors, create_error, open_error, skipped_number };
  75. int exit_code = no_errors;
  76. // numbers.txt
  77. // This is the input file.
  78. std::string file_name_numbers{ "number.txt" };
  79. // skipped.txt
  80. // Invalid "numbers" are written to this file.
  81. std::string file_name_skipped_numbers{ "skipped.txt" };
  82. if (!create_file_numbers(file_name_numbers, 3))
  83. {
  84. std::cerr << "ERROR - Could not create file: \""
  85. + file_name_numbers + '"';
  86. return create_error;
  87. }
  88. std::ifstream ist(file_name_numbers);
  89. if (!ist.is_open())
  90. {
  91. std::cerr << "ERROR - Could not open file: \""
  92. + file_name_numbers + '"';
  93. return open_error;
  94. }
  95. std::ofstream log(file_name_skipped_numbers);
  96. if (!log.is_open())
  97. {
  98. std::cerr << "ERROR - Could not open file: \""
  99. + file_name_skipped_numbers + '"';
  100. return open_error;
  101. }
  102. Vector<Forward_List<int>> arr;
  103. std::string num{};
  104. while (ist >> num)
  105. {
  106. if (is_digit_string(num))
  107. {
  108. // Note: This loop duplicates the action of the OP.
  109. // It reverses the order of the digits. Thus, the MSD
  110. // is pushed onto the front of the list first, followed
  111. // by the other digits. It would be easy to parse string
  112. // `num` in reverse order, and thereby create a list with
  113. // the digits in their original order.
  114. Forward_List<int> list;
  115. for (const char& ch : num)
  116. list.push_front(digit_to_int(ch));
  117. arr.push_back(list);
  118. }
  119. else
  120. {
  121. std::cerr
  122. << "ERROR - Skipping invalid number in input file: "
  123. << num
  124. << '\n';
  125. log << num << '\n';
  126. exit_code = skipped_number;
  127. }
  128. }
  129. ist.close();
  130. log.close();
  131. std::cout << arr;
  132. return exit_code;
  133. }
  134. // end file: main.ixx

展开查看全部

相关问题