c++ - 为 vector 类编写 sort() 方法

Question

我正在编写自己的 vector 类 Vector，其数据成员为:T* 数组、size_t vector_size 和 size_t capacity。我正在尝试创建一个 sort() 方法:

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

当数组中的元素是 int、char 等类型时，它工作正常。但是当我尝试对由 Vector 元素组成的 vector 进行排序时，它将无法编译。根据我所阅读的内容，我需要定义 <运算符以某种方式，但我真的不知道该怎么做...

我试过:

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

我的主要外观是这样的:

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;
}

这是我遇到的错误之一:

/usr/include/c++/4.6/bits/STL_algo.h:2212:4: 错误:'* __first < __pivot' 中的'operator<' 不匹配

Answer 1

您提供了带有错误签名的比较方法。您需要接受一个 const 引用或一个值，但不能接受对您的类型的(可修改的)引用，而前者应该是首选，除非它是原始类型。所以你的比较方法的签名应该是这样的:

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

这是因为 std::sort(以及许多其他方法)被设计为不修改内容。如果它们采用值(但这对于大型类型来说会很慢)或 const 引用，则可以保证这一点。

请注意，您定义的比较方法是比较 vector 的大小，而不是它们的内容。你所有的 vector 都是等长的。所以它们被 std::sort 视为相等。所以 std::sort 不会改变 v4...然后采取下一个等等......)，使用这个:

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;
}