Function-call operator overload & destructor help

Question

I think my destructor is good now... but still not sure how to call print_set from within the operator() overload.

It outputs as it should, but I feel like there is an easy way to just call print_set from within the function call overload... can't seem to get things how I want them..

Header file:

/**
 * disjoint_sets class declaration
 *
 */

#include<ostream>
#include<string>
#include<list>

class disjoint_sets 
{
public:

  disjoint_sets(int n); //n is the maximum int that can be in a set, so arrays need to be of size n+1
  ~disjoint_sets();

  bool make_set(int n);
  int find_set(int u);
  bool union_set(int u, int v);
  void print_set(std::ostream& out, int u); //e.g. { 1, 2, 4, 8, 10, }

  operator std::string(); //e.g. "{ { 1, 2, 4, 8, 10, }, { 3, 6, }, { 5, }, { 7, }, { 9, }, }"

private:
  typedef std::list<int>* listptr;

  int* p;       //parent array
  int* rank;    //rank array
  listptr* set; //array of pointers. Each set[i] is a pointer is to a list<int> containing the integers in the i'th set
  int size;     //the size i.e. maximum int that can be in a set

};

Implementation:

/**
 * disjoint_sets class implementation
 *
 */

#include <iostream>
#include <istream>
#include <sstream>
#include <string>
#include <list>

#include "disjoint.hpp"



/*********************
 * CONSTRUCTOR
 *********************/
disjoint_sets::disjoint_sets(int n)
{
  size = n;

  // initialize all arrays to same size (n+1)  
  p      =    new int[n+1];
  rank   =    new int[n+1];
  set    =    new listptr[n+1];

  // loop through set (array of pointers) and initialize
  //   each element to an empty list
  for (int i(1); i <= n; i++)
    {
      set[i] = new std::list<int>;
    }
}



/*********************
 * DESTRUCTOR
 *********************/
disjoint_sets::~disjoint_sets()
{
  delete[] p;
  delete[] rank;

  // delete each element in the set first, then delete the set.
  for(int i(1); i<size+1; i++)
    {
      set[i]->clear();  
    }
  delete[] set;
}



/*********************
 * MAKE_SET
 *********************/
bool disjoint_sets::make_set(int n)
{
  // if parent already exists
  if (p[n] != 0)
    {
      return false;
    }

  // else we need to make a set  
  else
    {
      // make itself the parent
      p[n] = n;

      // use push_front to add the int to front of set
      set[n]->push_front(n);

      return true;
    }
}



/*********************
 * FIND_SET
 ***********************/
int disjoint_sets::find_set(int u)
{
  while (u != p[u])
    {
      u = p[u];
    }

  // returns parent  
  return u;
}



/*********************
 * UNION_SET
 *********************/
bool disjoint_sets::union_set(int u, int v)
{
  // assign parents to u, v
  u = find_set(u);
  v = find_set(v);


  // return false if parent is 0, list is empty
  if (u == 0 or v == 0)
    {
      return false;
    }


  // if u's height is less than v's (not in same set)
  if (rank[u] < rank[v])
    {
      // point u's parent to v (merge them)
      p[u] = v;

      // splice u out
      (*set[v]).splice((*set[v]).end(), (*set[u]));

      return true;
    }

  // u's height is greater than or equal to v's height  
  else
    {
      // set v's parent to u
      p[v] = u;

      // splice v out
      (*set[u]).splice((*set[u]).end(), (*set[v]));

      return true;
    }


  // if ranks are equal
  if (rank[u] == rank[v])
    {
      // increment rank of u
      rank[u]++;

      return true;
    }
}



/*********************
 * PRINT_SET
 *********************/
void disjoint_sets::print_set(std::ostream& out, int u)
{
  // begin brace for set
  out << "{ ";

  // loop through with iter, seperate with comma
  for (std::list<int>::iterator iter((*set[u]).begin()); iter != (*set[u]).end(); iter++)
    {
      out << *iter << ", ";
    }

  // end brace for set
  out << "}";
}



/*********************
 * STRING CONVERSION
 *********************/
disjoint_sets::operator std::string()
{
  // sstream variable
  std::stringstream text; 


  // pointer to int array
  int *test;
  test = new int[size+1];


  // opening paren
  text << "{ ";


  // start main loop through the array
  for (int i(1); i <= (size + 1); i++)
    {

      // if the root is empty
      if (test[find_set(i)] == 0)
        {

          // set to anything != 0?
          test[find_set(i)] = 10;


          // check if list is empty
          if (set[i]->empty())
            {
              text << "";
            }


          else
            {
              // individual set opening parenthesis
              text << "{ ";

              // use iterator to loop through and load up the stringstream, separate w/ comma
              for (std::list<int>::iterator iter((*set[i]).begin()); iter != (*set[i]).end(); iter++)
                {
                  text << *iter << ", ";
                }

              // individual set closing parenthesis w/ proper punctuation
              text << "}, ";    
            }
        }  
    }

  // closing parenthesis
  text << "}";    

  delete[] test;  

  return text.str(); 
}

Driver:

#include<iostream>

#include "disjoint.hpp"


int main() 
{
  using namespace std;

  disjoint_sets ds(12);

  for( int i=1; i <= 10; ++i)
    ds.make_set(i);

  ds.union_set(1,2);
  ds.union_set(2,4);
  ds.union_set(1,8);
  ds.union_set(3,6);
  ds.union_set(2,10);

  //{ { 1, 2, 4, 8, 10, }, { 3, 6, }, { 5, }, { 7, }, { 9, }, }
  cout << string(ds) << endl;
}

Answer 1

Just focusing on the destructor:

// delete[] set; // need special conditions for this?

Yes, you need to delete each element in the set first and then delete the set. Use std::shared_ptr if you are not interested to do the memory management.

As a hint: You might get better answers if you ask concrete questions.