CODEWITHSUNDEEP
c++templatessortingvectoroperator-keyword
Smajjk
Smajjk

Reputation: 394

Writing a sort() method for a vector class

I am writing my own vector class, Vector, with the data members: T* array, size_t vector_size and size_t capacity. I am trying to create a sort() method:

template <class T>                                                                                                 
void Vector<T>::sort(bool ascending)                                                                                 
{                                                                                                                   
    std::sort(array,array+vector_size);                                                                              
    if(ascending==false)                                                                                             
        std::reverse(array,array+vector_size);                                                                      
}

It works fine when the elements in the array are of type int, char etc. But when I try to sort a vector consisting of Vector elements it won't compile. From what I have read I need to define the <operator in some way, but I really don't know how to do that...

I have tried:

template <class T>
bool Vector<T>::operator<(Vector<T> & source) const
{
    return (vector_size < source.vector_size);
}

My main look like this:

int main() {
    Vector<int> v1(5,1);
    Vector<int> v2(7,2);
    Vector<int> v3(3,3);
    Vector<Vector<int>> v4;
    v4 = {v1,v2,v3};
    v4.sort(1);
return 0;
}

This is one of the errors I get:

/usr/include/c++/4.6/bits/stl_algo.h:2212:4: error: no match for ‘operator<’ in ‘* __first < __pivot’

Upvotes: 3

Views: 557

Answers (3)

leemes
leemes

Reputation: 45675

You provided a comparison method with the wrong signature. You need to accept a const reference or a value, but not a (modifiable) reference to your type, while the former should be preferred unless it's a primitive type. So the signature of your comparison method should look like this:

template <class T>
bool Vector<T>::operator<(const Vector<T> & source) const
{
    return (vector_size < source.vector_size);
}

This is because std::sort (and a lot of other methods) are designed to not modify the contents. This is guaranteed if they take a value (but this will be slow for large types) or a const reference.

Note that you defined the comparison method to compare the size of the vectors, not their contents. All your vectors are of equal length. So they are treated to be equal by std::sort. So std::sort wouldn't change v4... If you intend to compare the contents in a way similar to string comparison (the first entry counts first, if equal then take the next and so on...), use this:

template <class T>
bool Vector<T>::operator<(const Vector<T> & source) const
{
    for(int i = 0; i < size && i < source.size; ++i) {
        if(*this[i] < source[i])
            return true;
        else if(source[i] < *this[i])
            return false;
    }
    // You have to decide what to do if the length isn't equal.
    // But if the vectors are really equal than return false:
    if(size == source.size)
        return false;
}

Upvotes: 3

Kevin Grant
Kevin Grant

Reputation: 5431

One thing you'd need is to use const in the parameter to your operator, otherwise it can't match anything that is read-only (which would be the common case).

Keep in mind though that sorting vectors-of-vectors would copy entire vectors every time swaps occur. This will not be particularly efficient. If the vectors were stored separately and you had something like vector-of-pointer-to-vector, at least the sorting would be faster.

Be sure to read the definition of "strict weak ordering", too. It is very important for the ordering to be consistent with itself, or standard algorithms like std::sort() can badly misbehave (to the point of corrupting memory in some implementations).

Upvotes: 1

ltjax
ltjax

Reputation: 15997

Your forgot a const!

template <class T>
bool Vector<T>::operator<(const Vector<T> & source) const // <- here
{
    return (vector_size < source.vector_size);
}

Upvotes: 1

Related Questions