std::bad_alloc issues

[oinkerbob]

I am trying to use smart pointers to sort and re-link potentially large data elements. I have defined a class in my code for smart pointers, as listed below:

template <typename T>
class sptr {
    public:
        sptr(T *_ptr=NULL) { ptr = _ptr; }
        bool operator<(const sptr &rhs) const {return *ptr < *rhs.ptr;}
        operator T * () const { return ptr; }
    private:
//      friend class slist;
        T *ptr;
};

The object I'm trying to sort is a singly-linked list containing class objects with personal records (i.e., names, phone numbers, etc.). The singly-linked list class has an iterator class within it, as listed below.

template <class T>
class slist {
  private:
    struct node {
      node() { data=T(); next=NULL; }
      // add overloaded operator< code
      bool operator<(const node & rhs) const {return next < rhs.next;}

      T data;
      node *next;
    };

    node *head;
    node *tail;
    int N;

  public:
    slist();
    ~slist();

    void push_back(const T &);
    void sort();

    class iterator {
    public:
      iterator() : p(NULL) {}
      T & operator*() { return p->data; }
      iterator & operator++() { p = p->next; return *this; }
      bool operator!=(const iterator & rhs) const { return p != rhs.p; }

    private:
      friend class slist<T>;
      iterator(node *p) : p(p) {}
      node *p;
    };

    iterator begin() {return iterator(head->next);}
    iterator end() {return iterator(NULL);}
};

The following is my function within my list class for "sorting" using the smart pointers.

template <typename T>
void slist<T>::sort(){
  vector< sptr<node> > Ap(N);   // set up smart point array for list
  //slist<T>::iterator iter = begin();
  node *ptrtemp = head->next;
  sptr<node> sptrtemp = ptrtemp;
  for (int i = 0; i < Ap.size() - 1; i++){
    if (Ap[i] != NULL){
        Ap.push_back(sptrtemp);
        ptrtemp = ptrtemp->next;
        sptrtemp = ptrtemp;

        cout << "Temporary Address: " << sptrtemp << "    Vector Element Address: " << Ap[i];
    }
  }

  //sort(Ap.begin(), Ap.end()); // WE GON SORT

  ptrtemp = head;
  for (int j = 0; j < Ap.size() - 1; j++){  // relink using sorted result
    ptrtemp->next = Ap[j];
    sptrtemp = ptrtemp;
    Ap.push_back(sptrtemp);
  }
  ptrtemp->next = NULL;
}

tl;dr, I must have a bad smart pointer assignment somewhere because this code compiles, but when I run it, std::bad_alloc happens along with a core dump. Where am I leaking memory?

P.S., I know I have my call to std::sort(begin, end) commented out, but I didn't want to start sorting until I got the smart pointers going in the right place.

[JLBorges]

Read: http://www.informit.com/articles/article.aspx?p=25264

Till you are thoroughly familiar with implementing smart pointers, restrict yourself to the smart pointers provided by the standard library.
http://en.cppreference.com/w/cpp/memory/unique_ptr
http://en.cppreference.com/w/cpp/memory/shared_ptr

[oinkerbob]

Thanks for the reference, JLBorges. Unfortunately, my professor is restricting me from using standard's smart pointers. Instead, the assignment requires the use of the "sptr" class he defined in lecture (listed in my original post) to keep track of linked list objects after sorting.

[cire]

I think the problem with that "sptr" is that it is in no way smart. The only benefit it provides is the less than comparison. Since it doesn't seem designed to manage the ownership of the pointer contained, I don't think it is the source of your problem.

On line 3 of your sort function you create a vector with N elements (which are all default constructed so the contained pointer is null.) In the loop which begins on line 7, you iterator over all the elements in Ap but the last element and do nothing with them since those elements are null. After the loop, Ap still has N elements, and ptrtemp and sptrtemp still point to head->next.

The resulting sort on line 17, if uncommented, would sort N identical elements. (In other words, it would do nothing.)

In the loop that begins on line 20, you increase the size of Ap via push_back every iteration of the loop. However, you're looping on the size of Ap. That's a definite problem and is likely the cause of your bad_alloc.

[LB]

I'm confused as to how sptr is any different from a plain pointer?

[cire]

I'm confused as to how sptr is any different from a plain pointer?

From the way it is used, I would guess it was meant to facilitate the call to std::sort, although a lambda or functor seem like better choices.

[JLBorges]

template <typename T>
void slist<T>::sort()
{
    if( N > 1 ) // at least two nodes
    {
        std::vector< sptr<node> > Ap ;
        for( node* n = head ; n ; n = n->next ) Ap.push_back(n) ;
        std::sort( Ap.begin(), Ap.end() ) ;

        // link up the nodes in sorted order
        static_cast<node*>( Ap.back() )->next = nullptr ;
        for( std::size_t i = 0 ; i < N - 1 ; ++i )
            static_cast<node*>( Ap[i] )->next = Ap[i+1] ;

        head = Ap[0] ; // and make the first node the head
    }
}