有效地对定义顺序的向量的子集进行排序

Question

我有定义项目顺序的向量(0..N-1),例如 {5, 0, 4, 3, 2, 1, 7, 6}.

我必须对该向量的子集进行排序.所以,因为{0, 1, 2, 5}我应该得到{5, 0, 2, 1}.

我测试了以下解决方案:

1. 在子集中创建一组项目,然后清除子集,浏览排序向量,仅添加集合中的项目.
2. 通过遍历排序向量创建新的排序向量,仅添加子集中找到的项目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;
    }

代码是从这里复制的