C++ std::sort does not work with pointer to vector

Question

After much searching, it seems that a pointer to a vector is not the best thing to do. However, the following code bugs me too much:

  1 #include <stdio.h>
  2 #include <algorithm>
  3 #include <vector>
  4
  5
  6 class Hdr
  7 {
  8     public:
  9     std::vector<long> *order;
 10     bool operator()(long i1, long i2) const;
 11     Hdr(int N);
 12     ~Hdr();
 13 };
 14
 15 Hdr::Hdr(int N)
 16 {
 17     order = new std::vector<long>(N,0);
 18     for(int k=0;k<N;k++) (*order)[k] = -k;
 19 };
 20
 21 Hdr::~Hdr()
 22 {
 23     order->clear();
 24     delete order;
 25 };
 26
 27 bool Hdr::operator()(long i1, long i2) const
 28 {
 29     return (i1<i2);
 30 };
 31
 32 int main(void)
 33 {
 34     Hdr mhdr(1000);
 35     std::sort(mhdr.order->begin(),mhdr.order->end(),mhdr);
 36
 37     printf("value at 300 = %d\n",mhdr.order->at(300));
 38 };

with gcc 4.3 on Linux, the executable gives "double free or corruption". So I commented out line 24, and it throws 'std::out_of_range'. Apparently, line 35 (sort) messes everything up when a dynamically allocated vector is passed to std::sort. Or I just had a big blunder somewhere. Please help!! If I change line 9 to std::vector order then things seem fine; however I can't keep wondering what went wrong with the pointer to vector.

Answer 1

You are not following the Rule of Three: you haven't defined a copy constructor and copy assignment operator for your class.

You make a copy of mhdr when you pass it as the functor to std::sort. The order data member of that copy and of the original mhdr both point to the same object. The copy is destroyed, causing the object pointed to by its order to be deleted, then the original is destroyed when main ends, causing a double deletion, undefined behavior, and other fun things to happen.

(In fact, even more copies might be made inside of std::sort, so it might crash even earlier.)

Why are you dynamically allocating the std::vector? If there are any good reasons to do that, there are very few of them.

Answer 2

You're passing mhdr by value to std::sort(), with a default copy constructor that duplicates the pointer to your vector, and deletes it when that instance goes out of scope. That's not what you want.

You should probably use a comparator object distinct from the thing holding that vector, or reference count the pointer to the vector (using an appropriate smart pointer class, probably).

Answer 3

You don't need bool operator()() on that class - the longs can be sorted with default comparison (see std::sort). The runtime-reported problem is that the third argument is copied, and you don't have a copy constructor, nor copy assignment operator in Hdr (see rule of three).

Answer 4

The problem is that std::sort takes the comparison functor by value, so the destructor will be invoked for the copy and for the original mhdr object, and thus, since you havent supplied a copy constructor, order will be deleted twice.

The easiest fix would be to use a normal std::vector instead of a pointer to a std::vector. By doing this the implicit copy constructor will work for you.

Beside that you could define your copy constructor and make a deep copy of the order vector, or use a smart pointer to wrap it.

But the best solution would be to make the compare function a static member function (or a global function) and using that as parameter for std::sort. You should always use dedicated functor classes. DONT just add an operator() to a class which already does something else. It might work as expected, but most certainly it wont be as effective as a dedicated functor class, because much more copy-operations might be needed (for member variables, like in this case). Of course you still should fix the copy-constructor of the Hdr class (or just declare a copy-ctor without definition, to remove the implicit one, which fails in this case).

Answer 5

As others mentioned, the main cause of it is that when you pass mhdr as the comparator, you are making a copy. This copy contains a pointer to the same vector. When that copy gets destroyed, that vector gets destroyed, corrupting the collection that was between your iterators.

This would have been apparent if you prevented copying and assignment by declaring those operators private and not implementing then.

The reason you got into this mess is that your Hdr class has two distinct functions -- maintaining the vector, and having the comparator function. Classes should do one thing, and one thing well.

The solution below fixes these problems, as well as some other problems like exposing data members as public (though I preserved the pointer to the vector since I suspect you were trying to illustrate something about that case even though I agree with the other answerers that this is a questionable decision)

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <memory>

class Hdr
{
    public:
          Hdr(int N);
        ~Hdr();

        typedef std::vector<long>::iterator OrderIt;
        OrderIt orderBegin();
        OrderIt orderEnd();
        long orderAt(int index) const;

    private:
        Hdr& operator=(const Hdr&);
        Hdr(const Hdr&);

        std::auto_ptr<std::vector<long> > order;
};

class Comparator
{
    public:
        bool operator()(long i1, long i2) const;

};

Hdr::Hdr(int N)
{
    order = std::auto_ptr<std::vector<long> >(new std::vector<long>(N,0));
    for(int k=0;k<N;k++) 
    {
        (*order)[k] = -k;
    }
};

Hdr::~Hdr()
{
    order->clear();
};

Hdr::OrderIt Hdr::orderBegin()
{
    return order->begin();
}

Hdr::OrderIt Hdr::orderEnd()
{
    return order->end();
}

long Hdr::orderAt(int nIndex) const
{
    return order->at(nIndex);
}

bool Comparator::operator()(long i1, long i2) const
{
    return (i1<i2);
};

int main(void)
{
    Hdr mhdr(1000);
    std::sort(mhdr.orderBegin(),mhdr.orderEnd(), Comparator());
    printf("value at 300 = %d\n",mhdr.orderAt(300));
};