so the code, basically an AList with multiple functions, I have below currently runs fine and my passes all assertions and test cases that are assigned to my assignment, however, I lose .5 points because of a memory error. I believe the error lies somewhere in my copy constructor, but I am currently struggling to know where is the issue.
This is how my code looks along with my copy constructor.
#ifndef __ALIST_H__
#define __ALIST_H__
// size should not be negative
typedef unsigned long size_t;
#define RFACTOR 2 // use factor 2
namespace ds {
template <typename ItemType> class TestDriver; // for autograding; please ignore
/** Array-based list. */
template <typename ItemType> class AList {
friend class TestDriver<ItemType>; // for autograding; please ignore
private:
/** The underlying array. */
ItemType *items;
/** Stores the current size of the list. */
size_t count;
/** Max number of items allowed. */
size_t maxCnt;
/** Resize the underlying array to the target capacity. */
void resize(size_t capacity) {
maxCnt = capacity;
ItemType *a = new ItemType[maxCnt];
for (size_t i = 0; i < count; i++) {
a[i] = items[i];
}
delete[] items;
items = a;
}
public:
/**
* Construct a new AList object.
*
* @param initSize initial size of the underlying array; default 100
*/
AList(size_t initSize = 100) {
count = 0;
maxCnt = initSize;
items = new ItemType[maxCnt];
}
/** Destroy the AList object. */
~AList() { delete[] items; }
/** Return the number of elements in list. */
size_t size() const { return count; }
/** Return the i-th item in list .*/
ItemType &get(int i) const { return items[i]; }
/** Append `x` to the end of list. */
void addLast(ItemType x) {
if (count == maxCnt) {
resize(count * RFACTOR);
}
items[count] = x;
count += 1;
}
/** Return the last item in list. */
ItemType &getLast() const { return items[count - 1]; }
/** Delete and return the last item. */
ItemType removeLast() {
ItemType returnItem = getLast();
count -= 1;
return returnItem;
}
AList(const AList<ItemType> &other);
void addFirst(ItemType x);
ItemType &getFirst() const;
ItemType removeFirst();
};
/** Copy constructor. */
template <typename ItemType>
AList<ItemType>::AList(const AList<ItemType> &other) {
// TODO: create a list that is identical to `other`
count = other.count;
maxCnt = other.maxCnt;
ItemType arr[maxCnt];
items = new ItemType[maxCnt];
for(size_t i = 0; i < count; i++)
{
items[i] = arr[i];
}
delete [] items;
items = other.items;
}
/** Insert x at the front of list. */
template <typename ItemType> void AList<ItemType>::addFirst(ItemType x) {
// TODO:
if(count == maxCnt)
{
resize(count * RFACTOR);
}
for(size_t i = count; i > 0; i--)
{
items[i] = items[i - 1];
}
items[0] = x;
count = count + 1;
}
/** Return the first element in list. */
template <typename ItemType> ItemType &AList<ItemType>::getFirst() const {
// TODO:
return items[0];
}
/** Delete and return the first element in list. */
template <typename ItemType> ItemType AList<ItemType>::removeFirst() {
// TODO:
ItemType temp = items[0];
for(size_t i = 0; i < count - 1; i++)
{
items[i] = items[i + 1];
}
count = count - 1;
return temp;
}
} // namespace ds
#endif // __ALIST_H__
When I run my code, this is what the memory error states:
Output: 'original list: [1]; copy & getFirst: 1; resulting list: [1]'
217Expected: 'original list: [1]; copy & getFirst: 1; resulting list: [1]'
218Error(s):
219==190== Invalid free() / delete / delete[] / realloc()
220==190== at 0x483D74F: operator delete[](void*) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
221==190== by 0x10979A: ds::AList<int>::~AList() (AList.h:51)
222==190== by 0x10962E: main (test_driver.cpp:55)
223==190== Address 0x4da3cc0 is 0 bytes inside a block of size 4 free'd
224==190== at 0x483D74F: operator delete[](void*) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
225==190== by 0x10979A: ds::AList<int>::~AList() (AList.h:51)
226==190== by 0x109608: main (test_driver.cpp:96)
227==190== Block was alloc'd at
228==190== at 0x483C583: operator new[](unsigned long) (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
229==190== by 0x109761: ds::AList<int>::AList(unsigned long) (AList.h:47)
230==190== by 0x10939F: main (test_driver.cpp:55)
231==190==
main program:
#define CATCH_CONFIG_MAIN
#include "AList.h"
#include "catch.hpp"
#include <cstdlib>
#define SIZE 5
TEST_CASE("All") {
ds::AList<int> L;
// randomly add SIZE ints to the array
int nums[SIZE];
srand(time(0)); // setting the seed for rand()
for (int i = 0; i < SIZE; i++) {
nums[i] = rand() % 20 + 1; // generating random numbers by rand()
L.addLast(nums[i]);
}
SECTION("copy constructor") {
ds::AList<int> *K = new ds::AList<int>(L);
CHECK(L.size() == K->size());
CHECK(K->getLast() == nums[SIZE - 1]);
delete K; // this should not also delete L
}
SECTION("addFirst") {
L.addFirst(123);
L.addFirst(234);
CHECK(L.getFirst() == 234);
CHECK(L.get(2) == nums[0]);
}
SECTION("removeFirst") {
int x = L.removeFirst();
CHECK(x == nums[0]);
CHECK(L.getLast() == nums[SIZE - 1]);
}
}
If anyone could give any tips or suggestions on how I can fix this, it would be greatly appreciated!