根据另一个向量对点向量进行排序

Question

我正在开发一个C++应用程序。

我有 2 个点向量

vector<Point2f> vectorAll;
vector<Point2f> vectorSpecial;  

Point2f 的定义typedef Point_<float> Point2f;

vectorAll 有 1000 点，而 vectorSpecial 有 10 点。

第一步：

我需要根据它们在vectorAll中的顺序对vectorSpecial中的点进行排序。所以像这样：

For each Point in vectorSpecial
    Get The Order Of that point in the vectorAll
    Insert it in the correct order in a new vector

我可以做一个双循环并保存索引。 然后根据点的索引对点进行排序。但是，当我们有很多点时，此方法花费的时间太长（例如vectorAll中有10000个点，vectorSpecial中有1000个点，所以这是一千万次迭代）

有什么更好的方法可以做到这一点？

第二步：

vectorSpecial 中的某些点在 vectorAll 中可能不可用。我需要取最接近它的点（通过使用通常的距离公式sqrt((x1-x2)^2 + (y1-y2)^2)）

这也可以在循环时完成，但如果有人对更好的方法有任何建议，我将不胜感激。

非常感谢任何帮助

Answer 1

您可以在vectorAll上使用std::sort，其中包含旨在考虑vectorSpecial内容的Compare函数：

struct myCompareStruct
{
    std::vector<Point2f> all;
    std::vector<Point2f> special;
    myCompareStruct(const std::vector<Point2f>& a, const std::vector<Point2f>& s)
        : all(a), special(s) 
    {
    }
    bool operator() (const Point2f& i, const Point2f& j) 
    { 
        //whatever the logic is
    }
};
std::vector<Point2f> all;
std::vector<Point2f> special;
//fill your vectors
myCompareStruct compareObject(all,special);
std::sort(special.begin(),special.end(),compareObject);

Answer 2

对于第一步，您可以使用 C++11 lambda 来达到很好的效果（special.size（） = K，all.size（） = N）

#include <algorithm>   // std::sort, std::transform, std::find, std::min_element
#include <iterator>    // std::distance
std::vector<int> indices;
indices.reserve(special.size());
// locate exact index in all for every element of special. Complexity = O(K * N)
std::transform(special.begin(), special.end(), indices.begin(), [&all](Point2f const& s){                   
     return std::distance(
         all.begin(), 
         std::find(all.begin(), all.end(), s)
     ); 
});
// sort special based on index comparison. Complexity = O(K * log(K))
std::sort(special.begin(), special.end(), [&indices](Point2f const& r, Point2f const& s){
     auto i = std::distance(special.begin(), r);
     auto j = std::distance(special.begin(), s);
     return indices[i] < indices[j];
});

解释：首先，对于special中的每个点，计算all的开始和特殊元素在all中的位置之间的距离，并将结果存储到indices向量中。其次，通过比较每对元素与indices向量中的相应元素，对special的所有元素进行排序。

对于第二步，您只需更改计算指数的方式

// locate closest element in all for every element of special. Complexity = O(K * N)
std::transform(special.begin(), special.end(), indices.begin(), [&all](Point2f const& s){                   
     return std::distance(
         all.begin(), 
         std::min_element(all.begin(), all.end(), [&s](Point2f const& a){
              return // Euclidean 2D-distance between a and s    
         });
     ); 
});

解释：与第一步相比，唯一的变化是，对于special中的每个元素，您都可以找到all中最接近它的元素，这是通过计算问题中建议的最小欧几里得距离来实现的。

UPDATE：您可以先将all的每个元素的索引存储到std::unordered_map哈希表中，然后根据对该哈希表的查找来比较special元素之间的比较，从而进行空间/时间权衡。这会将第一步的时间复杂度降低到 O（N）（假设 K