c++ - 有效地对定义顺序的 vector 子集进行排序

Question

我有定义项目顺序 (0..N-1) 的 vector ，例如{5、0、4、3、2、1、7、6}。

我必须对该 vector 的子集进行排序。因此，对于 {0, 1, 2, 5}，我应该得到 {5, 0, 2, 1}。

我测试了以下解决方案:

1. 在子集中创建一组项目，然后清除子集，遍历排序 vector ，仅添加该集中的项目。
2. 通过遍历排序 vector 创建新的排序 vector ，只添加在 std::lower_bound 的子集中找到的项。

第二个解决方案似乎更快，尽管它需要对子集进行排序。有没有更好的解决方案？我正在使用 C++/STL/Qt，但问题可能与语言无关。

Answer 1

检查这段代码:-

#include <iostream>
#include <algorithm>
#include <vector>


    struct cmp_subset
    {
        std::vector<int> vorder;

        cmp_subset(const std::vector<int>& order)
        {
            vorder.resize(order.size());
            for (int i=0; i<order.size(); ++i)
                vorder.at(order[i]) = i;
        }

        bool operator()(int lhs, int rhs) const
        {
            return vorder[lhs] < vorder[rhs];
        }
    };

    int main()
    {
        std::vector<int> order = {5, 0, 4, 3, 2, 1, 7, 6};
        std::vector<int> subset = {0, 1, 2, 5};

        for (auto x : subset)
            std::cout << x << ' ';
        std::cout << '\n';

        std::sort(subset.begin(), subset.end(), cmp_subset(order));

        for (auto x : subset)
            std::cout << x << ' ';
        std::cout << '\n';

        return 0;
    }

代码复制自here