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.

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

template
class List {
public:
List();
List(T item);
List(const List &rhs);
List(List &&rhs);
~List();
List& operator=(const List &rhs);
List& operator=(List &&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
List::List() : _arr(new T[0]),
_size(0),
_capacity(0)
{
}

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

template
List::List(const List &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
List::List(List &&rhs) : _arr(rhs._arr),
_size(rhs._size),
_capacity(rhs._capacity)
{
rhs._arr = nullptr;
}

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

template
List& List::operator=(const List &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
List& List::operator=(List &&rhs)
{
if (this != &rhs) {
delete [] _arr;
_arr = rhs._arr;
_size = rhs._size;
_capacity = rhs._capacity;
rhs._arr = nullptr;
}

return *this;
}

template
unsigned int List::size() const noexcept
{
return _size;
}

template
unsigned int List::capacity() const noexcept
{
return _capacity;
}

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

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

template
unsigned int List::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
void List::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
void List::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
void List::collapse(unsigned int i) noexcept
{
for (unsigned int counter = i; counter < _size - 1; counter++)
_arr[counter] = _arr[counter + 1];
}

#endif

//End of Code.

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

Here is the updated code for you, without any errors:

//myList.hpp source code
#ifndef MYLIST_H_
#define MYLIST_H_
#include<iostream>
#include<cctype>
using namespace std;
//PROJECT 2 STUDENT FILE
//template class that simulates an ordered list of common elements
//It is assumed that the list will either be empty or completely full
template <class type>
class myList
{
protected:
int length; //the number of elements in the list
type *items; //dynamic array to store the elements
  
public:
~myList();
//destructor for memory cleanup
//Postcondition: Deallocates the memory occupied by the items array
  
myList();   
//default constructor
//Postcondition: creates items array of size 0 and sets size to zero
  
myList(int n, type t);   
//assignment constructor
//Postcondition: creates items array of size n. Each element in the list
//is assigned the value of type t, sets length to n
  
myList(int n, type *anArray);   
//assignment constructor
//Postcondition: copies contents of anArray parameter into items array
//sets length to n
  
myList(const myList & otherList);
//copy constructor
//Postcondition: makes a deep copy of the parameter otherList to
//the calling list
void print(ostream& outStream);
//prints the elements of the list using outStream
//Postcondition: The elements of the list are printed to the
//output stream each separated by a comma. The last element
//printed should not have a comma after it
  
void append(const type& theItem);
//assigns the parameter theItem to the end of the list
//Postcondition: the parameter theItem is the last element in the list
  
bool isIn(const type& theItem);
//determines if an element is currently in the list
//Postcondition: Returns true if the parameter theItem is in the list,
//otherwise returns false
  
bool insert(const type& theItem, int location);
//inserts an element into the list
//Postcondition: inserts the parameter theItem into the list at position
//determined by the parameter location and then returns true, if the location
//is greater than the length of the list + 2, then the function returns false
//LOCATION MEANS COUNTING FROM 1, SO LOCATION 1 MEANS INDEX POSITION 0, ETC..
  
void sort(char ch);
//Assuming the list contains numbers, characters, or strings this functions
//sorts the elements in the list, where type is either 'A','a'
//for ascending, or 'D','d' for descending
//Choose any sorting algorithm of your choice
//Postcondition: sorts the elements in the list
  
//OVERLOADED OPERATORS
myList& operator=(const myList& rhs);
//overloading of the assignment operator to allow for list to list assignment
  
myList& operator+=(const type& t);
//overloading of the addition_equal operator that adds the parameter t
//to the end of the list
  
myList& operator+=(const myList& rhs);
//overloading of the addition_equal operator that adds another list
//to the end of the list
  
/*
FOR 10% EXTRA CREDIT ON THIS PROJECT GRADE, OVERLOAD THE FOLLOWING OPERATORS
AS NON-MEMBER FUNCTIONS
(1) << (insertion)
(2) + (addition) that adds one element to a list
(3) + (addition) that adds two lists
  
HINT: to overload both addition operators as stated above use the member
functions +=
KEEP IN MIND THAT THE SYNTAX GETS TRICKY WHEN WRITING NON-MEMBER FUNCTIONS
FOR TEMPLATE CLASSES
  
See example prototypes below
*/
//friend ostream& operator<< (ostream& outStream, const myList<type>& theList){}
//friend myList& operator+ (myList<type> &lhs, const type& t){}
//friend myList& operator+ (myList<type> &lhs, const myList<type>& rhs){}
};
template <class type>
myList<type>::~myList()
{
delete [] items;
}
template <class type>
myList<type>::myList()
{
length=0;
items=new type;
items = NULL;
}
template <class type>
myList<type>::myList(int n, type t)   
//assignment constructor
//Postcondition: creates items array of size n. Each element in the list
//is assigned the value of type t, sets length to n
{
length = n;
items = new type[length];
for(int i = 0; i < length; i++)
items[i] = t;
}
  
template <class type>
myList<type>::myList(int n, type *anArray)   
//assignment constructor
//Postcondition: copies contents of anArray parameter into items array
//sets length to n
{
length = n;
items = anArray;
}
  
template <class type>
myList<type>::myList(const myList & otherList)
//copy constructor
//Postcondition: makes a deep copy of the parameter otherList to
//the calling list
{
items = otherList.items;
}
template <class type>
void myList<type>::print(ostream& outStream)
//prints the elements of the list using outStream
//Postcondition: The elements of the list are printed to the
//output stream each separated by a comma. The last element
//printed should not have a comma after it
{
for(int i = 0; i < length - 1; i++)
outStream<<*(items + i)<<", ";
outStream<<*(items + length - 1);
}
template <class type>
void myList<type>::append(const type& theItem)
//assigns the parameter theItem to the end of the list
//Postcondition: the parameter theItem is the last element in the list
{
items[length] = theItem;
length++;
}
  
template <class type>
bool myList<type>::isIn(const type& theItem)
//determines if an element is currently in the list
//Postcondition: Returns true if the parameter theItem is in the list,
//otherwise returns false
{
for(int i = 0; i < length; i++)
if(*(items + i) == theItem)
return true;
return false;
}
  
template <class type>
bool myList<type>::insert(const type& theItem, int location)
//inserts an element into the list
//Postcondition: inserts the parameter theItem into the list at position
//determined by the parameter location and then returns true, if the location
//is greater than the length of the list + 2, then the function returns false
//LOCATION MEANS COUNTING FROM 1, SO LOCATION 1 MEANS INDEX POSITION 0, ETC..
{
if(location > length + 2)
return false;
for(int i = length-1; i >= location - 1; i--)
*(items + i + 1) = *(items + i);
*(items + location - 1) = theItem;
}
  
template <class type>
void myList<type>::sort(char ch)
//Assuming the list contains numbers, characters, or strings this functions
//sorts the elements in the list, where type is either 'A','a'
//for ascending, or 'D','d' for descending
//Choose any sorting algorithm of your choice
//Postcondition: sorts the elements in the list
{
type n;
switch(ch)
        {
            case 'd':
       case 'D':
           for(int i=0;i<length;i++)
           {
               for(int j=i+1;j<length;j++)
               {
               if(items[i]<items[j])
               {
                   n=items[i];
                   items[i]=items[j];
                   items[j]=n;
               }
               }
           }
           break;
       case 'a':
       case 'A':
           for(int i=0;i<length;i++)
           {
               for(int j=i+1;j<length;j++)
               {
               if(items[i]>items[j])
               {
                   n=items[i];
                   items[i]=items[j];
                   items[j]=n;
               }
               }
           }
           break;
       }
}
  
//OVERLOADED OPERATORS
template <class type>
myList<type>& myList<type>::operator=(const myList& rhs)
//overloading of the assignment operator to allow for list to list assignment
{
for(int i = 0; i < length; i++)
items[i] = rhs.items[i];
return this;
}
  
template <class type>
myList<type>& myList<type>::operator+=(const type& t)
//overloading of the addition_equal operator that adds the parameter t
//to the end of the list
{
items[length] = t;
    length++;
}

template <class type>
myList<type>& myList<type>::operator+=(const myList& rhs)
//overloading of the addition_equal operator that adds another list
//to the end of the list
{
for(int i = 0; i < rhs.size(); i++)
*(items + length + i) = rhs.items[i];
}
  

#endif /* MYLIST_H_ */

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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