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

Question

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

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

我测试了以下解决方案：

在子集中创建一组项，然后清除子集，遍历排序向量，只添加集合中的项。
通过排序向量创建新的排序向量，仅添加在 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

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

Efficiently sort subset of the vector that defines the order

c++

sorting

algorithm

vector