How to fix "free(): double free detected in tcache 2" error?

Question

So, I have created a derived class template called unorderedSet that uses a pointer member variable to hold the location of an array on the heap (using new).

I am trying to overload the arithmetic operators to find both the intersection and union of two different unorderedSet objects, and the code I have written so far (with the help of another user on this site) manages that. However, upon running the program I get the error in the title. I will post the relevant parts of my code below.

template <class elemType>
class unorderedSet: public unorderedArrayListType<elemType>
{
public:
  void insertAt(int location, const elemType& insertItem);
  void insertEnd(const elemType& insertItem);
  void replaceAt(int location, const elemType& repItem);
  const unorderedSet<elemType> operator+(const unorderedSet<elemType>&);
  // Function to overload the binary operator + to find the union of a pair/group of sets
  // Postcondition: Finds the union of the sets

  const unorderedSet<elemType> operator-(const unorderedSet<elemType>&);
  // Function to overload the binary operator - to find the intersection of a pair/group of sets
  // Postcondition: Finds the intersection of the sets
  
  unorderedSet(int size = 100);
  unorderedSet(const unorderedSet<elemType>& otherSet);
  ~unorderedSet();
  
protected:
  elemType *set;
  int length;
  int maxSize;
};

template <class elemType>
const unorderedSet<elemType> unorderedSet<elemType>::operator+(const unorderedSet<elemType>& otherSet)
{
  unorderedSet<elemType> unSet(this->length + otherSet.length); // Initializes new set to hold values of the union set

  for (int i = 0; i < this->length; i++)
    unSet.insertEnd(this->list[i]); // Assigns all values of the activating operand to the union set using insertEnd
  
  for (int i = 0; i < otherSet.length; i++)
    unSet.insertEnd(otherSet.list[i]); // Calls insertEnd() to both check for duplicate values and add unique values to the union of the sets

  return unSet; // Should return the union set, but dumps the core at the moment
} // end operator overload

template <class elemType>
unorderedSet<elemType>::unorderedSet(int size) : unorderedArrayListType<elemType>(size)
{
  if (size <= 0)
  {
    cout << "The array size must be positive. Creating an array of the size 100. " << endl;

    this->maxSize = 100;
  }
  else
    this->maxSize = size;

    this->length = 0;

    set = new elemType[this->maxSize];
}

template <class elemType>
unorderedSet<elemType>::~unorderedSet()
{
  delete [] set;
}

template <class elemType>
unorderedSet<elemType>::unorderedSet(const unorderedSet<elemType>& otherSet)
{
  this->maxSize = otherSet.maxSize;
  this->length = otherSet.length;

  set = new elemType[this->maxSize];

  for (int j = 0; j < length; j++)
    set[j] = otherSet.set[j];
}

The following code comes from my test client program.

int main() 
{
  int intArr1[6] = {0, 1, 2, 3, 4, 5};
  unorderedSet<int> testIntSet1;

  for (int i = 0; i < (sizeof(intArr1) / sizeof(intArr1[0])); i++)
    testIntSet1.insertEnd(intArr1[i]);
  // Some more code before the function call
  
  int intArr2[6] = {0, 1, 3, 6, 7, 9};
  unorderedSet<int> testIntSet2, testIntSet3;

  for (int i = 0; i < (sizeof(intArr2) / sizeof(intArr2[0])); i++)
    testIntSet2.insertEnd(intArr2[i]);

  testIntSet3 = testIntSet1 + testIntSet2;
  // Some more code
}

I also have an assignment operator overload function in the base class of this class's base class. The code is as follows

template <class elemType>
const arrayListType<elemType>& arrayListType<elemType>::operator= (const arrayListType<elemType>& otherList)
{
  if (this != &otherList)    //avoid self-assignment
  {
    delete [] list;
    this->maxSize = otherList.maxSize;
    this->length = otherList.length;
 
    list = new elemType[this->maxSize];

    for (int i = 0; i < this->length; i++)
      list[i] = otherList.list[i];
  }

  return *this;
}

I have attempted to create another version of this in my unorderedSet class, but when I run it the testIntSet3 variable outputs nothing (not even some random garbage). I decided to remove it since the code seemed to at least function properly before.

Consider putting together a [mcve] that demonstrates the issue. It's almost always a rule of three violation when you have raw pointers — Retired Ninja, Oct 18 '21 at 02:32
Rule of 3 violation. Your `unorderedSet` is not safely copyable or assignable, yet you are doing that. Right here: `const unorderedSet operator-` and here: `const unorderedSet operator+`. The assignment operator, which you totally left out, should not be an afterthought (although it is easily implemented). — PaulMcKenzie, Oct 18 '21 at 02:32
I figured it had something to do with the rule of 3, but I'm not quite sure where I am going wrong. I believed that I was making deep copies in my program with the copy constructor and base class's assignment operator overload, is that not the case @PaulMcKenzie? — imt, Oct 18 '21 at 02:40
That assignment operator is for `arrayListType`, not `unorderedSet`. FYI, even that implementation is faulty for a variety of reasons. For example, you've deleted your `list`, before you know if `new[]` will be successful. If `new[]` throws an exception, you've messed up your object. Consider using [copy and swap](https://stackoverflow.com/questions/3279543/what-is-the-copy-and-swap-idiom), instead of what you're doing now. — PaulMcKenzie, Oct 18 '21 at 02:41

score 0 · Answer 1 · answered Oct 18 '21 at 03:05

One issue is that your orderedSet is missing the user-defined assignment operator:

template <class elemType>
class unorderedSet: public unorderedArrayListType<elemType>
{
  public:
      unorderedSet<elemType>& operator=(const unorderedSet<elemType>&);
  //...
};

That function needs to be implemented. The simplest way to do that, assuming you have a fully functional, working, copy constructor and destructor for unorderedSet, would be the following:

template <class elemType>
unorderedSet<elemType>& unorderedSet<elemType>::operator=(const unorderedSet<elemType>& otherSet)
{
   if (this != &otherSet)
   {
      unorderedSet<elemType> temp = otherSet;
      std::swap(temp.set, set);
      std::swap(temp.length, length);
      std::swap(temp.maxSize, maxSize);
   }
   return *this;
}

This uses the copy-swap idiom.

Your arrayListType's assignment operator should be written in the same fashipn.

The copy to `temp` can be shifted into the function parameter by declaring the parameter to take a copy rather than as a `const &`. The test for self-assignment is an unnecessary expense, since you are testing for a rare case all the time, and the modification of the parameter makes it pointless. Finally, add `using std::swap;` inside the function body, and then call `swap` instead of `std::swap` to allow ADL to choose a more type specific `swap` implementation if it is available. — jxh, Oct 18 '21 at 04:36
I have implemented your code, but now I have the issue where the return of the `operator+` function is nothing. I know that means my destructor/copy constructor aren't working properly. My code just seems to be a mess at the moment, but I'll continue tinkering with it until I find something — imt, Oct 18 '21 at 17:26

score 0 · Answer 2 · answered Oct 18 '21 at 05:01

Just to illustrate how valgrind can be used to diagnose this issue, I converted your program into a more minimal example (Try it online!).

When I run valgrind against the program (compiled as g++ -g x.cpp), there is output that reads:

^{_{==598== Invalid free() / delete / delete[] / realloc()

==598== at 0x4C3373B: operator delete[](void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==598== by 0x108E78: unorderedSet<int>::~unorderedSet() (x.cpp:68)

==598== by 0x108CC7: main (x.cpp:93)

==598== Address 0x5b80630 is 0 bytes inside a block of size 400 free'd

==598== at 0x4C3373B: operator delete[](void*) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==598== by 0x108E78: unorderedSet<int>::~unorderedSet() (x.cpp:68)

==598== by 0x108CBB: main (x.cpp:98)

==598== Block was alloc'd at

==598== at 0x4C3289F: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)

==598== by 0x108E40: unorderedSet<int>::unorderedSet(int) (x.cpp:62)

==598== by 0x108ECC: unorderedSet<int>::operator+(unorderedSet<int> const&) (x.cpp:41)

==598== by 0x108C97: main (x.cpp:98)}}

The valgrind output is saing that the address being freed points inside an already freed block. Hence, the issue is a double free.

Helpfully, it locates the two distinct locations of the double free.

93 unorderedSet<int> testIntSet2, testIntSet3;

and

98 testIntSet3 = testIntSet1 + testIntSet2;

The second free is detected on line 93, so the first one occurred on line 98. We deduce the destruction is from the temporary returned by operator+.

Since the destruction was not expected to trigger a double free, your hypothesis is that the copy was not deep for some reason, and the same pointer was used in the copy that was allocated in the original object.

How to fix "free(): double free detected in tcache 2" error?

2 Answers2