Use of smart pointers vs new and delete

[TheIdeasMan]

I hear all the time from experts that it is preferable to use smart pointers; one should never need to use new/delete in application code.

However I have run into a lot of trouble with std::unique, specifically with trying to sort containers like priority_queue, queue, deque. I gather there are restrictions on things like the iterators and compare functions.

So are there any general rules about when to use smart pointers, or when it is better to use new / delete?

The code I had a problem with is this and the following post: http://www.cplusplus.com/forum/beginner/214575/#msg999169

Note that code is my version of the OP's (globaltourist), so I wish to acknowledge him :+)

It seemed to work for the compression using a std::queue, except that it wasn't being being sorted - having it sorted is a mandatory requirement. Ideally I would like to have a std::priority_que. Can anyone see any changes to make to that code to make it work? Maybe there is more to it than converting new to make_unique and putting std::move everywhere? Or maybe the philosophy of doing that doesn't apply here?

In an earlier version I tried to implement with value / reference semantics: that is without smart pointers, just owning raw pointers in the node. But there was a problem in the makeTree function with local variables going out of scope and the object becoming invalid. Is there a way to prevent that happening?
http://www.cplusplus.com/forum/beginner/213653/2/#msg997702

Note that code is globaltourist's version of my suggestions. There seems to be some changing of the sense of struct functor (< or >)and the use of variations of front() or back() in the function makeTree. These two things sometimes oppose each other. In my mind < goes with front().

Thanks in advance with any help on this :+)

[JLBorges]

#include <iostream>
#include <memory>
#include <queue>
#include <vector>
#include <algorithm>
#include <cstdlib>

struct A
{
    A( int value = 0 ) : value(value) {}
    int value ;
    friend std::ostream& operator<< ( std::ostream& stm, A a ) { return stm << a.value ; }
    friend bool operator< ( A first, A second ) { return first.value < second.value ; }
};

int main()
{
    using ptr_a = std::unique_ptr<A> ;

    // predicate to compare the objects pointed to by unique pointers (note: nullptr < non null pointer)
    const auto cmp = [] ( const ptr_a& pa, const ptr_a& pb )
    {
        if( pa == nullptr ) return pb != nullptr ;
        else return pb != nullptr && *pa < *pb ;
    };

    std::vector<ptr_a> vec(2) ;
    for( int value : { 32, -56, 18, -75, 12, 52, -44, 71, 92, 25, -16 } )
        vec.push_back( std::make_unique<A>(value) ) ;

    // sort the vector 
    std::sort( std::begin(vec), std::end(vec), cmp ) ;
    for( const auto& p : vec ) if(p) std::cout << *p << ' ' ; else std::cout << "<nullptr> " ;
    std::cout << '\n' ;

    // create a priority queue of unique pointers note: we need to specify the predicate
    std::priority_queue< ptr_a, std::vector<ptr_a>, decltype(cmp) > pq(cmp) ;
    for( const auto& p : vec ) pq.push( p ? std::make_unique<A>( std::abs(p->value) ) : nullptr ) ;

    while( !pq.empty() ) // pop and print 
    {
        const auto& p = pq.top() ;
        if(p) std::cout << *p << ' ' ; else std::cout << "<nullptr> " ; ;
        pq.pop() ;
    }
    std::cout << '\n' ;
}

http://coliru.stacked-crooked.com/a/26cda0ec50d5fe29

[TheIdeasMan]

Thanks for your excellent reply, which I have just seen.

I had to manage to work out the following code on my own, but there are a few concepts in your code that I was missing. I will have to experiment a bit more :+) Namely to see if I can create a tree from the priority queue .....

#include <iostream>
#include <string>
#include<vector>
#include<memory>
#include<algorithm>
#include<queue>


struct node {
  int a = 0;
  std::string name;

  node() = default;
  node (const int Arg,  std::string nameArg)
    : a(std::move(Arg) ),
      name(std::move(nameArg) )
  {}

  node(node&& other)
    : a(std::move(other.a) ),
      name(std::move(other.name) )
  {}

  node& operator=(const node&) = default;

  friend bool operator<(const node& lhs, const node& rhs) {return lhs.a < rhs.a;}


};

std::ostream& operator<<(std::ostream& os, const node& obj) {
  std::cout << obj.a << " " << obj.name << "\n";
  return os;
}

bool compare_ptr(const node& lhs, const node& rhs) {return lhs.a < rhs.a;}

int main()
{
  std::priority_queue<node>  Data;

  Data.emplace(10, "Fred");
  Data.emplace(4, "Ginger");
  Data.emplace(9, "Trevor");
  Data.emplace(2, "Sheryl");
  Data.emplace(8, "Bloke");
  Data.emplace(1, "Kevin");
  Data.emplace(7, "Anne");
  Data.emplace(3, "Bruce");
  Data.emplace(6, "Elvis");
  Data.emplace(5, "Diana");

  //std::sort(std::move(Data.front() ) ,  std::move(Data.back() ) , compare_ptr );

  while (!Data.empty() ) {
      std::cout << Data.top();
      Data.pop();
    }

  return 0;
}

[mbozzi]

Here's a way to Huffman-encode strings using std::priority_queue.

# include <algorithm>
# include <iomanip>
# include <iostream>
# include <iterator>
# include <map>
# include <memory>
# include <queue>

template<typename Iter>
auto symbol_frequencies(Iter begin, Iter end) {
  using value_type = typename std::iterator_traits<Iter>::value_type;
  std::map<value_type, std::size_t> result;
  std::for_each(begin, end, [&](auto const elt){ ++result[elt]; });
  return result;
}

/* Huffman tree node */
struct Node {
  Node(char sym, int freq,
       std::unique_ptr<Node>&& l = nullptr,
       std::unique_ptr<Node>&& r = nullptr)
    : sym(sym) , freq(freq)
    , lchild{std::move(l)} , rchild{std::move(r)}
  {}
  char sym{}; /* Character represented by the node */
  int  freq;  /* Number of times the symbol appears */
  std::unique_ptr<Node> lchild, rchild;
};

// print a node
inline std::ostream& operator<<(std::ostream& s, Node const& n)
{ return s << "('" << n.sym << "', " << n.freq << ')'; }

// compare two nodes through unique_ptrs
struct Cmp {
  inline bool operator()(std::unique_ptr<Node> const& lhs,
                         std::unique_ptr<Node> const& rhs)
  { return lhs->freq > rhs->freq; }
};

template<typename Iter>
std::unique_ptr<Node> huffman_tree(Iter begin, Iter end) {
  using value_type = std::unique_ptr<Node>;
  std::priority_queue<value_type, std::vector<value_type>, Cmp> heap;

  for (auto sym_freq: symbol_frequencies(begin, end))
    heap.push(std::make_unique<Node>(sym_freq.first, sym_freq.second));

  while (heap.size() > 1) {
    value_type l = std::move(const_cast<value_type&>(heap.top())); heap.pop();
    value_type r = std::move(const_cast<value_type&>(heap.top())); heap.pop();

    heap.emplace(std::make_unique<Node>('\0', l->freq + r->freq,
                                        std::move(l), std::move(r)));
  }
  
  return heap.size()? std::move(const_cast<value_type&>(heap.top())): nullptr;
}

void display_codes(std::unique_ptr<Node> const& n, std::string acc = "") {
  if (!n) return;

  if (n->sym) {
    std::cout << n->sym << " = " << std::setw(8) << std::left << acc
              << ' ' << *n << '\n';
  }

  display_codes(n->lchild, acc + "0"); // DFS
  display_codes(n->rchild, acc + "1");
}

int main() {
  std::string line; std::getline(std::cin, line);
  display_codes(huffman_tree(line.begin(), line.end()));
}

http://coliru.stacked-crooked.com/a/2479616fe6771d1d

Keep in mind that std::pop_heap means you can accomplish the same thing without having to perform acrobatics with const_cast. The only disadvantage is that you must maintain the heap invariant manually.

I had a hard time finding out what was supposed to own what -- i.e., what's a unique_ptr and what's not. I found it awkward to build the tree from a given collection of nodes instead of creating the nodes as you go: given that one root node will end up uniquely owning all the other nodes, all of those nodes must have a dynamic lifetime (to avoid the issue in your first link) and be uniquely owned .

Also worth mentioning is that while new+delete are error prone, it wouldn't be too hard to do this with only raw pointers in an exception-safe manner: the only data carried by the nodes is POD, and (usually) nothing will throw in a fixed-size container of POD.

http://coliru.stacked-crooked.com/a/2479616fe6771d1d

[TheIdeasMan]

@mbozzi

Thanks for your excellent reply - that has cleared up some concepts for me. Cheers :+)

[TheIdeasMan]

Hi,

I have been thinking more about POD types throwing exceptions: the "unusual" side of mbozzi's comment above. Is it possible they still could do that under some circumstances? For example if a variable has an unsigned type, and somehow an attempt is made to assign a negative value to it at runtime, then it will throw. So the thing to do there is to have code to check that the value is positive before assigning. But if that code doesn't exist .... And I get the feeling that this situation could sneak up on one in surprising ways?

[JLBorges]

> Is it possible they still could do that under some circumstances?

On their own, POD types do not throw exceptions.
(POD types are compatible with types used in C, and can be safely passed to components written in C).

It does not mean that operations on POD types will never throw.
For example, operator new may still throw std::bad_alloc; if we push a POD type into a priority_queue, while the trivial copy/move constructor of the POD will never throw on their own, the priority queue (the allocator for the container) may still throw std::bad_alloc

It is not a good idea to use raw owning pointers even for pod types . Even if we carefully program around all the places when an exception could be thrown to clean up the mess that we created, the code very soon becomes brittle; in practice, non-extensible and non-maintainable over a period of time.

Raw owning pointers should be limited to the implementations of components which are solely or primarily concerned with management of dynamically allocated resources.

[TheIdeasMan]

@JLBorges

Splendid, thank you :+)