C++ STL:根据一个向量的内容对另一个向量进行自定义排序[重复]

xqk2d5yq  于 2023-05-30  发布在  其他
关注(0)|答案(6)|浏览(78)

此问题已在此处有答案

How can I sort two vectors in the same way, with criteria that uses only one of the vectors?(9个回答)
9年前关闭。
这可能是最好的陈述作为一个例子。我有两个向量/列表:

People = {Anne, Bob, Charlie, Douglas}
Ages   = {23, 28, 25, 21}

我想使用类似sort(People.begin(), People.end(), CustomComparator)的东西根据年龄对People进行排序,但我不知道如何编写CustomComparator来查看Ages而不是People。

0tdrvxhp

0tdrvxhp1#

明显的方法

通常的处理方法不是创建两个单独的向量/列表,而是创建一个包含名称和年龄的对象的向量/列表:

struct person { 
    std::string name;
    int age;
};

要获得基于年龄的排序,请传递一个查看年龄的比较器:

std::sort(people.begin(), people.end(), 
          [](auto const &a, auto const &b) { return a.age < b.age; });

在旧的C++(C++11之前,所以没有lambda表达式)中,可以将比较定义为operator<的成员重载,或者定义为函数对象(重载operator()的对象)来进行比较:

struct by_age { 
    bool operator()(person const &a, person const &b) const noexcept { 
        return a.age < b.age;
    }
};

然后你的排序看起来像这样:

std::vector<person> people;
// code to put data into people goes here.

std::sort(people.begin(), people.end(), by_age());

至于是为类定义operator<,还是像我上面展示的那样使用一个单独的比较器对象,这主要是一个问题,即是否有一个对这个类“明显”的单一顺序。
在我看来,按年龄对人进行分类并不一定是显而易见的。然而,如果在你的程序上下文中,很明显,除非你明确指定,否则将按年龄对人进行排序,那么将比较实现为person::operator<而不是在一个单独的比较类中实现比较是有意义的。

其他方法

尽管如此,在一些情况下,在排序之前将数据合并到结构中确实是不切实际或不可取的。
如果是这样的话,你有几个选择要考虑。如果因为你使用的键太昂贵而无法交换(或者根本不能交换,尽管这很少见),所以普通的排序是不切实际的,你可以使用一种类型,在这种类型中,你存储要排序的数据沿着与每个键相关联的键集合的索引:

using Person = std::pair<int, std::string>;

std::vector<Person> people = {
    { "Anne", 0},
    { "Bob", 1},
    { "Charlie", 2},
    { "Douglas", 3}
};

std::vector<int> ages = {23, 28, 25, 21};

std::sort(people.begin(), people.end(), 
    [](Person const &a, person const &b) { 
        return Ages[a.second] < Ages[b.second];
    });

你也可以很容易地创建一个单独的索引,按照键的顺序排序,然后使用该索引来读取相关的值:

std::vector<std::string> people = { "Anne", "Bob", "Charlie", "Douglas" };   
std::vector<int> ages = {23, 28, 25, 21};

std::vector<std::size_t> index (people.size());
std::iota(index.begin(), index.end(), 0);

std::sort(index.begin(), index.end(), [&](size_t a, size_t b) { return ages[a] < ages[b]; });

for (auto i : index) { 
    std::cout << people[i] << "\n";
}

但是,请注意,在本例中,我们根本没有对项目本身进行排序。我们刚刚根据年龄对索引进行了排序,然后使用索引索引到我们想要排序的数据数组中--但是年龄和姓名都保持原来的顺序。
当然,在理论上,你可能会遇到这样一种奇怪的情况,上面的方法都不起作用,你需要重新实现排序来做你真正想要的事情。虽然我认为这种可能性是存在的,但我还没有在实践中看到过(我甚至不记得看到过一次我几乎决定这样做是正确的)。

vuv7lop3

vuv7lop32#

正如其他人所指出的,您应该考虑对People和Ages进行分组。
如果你不能/不想这样做,你可以为它们创建一个“索引”,并对该索引进行排序。例如:

// Warning: Not tested
struct CompareAge : std::binary_function<size_t, size_t, bool>
{
    CompareAge(const std::vector<unsigned int>& Ages)
    : m_Ages(Ages)
    {}

    bool operator()(size_t Lhs, size_t Rhs)const
    {
        return m_Ages[Lhs] < m_Ages[Rhs];
    }

    const std::vector<unsigned int>& m_Ages;
};

std::vector<std::string> people = ...;
std::vector<unsigned int> ages = ...;

// Initialize a vector of indices
assert(people.size() == ages.size());
std::vector<size_t> pos(people.size());
for (size_t i = 0; i != pos.size(); ++i){
    pos[i] = i;
}

// Sort the indices
std::sort(pos.begin(), pos.end(), CompareAge(ages));

现在,第n个人的名字是people[pos[n]],年龄是ages[pos[n]]

lndjwyie

lndjwyie3#

一般来说,你不会把你想保存在不同容器中的数据放在一起。为Person创建一个struct/class并重载operator<

struct Person
{
    std::string name;
    int age;
}

bool operator< (const Person& a, const Person& b);

或者这是一个可以扔掉的东西:

typedef std::pair<int, std::string> Person;
std::vector<Person> persons;
std::sort(persons.begin(), persons.end());

std::pair已经实现了比较运算符。

hfsqlsce

hfsqlsce4#

将它们保存在两个单独的数据结构中是没有意义的:如果重新排序People,就不再有到Ages合理Map。

template<class A, class B, class CA = std::less<A>, class CB = std::less<B> >
struct lessByPairSecond
    : std::binary_function<std::pair<A, B>, std::pair<A, B>, bool>
{
    bool operator()(const std::pair<A, B> &left, const std::pair<A, B> &right) {
        if (CB()(left.second, right.second)) return true;
        if (CB()(right.second, left.second)) return false;
        return CA()(left.first, right.first);
    }
};

std::vector<std::pair<std::string, int> > peopleAndAges;
peopleAndAges.push_back(std::pair<std::string, int>("Anne", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Bob", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Charlie", 23));
peopleAndAges.push_back(std::pair<std::string, int>("Douglas", 23));
std::sort(peopleAndAges.begin(), peopleAndAges.end(),
        lessByPairSecond<std::string, int>());
qojgxg4l

qojgxg4l5#

我建议将这两个列表合并为一个结构列表。这样你就可以像dirkgently说的那样简单地定义operator <

wfveoks0

wfveoks06#

“杰瑞·科芬”的回答非常明确和正确。
A只是有一个相关的问题,可能会给予一个很好的讨论的主题...:)
我不得不< T >根据向量的排序(假设sequence)重新排序矩阵对象(假设TMatrix)的列...TMatrix < T >类不提供对其行的引用访问(因此我不能创建一个结构来重新排序...),但方便地提供了一个方法TMatrix< T >::swap(row 1,row 2)...
这就是代码:

TMatrix<double> matrix;
vector<double> sequence;
// 
// 1st step: gets indexes of the matrix rows changes in order to sort by time
//
// note: sorter vector will have 'sorted vector elements' on 'first' and 
// 'original indexes of vector elements' on 'second'...
//
const int n = int(sequence.size());
std::vector<std::pair<T, int>> sorter(n);
for(int i = 0; i < n; i++) {
    std::pair<T, int> ae;
    ae.first = sequence[i]; 
    ae.second = i;              
    sorter[i] = ae;
}           
std::sort(sorter.begin(), sorter.end());

//
// 2nd step: swap matrix rows based on sorter information
//
for(int i = 0; i < n; i++) {
    // updates the the time vector
    sequence[i] = sorter[i].first;
    // check if the any row should swap
    const int pivot = sorter[i].second;
    if (i != pivot) {
        //
        // store the required swaps on stack
        //
        stack<std::pair<int, int>> swaps;
        int source = pivot;
        int destination = i;
        while(destination != pivot) {
            // store required swaps until final destination 
            // is equals to first source (pivot)
            std::pair<int, int> ae;
            ae.first = source;
            ae.second = destination;
            swaps.push(ae);
            // retrieves the next requiret swap
            source = destination;
            for(int j = 0; j < n; j++) {
                if (sorter[j].second == source) 
                    destination = j;
                    break;
                }
            }
        }                   
        //
        // final step: execute required swaps
        //
        while(!swaps.empty()) {
            // pop the swap entry from the stack
            std::pair<int, int> swap = swaps.top();
            destination = swap.second;                      
            swaps.pop();
            // swap matrix coluns
            matrix.swap(swap.first, destination);
            // updates the sorter
            sorter[destination].second = destination;
        }
        // updates sorter on pivot
        sorter[pivot].second = pivot;
    }
}

我相信这仍然是O(n log n)因为每一行不到位将交换一次。
玩得开心!:)

相关问题