Do I need to set my destructor methods when I am using shared pointers?

Question

I tried finding an answer but didn't see one for my particular problem. I am using shared pointers for a ternary search tree (to be used for a predictive text algorithm) and am running into some problems using shared pointers.

I've been away from C++ for 5 years, and let me tell you, Java does not help you learn pointers. I've had to relearn pointer material I learned in school 5-6 years ago over the past couple of days, and have successfully managed to destroy my code.

Here is most of the code I have:

// TernarySearchTree.cc

#include "stdafx.h"
#include "ternary_search_tree.h"

//Constructor
TernarySearchTree::TernarySearchTree() {
  num_nodes_ = 0;
  size_in_memory_ = 0;
  root_node_ = nullptr;
}

TernarySearchTree::TernarySearchTree(const TernarySearchTree& other) {
  num_nodes_ = other.num_nodes_;
  size_in_memory_ = other.size_in_memory_;

  TernarySearchTreeNode node;
  node = *other.root_node_;
  root_node_.reset(&node);
}

//Destructor
TernarySearchTree::~TernarySearchTree() {

}

//operators
TernarySearchTree& TernarySearchTree::operator=(const TernarySearchTree& other) {

  //TODO: swap idiom - create a copy of the node then swap the new one with it
  //do this first to provide exception safety
  TernarySearchTreeNode node;
  node = *other.root_node_;

  root_node_.reset(&node);
  num_nodes_ = other.num_nodes_;
  size_in_memory_ = other.size_in_memory_;

  return *this;
}

//Convert from string to c-style string
std::vector<char> TernarySearchTree::ConvertStringToCString(std::string str) {

  std::vector<char> wordCharacters (str.begin(), str.end());
  //remove newlines or tabs
  if (wordCharacters.back() == '\n' || wordCharacters.back() == '\t') {
    wordCharacters.pop_back();
  }
  wordCharacters.push_back('\0');
  return wordCharacters;
}

//Insert a node
TernarySearchTreeNode TernarySearchTree::InsertNode(TernarySearchTreeNode &currentNode, 
                                                    char character,
                                                    NodePosition position,
                                                    bool isRoot) {

  TernarySearchTreeNode newNode;
  newNode.set_character(character);

  if (!isRoot) {
    switch (position) {
    case NODE_POS_LEFT:
      currentNode.set_left_node(newNode);
      break;
    case NODE_POS_CENTRE:
      currentNode.set_centre_node(newNode);
      break;
    case NODE_POS_RIGHT:
      currentNode.set_right_node(newNode);
      break;
    default:
      break;
    }
  }

  return newNode;
}

//Insert a word
void TernarySearchTree::InsertWord(std::string word) {

  std::vector<char> characters = ConvertStringToCString(word);
  std::shared_ptr<TernarySearchTreeNode> currentNode = 0;
  bool isFirstCharacter = true;

  //Add each character to a node while traversing
  //Base case where there is no root node
  if (!root_node_) {

    for(std::vector<char>::iterator it = characters.begin(); it != characters.end(); ++it) {

      if (*it != '\0') {        
        //if it is the first character
        //root_node_ is equal to the address of new node
        if (isFirstCharacter) {
          std::cout << "HIHI";
          TernarySearchTreeNode node = InsertNode(*currentNode, *it, NODE_POS_CENTRE, true);
          root_node_.reset(&node);
          currentNode.reset(&node);
          isFirstCharacter = false;

        } else {
          TernarySearchTreeNode node = InsertNode(*currentNode, *it, NODE_POS_CENTRE, false);
          std::cout << std::endl << node.get_character();
          currentNode.reset(&node);
        }
      }
    }
    //If not base case, then we need to compare each character
  } else {
    currentNode = root_node_;
    for(std::vector<char>::iterator it = characters.begin(); it != characters.end(); ++it) {
      if (*it != '\0') {
        currentNode.reset(&SetNextNode(*currentNode, *it, *std::next(it, 1)));
      } else {
        currentNode->set_end_of_word(true);
      }
    }
  }
}

//Recursive function for obtaining/adding the next node when inserting a word
TernarySearchTreeNode TernarySearchTree::SetNextNode(TernarySearchTreeNode &currentNode, const char currentChar, const char nextChar) {

  //If characters match
  if (currentChar == currentNode.get_character()) {

    //if centre node exists
    if (currentNode.get_centre_node()) {
      return *(currentNode.get_centre_node());

      //Otherwise, create a new node and recall method on that node
    } else {

      //If not the end of the word, make a new node with the next letter
      if (nextChar != '\0') {
        return InsertNode(currentNode, nextChar, NODE_POS_CENTRE, false);

      } else {
        return currentNode;
      }
    }
    //If it is less, follow node on the left
  } else if (currentChar < currentNode.get_character()) {

    //if left node exists, recursive call
    if (currentNode.get_left_node()) {
      return SetNextNode(*(currentNode.get_left_node()), currentChar, nextChar);

      //Otherwise, create a new node and recall method on that node
    } else {
      return SetNextNode(InsertNode(currentNode, currentChar, NODE_POS_LEFT, false), currentChar, nextChar);
    }
    //Otherwise it is bigger, so take right path
  } else {

    //if right node exists, recursive call
    if (currentNode.get_right_node()) {
      return SetNextNode(*(currentNode.get_right_node()), currentChar, nextChar);

      //Otherwise, create a new node and recall method on that node
    } else {
      return SetNextNode(InsertNode(currentNode, currentChar, NODE_POS_RIGHT, false), currentChar, nextChar);
    }
  }
}

//Populate the TST from a word list/file
void TernarySearchTree::PopulateTreeFromTextFile(std::string fileName) {

  std::ifstream file;
  std::string line;
  file.open(fileName);

  if (file.is_open()) {
    //Assume text file has one word per line
    while (std::getline(file, line)) {
      InsertWord(line);
    }     
  }
}

//Search
bool TernarySearchTree::SearchForWord(std::string word) {
  return false;
}

int _tmain(int argc, _TCHAR* argv[])
{

  //Test
  TernarySearchTree tst;
  //Open file
  tst.PopulateTreeFromTextFile("simple.txt");

  //start at root and follow some paths
 std::cout << tst.get_root_node();


  /**std::vector<char> vec;
  vec.push_back('a');
  vec.push_back('c');
  std::vector<char>::iterator it = vec.begin();
  std::cout << *std::next(vec.begin(), 1);
  std::cout << (*it < 'c');
  it++;
  std::cout << *std::next(it, 0);
  std::cout <<  (*it < 'c');
  **/
  return 0;
}

and for the nodes:

/*TST node methods */
#include <iostream>
#include "ternary_search_tree_node.h"

/** ADD COPY CONSTRUCTOR*/
//Constructors
TernarySearchTreeNode::TernarySearchTreeNode() {

  character_ = '\0';
  end_of_word_ = false;
  left_node_ = nullptr;
  centre_node_ = nullptr;
  right_node_ = nullptr;
}

TernarySearchTreeNode::TernarySearchTreeNode(const TernarySearchTreeNode& other) {

  character_ = other.character_;
  end_of_word_ = other.end_of_word_;

  TernarySearchTreeNode leftNode;
  leftNode = *other.left_node_;
  left_node_.reset(&leftNode);

  TernarySearchTreeNode centreNode;
  centreNode = *other.centre_node_;
  centre_node_.reset(&centreNode);

  TernarySearchTreeNode rightNode;
  rightNode = *other.right_node_;
  right_node_.reset(&rightNode);
}

TernarySearchTreeNode::TernarySearchTreeNode(char character, bool end_of_word,
                                             TernarySearchTreeNode left_node, 
                                             TernarySearchTreeNode centre_node, 
                                             TernarySearchTreeNode right_node) {

  character_ = character;
  end_of_word_ = end_of_word;
  left_node_.reset(&left_node);
  centre_node_.reset(&centre_node);
  right_node_.reset(&right_node);
}

//Destructor
TernarySearchTreeNode::~TernarySearchTreeNode() {

  left_node_.reset();
  centre_node_.reset();
  right_node_.reset();

}

//operators
TernarySearchTreeNode& TernarySearchTreeNode::operator=(const TernarySearchTreeNode& other) {

  if (&other) {
    TernarySearchTreeNode leftNode;
    leftNode = *other.left_node_;
    TernarySearchTreeNode centreNode;
    centreNode = *other.centre_node_;
    TernarySearchTreeNode rightNode;
    rightNode = *other.right_node_;

    left_node_.reset(&leftNode);
    centre_node_.reset(&centreNode);
    right_node_.reset(&rightNode);

    character_ = other.character_;
    end_of_word_ = other.end_of_word_;
  }

  return *this;
}

//printing
std::ostream& operator<<(std::ostream& os, const TernarySearchTreeNode& obj)
{
  // write obj to stream
  char c = obj.get_character();
  bool b = obj.is_end_of_word();

  os << c << "\t is end of word: " << b;
  return os;
}

When I run in debug mode (Visual Studios), it is able to set the root node, but when it goes to input the second node, it crashes trying to delete "stuff" when currentNode calls .reset(&node) within the else statement of function InsertWord. Am I doing something wrong in the copy constructors or operator= methods, or the destructors? The cout line above it does print the correct letter, so it looks like the node is getting created properly.

The debug call stack shows:

TernarySearchTree.exe!std::_Ref_count_base::_Decref() Line 118 C++ TernarySearchTree.exe!std::_Ptr_base::_Decref() Line 347 C++ TernarySearchTree.exe!std::shared_ptr::~shared_ptr() Line 624 C++ TernarySearchTree.exe!std::shared_ptr::reset() Line 649 C++ TernarySearchTree.exe!TernarySearchTreeNode::~TernarySearchTreeNode() Line 50 C++ TernarySearchTree.exe!TernarySearchTreeNode::`scalar deleting destructor'(unsigned int) C++ TernarySearchTree.exe!std::_Ref_count::_Destroy() Line 161 C++ TernarySearchTree.exe!std::_Ref_count_base::_Decref() Line 120 C++ TernarySearchTree.exe!std::_Ptr_base::_Decref() Line 347 C++ TernarySearchTree.exe!std::shared_ptr::~shared_ptr() Line 624 C++ TernarySearchTree.exe!std::shared_ptr::reset() Line 649 C++ TernarySearchTree.exe!TernarySearchTreeNode::~TernarySearchTreeNode() Line 50 C++

TernarySearchTree.exe!TernarySearchTree::InsertWord(std::basic_string,std::allocator word) Line 105 C++ TernarySearchTree.exe!TernarySearchTree::PopulateTreeFromTextFile(std::basic_string,std::allocator fileName) Line 182 C++ TernarySearchTree.exe!wmain(int argc, wchar_t * * argv) Line 200 C++ TernarySearchTree.exe!__tmainCRTStartup() Line 533 C TernarySearchTree.exe!wmainCRTStartup() Line 377 C kernel32.dll!7592338a() Unknown [Frames below may be incorrect and/or missing, no symbols loaded for kernel32.dll]
ntdll.dll!77599f72() Unknown ntdll.dll!77599f45() Unknown

Thanks for any help you can provide! And let me know if there is anythign else you need me to provide (the text file I am reading in just has the word cornin it).

Answer 1

Your problem is that you're using Java style in C++. Unlike in Java where everything is essentially a pointer, in C++ you have to think about the difference between values, references, pointers, and object lifetime.

This function is bad:

TernarySearchTreeNode::TernarySearchTreeNode(char character, bool end_of_word,
                                             TernarySearchTreeNode left_node, 
                                             TernarySearchTreeNode centre_node, 
                                             TernarySearchTreeNode right_node) {

  character_ = character;
  end_of_word_ = end_of_word;
  left_node_.reset(&left_node);
  centre_node_.reset(&centre_node);
  right_node_.reset(&right_node);
}

You are taking TernarySearchTreeNode objects by value, then putting their address into a shared_ptr. The point of a shared_ptr to to take ownership of a dynamically allocated object (one created using new) and delete it when the reference count goes to zero. The objects above (left_node, etc) are stack objects that will go out of scope at the end of the function. When you put their address into a shared_ptr, it will then try to delete those objects later, but they no longer exist.

As far as recommending how to fix this, there is a whole lot going on here where the assumptions are just off. For instance, can a child node have more than one parent? Does it actually make sense to copy nodes?

I'll assume for the moment that copying nodes makes sense, so using shared_ptr is reasonable. In that case we might start here:

TernarySearchTreeNode TernarySearchTree::InsertNode(std::shared_ptr<TernarySearchTreeNode currentNode>, 
                                                    char character,
                                                    NodePosition position,
                                                    bool isRoot) {

  auto newNode = std::make_shared<TernarySearchTreeNode>();
  newNode->set_character(character);

  if (!isRoot) {
    switch (position) {
    case NODE_POS_LEFT:
      currentNode->set_left_node(newNode);

Then all of your functions like set_left_node should also take std::shared_ptr<TernarySearchNode> as parameters. You should not be calling reset(), which exists to allow a shared_ptr to take ownership (refcount == 1) of a free pointer. shared_ptr works by incrementing the reference count on copy and dereferencing in the destructor. When you dereference the pointer and then take the address, you are working around the shared_ptr.