I'm getting this error from Visual Studio when trying to print the ArrayList's items:
Unhandled exception at 0x00007FF9E8AF8739 (ucrtbased.dll) in List.exe: 0xC00000FD: Stack overflow (parameters: 0x0000000000000001, 0x0000007E50C13FF8).
I have no idea what to make of this. I was trying to implement copy-and-swap idiom.
I was reading a file of numbers, add its digits to a linked list. And appending that linked list to a dynamic array and print its content. Both LinkedList and ArrayList have their operator<< overloaded.
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;
}
I fixed several bugs in your code. Namely:
swap functions out of LinkedList. And then fixed your LinkedList overloaded assigment operator to do a proper copy instead of some swap thing.Instead of this:
// 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;
}
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;
}
Several places in LinkedList where m_size gets decremented, but you forget to set m_head and m_tail to nullptr when this happens. remove_front and remove specifically.
The reserve method in ArrayList needed a quick fix to handle the case where capacity was initially zero. In which case, the easy fix is to grow the size to 2.
Removed most of those overloaded copy constructors and assignment operators in ArrayList. They weren't getting used and I wasn't convinced they were needed. You can add them back, but I wasn't convinced it wasn't a source of a bug.
After all that, your code seems to work.
Here's your code after the above fixes.
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;
}
};