Changing normal pointers to smart pointers

Forgetful (37)
Hi, I want to change all my pointers into unique pointers so once it passes out of scope all the pointers will be deleted and clears up memory space how can I change my pointers into unique pointers so they delete after passing out of scope and there will be no memory leaks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
 
#include <iostream>
#include <string>
#include <memory>
#include <fstream> 

class WordSearch {
  struct node {
    char letters;
    bool end = false;
    node* subs = nullptr;
    node* main = nullptr;
  };
  public:
  void add(const std::string& word) {
    node* temp1 = &this->start;
    for (auto i : word) {
      node* found = this->next(temp1, i);
      if (found) {
        temp1 = found;
      } else {
        node* temp2 = new node{i};
        if (temp1->main) {
          temp1 = temp1->main;
          while (temp1->subs) {
            temp1 = temp1->subs;
          }
          temp1->subs = temp2;
        } else {
          temp1->main = temp2;
        }
        temp1 = temp2;
      }
    }
    if (!temp1->end) {
      ++this->size;
      temp1->end = true;
    }
  }
  bool search(const std::string& word) const {
    const node* temp = &this->start;
    for (auto i : word) {
      temp = this->next(temp, i);
      if (!temp) {
        return false;
      }
    }
    return true;
  }
  private:
  node* next(const node* base, char letter) const {
    if (base->main) {
      if(base->main->letters == letter) {
        return base->main;
      }
      node* subs = base->main->subs;
      while (subs) {
        if (subs->letters == letter) {
          return subs;
        }
        subs = subs->subs;
      }
    }
    return nullptr;
  }
  node start{0};
  std::size_t size = 0;
};
int main(int argc, char** argv) {
  std::ifstream book(argv[1], std::ifstream::in);
  WordSearch text;
  for(std::string word; std::getline(book, word);)
    text.add(word);
    std::string looking_for;
    std::cout << "Is word in book: ";
    std::cin >> looking_for;
  while (looking_for != "y") {
    if(text.search(looking_for) == true) {
      std::cout << "The word " << looking_for << " is in the book";
    } else {
      std::cout << "The word " << looking_for << " is not in the book";
    }
    std::cout << std::endl << "Would you like to stop?:(type y to exit or type new word to search): ";
    std::cin >> looking_for;
  }
}
keskiverto (10402)
Your main() has one WordSearch object that is automatically destructed at the end.

1
2
3
4
 
class WordSearch {
  node start {0};
  std::size_t size = 0;
};

The WordSearch has two members, start and size that the destructor of WordSearch destructs.

1
2
3
4
5
6
 
WordSearch::node {
    char letters;
    bool end = false;
    node* subs = nullptr;
    node* main = nullptr;
  };

The node has four members. The letters and end are trivial.

Does subs or main point to a dynamically allocated object that should be deleted when this is destructed? Frankly, your code is hard to follow.
Forgetful (37)
I'm not sure if it is I was thinking of creating a destructor but using smart pointers seems more easier what do you think would be best?
coder777 (8444)
Actually the problem of smart pointer is that they are sensitive against circular dependency. Thus when node 1 points at node 2 and node 2 points at node 1 they are not automaticallly freed. You need to detach the pointers somewhere 'by hand'.
Forgetful (37)
so what would should I do to clear all memory leaks from my program?
coder777 (8444)
With destructors it is simple:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
class WordSearch {
  struct node {
    char letters;
    bool end = false;
    node* subs = nullptr;
    node* main = nullptr;

    ~node()
    {
      if(subs)
        delete subs;
    }
  };

  ~WordSearch()
  {
    if(start)
      delete start;
  }

...

  node *start{0}; // Better not mix pointers and not pointers here
};
Forgetful (37)
I run the code with 
1
2
3
4
5
6
7
8
9
10
 
~WordSearch()
  {
    if(start)
      delete start;
  }

...

  node *start{0}; // Better not mix pointers and not pointers here
};

and get two errors
WordSearch.cpp:27:13: error: assigning to 'WordSearch::node *' from
incompatible type 'WordSearch::node **'; remove &
temp1 = &this->start;
^~~~~~~~~~~~
WordSearch.cpp:53:17: error: cannot initialize a variable of type
'const WordSearch::node *' with an rvalue of type
'WordSearch::node *const *'
const node* temp = &this->start;
^ ~~~~~~~~~~~~
2 errors generated.
Forgetful (37)
also when I run just the node destructor I get
work(75281,0x11db805c0) malloc: *** error for object 0x7fd396c068f0: pointer being freed was not allocated
work(75281,0x11db805c0) malloc: *** set a breakpoint in malloc_error_break to debug
Abort trap: 6
Forgetful (37)
could I implement unique pointers if the program isn't circular dependency.
if I changed 
1
2
 
 std::unique_ptr<node> subs = nullptr;
 std::unique_ptr<node> main = nullptr;


how would I change these into a unique_ptr.

1
2
 
  node* temp1 = &this->start;
      node* found = this->next(temp1, i);


and

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
node* next(const node* base, char letter) const {
    if (base->main) {
      if(base->main->letters == letter) {
        return base->main;
      }
      node* subs = base->main->subs;
      while (subs) {
        if (subs->letters == letter) {
          return subs;
        }
        subs = subs->subs;
      }
    }
    return nullptr;
  }
  node start{0};

or I shouldn't change?
coder777 (8444)
Modify the code a bit:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 
  void add(const std::string& word) {
    node* temp1 = this->start;
    for (auto i : word) {
if(temp1)
{
      node* found = this->next(temp1, i);
      if (found) {
        temp1 = found;
      } else {
        node* temp2 = new node{i};
        if (temp1->main) {
          temp1 = temp1->main;
          while (temp1->subs) {
            temp1 = temp1->subs;
          }
          temp1->subs = temp2;
        } else {
          temp1->main = temp2;
        }
        temp1 = temp2;
      }
}
else
{
  this->start = new node{i};
  temp1 = this->start;
}
    }
    if (!temp1->end) {
      ++this->size;
      temp1->end = true;
    }
  }

1
2
3
4
5
6
7
8
9
10
 
  bool search(const std::string& word) const {
    const node* temp = this->start; // No &
    for (auto i : word) {
      temp = this->next(temp, i);
      if (!temp) {
        return false;
      }
    }
    return true;
  }
Not test...
Forgetful (37)
what about the node* main don't I have to delete that too? and since its 
1
2
3
 
if (start) {
delete start;
}

if I wanted to delete every memory leak could I do
1
2
3
 
while(start) {
delete start;
}
Last edited on
Repeater (3046)
1
2
3
 
while(start) {
delete start;
}


Calling delete on the same pointer more than once is a bad idea. In this case, if start is a valid pointer, you'll be attempting to call delete on it forever.
keskiverto (10402)
delete foo; does not modify the foo. The delete simply reads the value (memory address) from foo.

delete nullptr; is defined to be safe. No need to if-not-null-then-delete.

could I implement unique pointers if the program isn't circular dependency.

Yes. Why do you have IF there? Surely you know whether your data structure is cyclic or not? Is it a linked list?


and get two errors
WordSearch.cpp:27:13: error: assigning to 'WordSearch::node *' from
incompatible type 'WordSearch::node **'; remove &
temp1 = &this->start;
...

You did change the type of WordSearch::start radically, but you did not update the code that uses that member. Of course that breaks something.

When/if you do change node::main and/or node::subs into smart pointers, you have to update the using code too.

(It is possible to write generic code with templates, type aliases, etc that does not always break on changes.)
JLBorges (13770)
Using unique pointers:
Note that the implementation is slightly different: it uses a map to hold the child nodes (instead of a linked list),
the key in the map is the letter of interest. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
 
#include <iostream>
#include <string>
#include <memory>
#include <map>

struct WordSearch {


    void insert( const std::string& word ) {

         node* curr = root.get() ;

         for( char c : word ) {

            c = std::tolower(c) ;
            auto& next = curr->subs[c] ;
            if( next == nullptr ) next = std::make_unique<node>() ;
            curr = next.get() ;
         }

         curr->end_of_word = true ;
    }

    bool search( const std::string& word ) const {

         const node* curr = root.get() ;

         for( char c : word ) {

            c = std::tolower(c) ;

            const auto& iter = curr->subs.find(c) ;
            if( iter == curr->subs.end() ) return false ;
            else curr = iter->second.get() ;
         }

         return curr && curr->end_of_word ;
    }

    private:

        struct node {

            using pointer = std::unique_ptr<node> ;
            std::map< char, pointer > subs ;
            bool end_of_word = false ;
        };

        node::pointer root = std::make_unique<node>() ;
};

int main()
{
    WordSearch ws ;

    std::cout << "insert:\n    " ;
    for( std::string word : { "change", "any", "and", "an", "all", "pointers", "to", "unique", "pointers" } ) {

        std::cout << word << ' ' ;
        ws.insert(word) ;
    }
    std::cout << "\n\n" ;

    for( std::string word : { "change", "many", "always", "an", "AND", "pointers", "pointer" } )
        std::cout << word << " : " << ( ws.search(word) ? "found\n" : "not found\n" ) ;
}

http://coliru.stacked-crooked.com/a/70c3e45fe9d95075
Forgetful (37)
yes it is a linked list, im still getting many memory leaks not understanding how to clear up my memory leaks.
Last edited on
JLBorges (13770)
Using the same node structure as in the original code,
but replacing raw pointer members with unique pointers (to automate memory management):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
 
#include <iostream>
#include <string>
#include <memory>
#include <cctype>

struct WordSearch {

    void insert( const std::string& word ) {

        node* curr = root.get() ;

        for( char c : word ) {

            c = std::tolower(c) ;
            if( curr->letter == 0 ) curr->letter = c ; // null character, use this node

            node* n = curr->find(c) ;
            if( n == nullptr ) n = curr->append(c) ; // not found, append it

            // if subtrie is empty, add a sentinel node (makes the code easier)
            if( n->sub == nullptr ) n->sub = std::make_unique<node>(0) ;

            curr = n->sub.get() ; // go down to the next level
        }

        curr->end_of_word = true ;
    }

    bool search( const std::string& word ) const {

         const node* curr = root.get() ;

         for( char c : word ) {

            c = std::tolower(c) ;

            const node* n = curr ? curr->find(c) : nullptr ;
            if( n == nullptr ) return false ;
            else curr = n->sub.get() ;
         }

         return curr && curr->end_of_word ;
    }

    private:

        struct node {

            using pointer = std::unique_ptr<node> ;

            char letter ; // letters
            bool end_of_word = false ; // end
            pointer next ; // main
            pointer sub ; // subs

            explicit node( char c ) : letter(c) {}

            node* find( char c ) { // locate node with letter == c in this list

                if( c == letter ) return this ;

                for( node* p = next.get() ; p != nullptr ; p = p->next.get() )
                    if( p->letter == c ) return p ;

                return nullptr ; // not found
            }

            const node* find( char c ) const {

                return const_cast<node*>(this)->find(c) ;
            }

            node* append( char c ) { // append node with letter == c to this list

                node* p = this ;

                // bump p to get to the last node in the list
                while( p->next != nullptr ) p = p->next.get() ;

                p->next = std::make_unique<node>(c) ; // append a new node as the next of p

                return p->next.get() ;
            }
        };

        // note: a null char character is used for the sentinel leaf node
        node::pointer root = std::make_unique<node>(0) ;
};

int main()
{
    WordSearch ws ;

    std::cout << "insert:\n    " ;
    for( std::string word : { "change", "any", "and", "an", "all", "pointers", "to", "unique", "pointers" } ) {

        std::cout << word << ' ' ;
        ws.insert(word) ;
    }
    std::cout << "\n\n" ;

    for( std::string word : { "change", "many", "Any", "allot", "all", "an", "AND", "pointers", "point" } )
        std::cout << word << " : " << ( ws.search(word) ? "found\n" : "not found\n" ) ;
}

http://coliru.stacked-crooked.com/a/a23ea7718ac57730

Note that we use raw pointers where ownership (and the associated responsibility for correctly managing life-time) is not involved.
Topic archived. No new replies allowed.