Take this class and retool it to use allocated memory in your dynamic array. My

Question

Take this class and retool it to use allocated memory in your dynamic array. My teacher said that you only really need to touch the List class to fully retool the program. To show an example of what my teacher wants here is this, and also as you can read from this screenshot. He also wants a static allocator object to be added in the List class.

List class requirements:

– The list shall only be expected to work when it holds pointers to whatever data type– The list shall hold its items in a dynamic array

* The use of the vector class is not allowed– The list shall be sorted

* In the case of Books, they should sort themselves by author, then title 1

* The List only cares about a < b, your Books are responsible for ensuring that comparison can be made

– The list shall double its capacity when needed
– The list shall never shrink its capacity
– Items in the list shall always be contiguous in the dynamic array (no gaps in the array)

Now this is all of the code for the List class that has NOT been retooled yet to use memory allocation.

Code:

List.hpp:

#ifndef ARRAY_LIST_HPP
#define ARRAY_LIST_HPP

#include <stdexcept>
#include <iostream>

template <typename T>
class List {
public:
List();
List(T item);
List(const List<T> &rhs);
List(List<T> &&rhs);
~List();
List<T>& operator=(const List<T> &rhs);
List<T>& operator=(List<T> &&rhs);
unsigned int size() const noexcept;
unsigned int capacity() const noexcept;
void insert(T item) noexcept;
void erase(T item); // Throws underflow_error if empty, range_error if item doesn't exist
const T& at(unsigned int i) const; // Both at() functions can throw
T& at(unsigned int i); // out_of_range exception
unsigned int search(T item) const; // Throws domain_error if item doesn't exist
private:
T *_arr;
unsigned int _size;
unsigned int _capacity;

void grow() noexcept; // EXTRA
void displace(unsigned int i); // EXTRA
void collapse(unsigned int i) noexcept; // EXTRA
};

// LIST CLASS IMPLEMENTATION
template <typename T>
List<T>::List() : _arr(new T[0]),
_size(0),
_capacity(0)
{
}

template <typename T>
List<T>::List(T item) : _arr(new T[1]),
_size(1),
_capacity(1)
{
_arr[0] = item;
}

template <typename T>
List<T>::List(const List<T> &rhs) : _arr(new T[rhs._size]),
_size(rhs._size),
_capacity(rhs._size)
{
for (unsigned int i = 0; i < _size; i++)
_arr[i] = rhs._arr[i];
}

template <typename T>
List<T>::List(List<T> &&rhs) : _arr(rhs._arr),
_size(rhs._size),
_capacity(rhs._capacity)
{
rhs._arr = nullptr;
}

template <typename T>
List<T>::~List()
{
if (_arr != nullptr) {
delete [] _arr;
_arr = nullptr;
}
_size = 0;
_capacity = 0;
}

template <typename T>
List<T>& List<T>::operator=(const List<T> &rhs)
{
if (this != &rhs) {
delete [] _arr;
_arr = new T[rhs._size];
_size = rhs._size;
_capacity = rhs._capacity;
for (unsigned int i = 0; i < _size; i++)
_arr[i] = rhs._arr[i];
}

return *this;
}

template <typename T>
List<T>& List<T>::operator=(List<T> &&rhs)
{
if (this != &rhs) {
delete [] _arr;
_arr = rhs._arr;
_size = rhs._size;
_capacity = rhs._capacity;
rhs._arr = nullptr;
}

return *this;
}

template <typename T>
unsigned int List<T>::size() const noexcept
{
return _size;
}

template <typename T>
unsigned int List<T>::capacity() const noexcept
{
return _capacity;
}

template <typename T>
void List<T>::insert(T item) noexcept
{
if (_capacity == 0 || _size == _capacity) {
grow();
}

if (_size == 0) {
_arr[0] = item;
_size++;
return;
}
  
unsigned int i = 0;
while (i < _size) {
if (*item < *(_arr[i])) {
try {
displace(i);
} catch (std::range_error &e) {
std::cerr << e.what() << " in insert function. ";
}
break;
}
i++;
}

_arr[i] = item;
_size++;
}

template <typename T>
void List<T>::erase(T item)
{
if (_size == 0)
throw std::underflow_error("erase on empty");
  
try {
int loc = search(item);

collapse(loc);
_size--;
} catch(std::domain_error &e) {
throw std::range_error("erase non-existent item");
}
}

template <typename T>
const T& List<T>::at(unsigned int i) const
{
if (i < 0 || i >= _size)
throw std::out_of_range("bad index");
  
return _arr[i];
}

template <typename T>
T& List<T>::at(unsigned int i)
{
if (i < 0 || i >= _size)
throw std::out_of_range("bad index");
  
return _arr[i];
}

template <typename T>
unsigned int List<T>::search(T item) const
{
for (unsigned int i = 0; i < _size; i++) {
if (_arr[i] == item) {
return i;
}
}

throw std::domain_error("does not exist");
}

template <typename T>
void List<T>::grow() noexcept
{
if (_capacity == 0) {
delete [] _arr;
_arr = new T[1];
_capacity = 1;
} else {
T *temp = new T[_capacity * 2];
for (unsigned int i = 0; i < _size; i++) {
temp[i] = _arr[i];
}
delete _arr;
_arr = temp;
_capacity *= 2;
}
}

template <typename T>
void List<T>::displace(unsigned int i)
{
if ( !(_size < _capacity) )
throw std::range_error("displace has no room");
  
for (unsigned int counter = _size; counter > i; counter--)
_arr[counter] = _arr[counter - 1];
}

template <typename T>
void List<T>::collapse(unsigned int i) noexcept
{
for (unsigned int counter = i; counter < _size - 1; counter++)
_arr[counter] = _arr[counter + 1];
}

#endif

You shall add a static allocator object to the class. . You shall retool the entire class around memory allocation, here's one constructor for free: template List::List(T item) begin(alloc.allocate(1)) end(_begin) -capacityC.begin + 1) alloc.constructcend-+, item);

Explanation / Answer

#ifndef DL_LIST_H #define DL_LIST_H #include namespace cop4530 { template class List { private: // nested Node class struct Node { T data; Node *prev; Node *next; Node(const T & d = T(), Node *p = NULL, Node *n = NULL) : data(d), prev(p), next(n) {} }; public: //nested const_iterator class class const_iterator { public: const_iterator(); // default zero parameter constructor const T & operator*() const; // operator*() to return element // increment/decrement operators const_iterator & operator++(); const_iterator operator++(int); const_iterator & operator--(); const_iterator operator--(int); // comparison operators bool operator==(const const_iterator &rhs) const; bool operator!=(const const_iterator &rhs) const; protected: Node *current; // pointer to node in List T & retrieve() const; // retrieve the element refers to const_iterator(Node *p); // protected constructor friend class List; }; // nested iterator class class iterator : public const_iterator { public: iterator() {} T & operator*(); const T & operator*() const; // increment/decrement operators iterator & operator++(); iterator operator++(int); iterator & operator--(); iterator operator--(int); protected: iterator(Node *p); friend class List; }; public: // constructor, desctructor, copy constructor List(); // default zero parameter constructor List(const List &rhs); // copy constructor // num elements with value of val explicit List(int num, const T& val = T()); // constructs with elements [start, end) List(const_iterator start, const_iterator end); ~List(); // destructor // assignment operator const List& operator=(const List &rhs); // member functions int size() const; // number of elements bool empty() const; // check if list is empty void clear(); // delete all elements void reverse(); // reverse the order of the elements T &front(); // reference to the first element const T& front() const; T &back(); // reference to the last element const T & back() const; void push_front(const T & val); // insert to the beginning void push_back(const T & val); // insert to the end void pop_front(); // delete first element void pop_back(); // delete last element void remove(const T &val); // remove all elements with value = val // print out all elements. ofc is deliminitor void print(std::ostream& os, char ofc = ' ') const; iterator begin(); // iterator to first element const_iterator begin() const; iterator end(); // end marker iterator const_iterator end() const; iterator insert(iterator itr, const T& val); // insert val ahead of itr iterator erase(iterator itr); // erase one element iterator erase(iterator start, iterator end); // erase [start, end) private: int theSize; // number of elements Node *head; // head node Node *tail; // tail node void init(); // initialization }; // overloading comparison operators template bool operator==(const List & lhs, const List &rhs); template bool operator!=(const List & lhs, const List &rhs); // overloading output operator template std::ostream & operatorprev; return *this; } template typename List::const_iterator List::const_iterator::operator--(int) { const_iterator old = *this; operator--(); return old; } template bool List::const_iterator::operator==(const typename List::const_iterator& rhs) const { return current == rhs.current; } template bool List::const_iterator::operator!=(const typename List::const_iterator& rhs) const { return !(*this == rhs); } template T& List::const_iterator::retrieve() const { return current->data; } template List::const_iterator::const_iterator(Node* p) { current = p; } template T& List::iterator::operator*() { return this->retrieve(); } template const T& List::iterator::operator*() const { return this->retrieve();; } template typename List::iterator& List::iterator::operator++() { this->current = this->current->next; return *this; } template typename List::iterator List::iterator::operator++(int) { iterator it = *this; this->current = this->current->next; return it; } template typename List::iterator& List::iterator::operator--() { this->current = this->current->prev; return *this; } template typename List::iterator List::iterator::operator--(int) { iterator it = *this; this->current = this->current->prev; return it; } template List::iterator::iterator(Node* p) { this->current = p; } template List::List() { init(); } template List::List(const List &rhs) { init(); for (typename List::iterator i = rhs.begin(); i != rhs.end(); ++i) { push_back(*i); } } template List::List(int num, const T& val) { init(); for (int i = 0; i next = tail; tail->prev = head; } template List::~List() { clear(); delete head; delete tail; } template const List& List::operator=(const List &rhs) { //todo COPIES of nodes? head = rhs.head; tail = rhs.tail; theSize = rhs.theSize; return *this; } template int List::size() const { return theSize; } template bool List::empty() const { return theSize == 0; } template void List::clear() { while (!empty()) pop_front(); } template void List::reverse() { for (iterator it = ----end(); it != begin();) { it = --erase(it); } push_back(*begin()); pop_front(); } template T& List::front() { return *begin(); } template const T& List::front() const { return *begin(); } template T& List::back() { return tail->prev->data; } template const T& List::back() const { return tail->prev->data; } template void List::push_front(const T & val) { insert(begin(), val); } template void List::push_back(const T & val) { insert(end(), val); } template void List::pop_front() { erase(begin()); } template void List::pop_back() { erase(--end()); } template void List::remove(const T& val) //delete all nodes with value equal to val from the list. { for (typename List::iterator it = begin(); it != end(); ) { if (*it == val) it = erase(it); else ++it; } } template void List::print(std::ostream& os, char delim) const { for (typename List::const_iterator it = begin(); it != end();) { os prev = p -> prev -> next = new Node(val, p -> prev, p)); } template typename List::iterator List::erase(typename List::iterator itr) { Node* p = itr.current; typename List::iterator retVal(p -> next); p -> prev -> next = p -> next; p -> next -> prev = p -> prev; delete p; theSize--; return retVal; } template typename List::iterator List::erase(typename List::iterator start, typename List::iterator end) { for (typename List::iterator it = start; it != end; ) { it = erase(it); } return end; } template bool operator==(const typename List & lhs, const typename List & rhs) { std::cout

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.