0

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!

Michael
  • 1
  • 1
  • `ItemType arr[maxCnt];` -- This is not valid C++. Arrays in C++ must have their size denoted by a compile-time constant, not a runtime variable. As a matter of fact, that illegal declaration defeats the purpose of your class. Also, you are missing a user-defined assignment operator. – PaulMcKenzie Mar 26 '21 at 04:21
  • `#ifndef __ALIST_H__` -- Also, in C++, identifiers starting with a double underscore are reserved for the system. You are not supposed to create identifiers like `__ALIST_H__`. Another point -- there is no code to "run" in the code you posted. Where is the `main` program that tests your class that duplicates the error? – PaulMcKenzie Mar 26 '21 at 04:25
  • sorry I forgot to include the main program, I will fix it right now – Michael Mar 26 '21 at 04:33
  • `ItemType arr[maxCnt];` -- Get rid of this line and rewrite your copy constructor with no idea that code like that is valid C++ code. It will force you to figure out the proper way to code the copy constructor. Also, due to that code not being valid C++, maybe you would have been docked more points by having it in your code. – PaulMcKenzie Mar 26 '21 at 04:36
  • Michael - please post a [mcve] that we can cut and past into our IDEs locally and compile. What you've provided doesn't compile. For example, your `TEST_CASE` macro isn't something we can compile locally. – selbie Mar 26 '21 at 05:31
  • @PaulMcKenzie: 1) Arrays in C++ no not need to be declared with a size that is a compile time constant. Read: https://en.cppreference.com/w/cpp/language/array - it was a constant up until c++14. If his code was wrong, it wouldn't compile at all. 2) It's perfectly fine to use preprocessors symbols containing leading underscores. These don't make it into the c++ compilation. Also if you happen to declare a variable with two leading underscores and it somehow happens to clash with an impl variable, then you would receive a compilation error. – David Bien Mar 26 '21 at 05:39
  • Hi, all. Sorry I guess I should have initially include the full code on here, I will edit the post so that the fully runnable code is on here – Michael Mar 26 '21 at 05:47
  • @Michael: You are double deleting memory. You assign items to other.items in this statement: "items = other.items;" This means that both object refers to the same set of items. So when other gets destructed it destructs the items first, then when this gets destructed it deletes the same set of items.\ – David Bien Mar 26 '21 at 05:49
  • @Michael: Look at your copy constructor code. It isn't correct at all - the loop isn't doing anything at all - it is looping over a local variable which is an uninitialized array. I would suggest rewriting the copy constructor for AList from scratch. You need to: 1) Set the size of this's member item array to the size of other's. Then move through other's item array copying items from it to this. This is not at all what the code is doing. – David Bien Mar 26 '21 at 05:56
  • @DavidBien -- You are wrong. A compile-time expression, which is a constant, is required. [See this](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). The code "compiles" because variable-length arrays are an *extension* in many compilers, and unfortunately the compilers turn on this extension by default. Seems as if you were fooled by this, but you're not the first. Also, your claim of using two underscores -- this has always been prohibited by the C++ standard as being reserved for the implementation. – PaulMcKenzie Mar 26 '21 at 12:28
  • [Double underscore usage](https://stackoverflow.com/questions/224397/why-do-people-use-double-underscore-so-much-in-c). The users code is not guaranteed to compile successfully in any environment due to the usage of the double underscore. – PaulMcKenzie Mar 26 '21 at 12:42

0 Answers0