किसी अन्य वेक्टर

Question

के आधार पर बिंदुओं का एक वेक्टर ऑर्डर करें, मैं एक सी ++ एप्लिकेशन पर काम कर रहा हूं।

मैं

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

Point2f परिभाषित किया गया है typedef Point_<float> Point2f;

vectorAll 1000 बिंदु है, जबकि vectorSpecial 10 अंक है अंकों की 2 वैक्टर की है।

पहला चरण:

मैं 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 

मैं एक डबल पाश करना और अनुक्रमित बचा सकता है। और उसके बाद उनके सूचकांक के आधार पर अंक ऑर्डर करें। हालांकि इस विधि में बहुत अधिक समय लग रहा है (उदाहरण के लिए वेक्टरएल में 10000 अंक और वेक्टर विशेष में 1000 अंक) ताकि दस मिलियन पुनरावृत्ति हो)

ऐसा करने के बेहतर तरीके क्या हैं?

दूसरा कदम:

vectorSpecial में कुछ बिंदुओं vectorAll में उपलब्ध नहीं हो सकता है। मुझे उस बिंदु को लेने की ज़रूरत है जो इसके निकटतम है (सामान्य दूरी सूत्र sqrt((x1-x2)^2 + (y1-y2)^2))

यह लूपिंग के दौरान भी किया जा सकता है, लेकिन अगर किसी के पास बेहतर तरीके के लिए कोई सुझाव है, तो मैं इसकी सराहना करता हूं।

धन्यवाद किसी भी मदद के लिए एक बहुत

Answer 1

आप std::sortvectorAll पर Compare समारोह खाते में vectorSpecial की सामग्री को लेने के लिए तैयार किया गया है के साथ उपयोग कर सकते हैं:

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

अपने प्रथम चरण, आप कर सकते हैं के लिए सी ++ 11 लैम्ब्डा का शानदार प्रभाव (विशेष.size() = के, और all.size() = एन)

#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 वेक्टर में परिणाम के बीच की दूरी की गणना। दूसरा, वेक्टर में संबंधित तत्वों के तत्वों की प्रत्येक जोड़ी की तुलना करके 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 में तत्व जो निकटतम है, जो आप अपने प्रश्न में सुझाए गए न्यूनतम यूक्लिडियन दूरी की गणना करके करते हैं।

अद्यतन: आप पहले एक std::unordered_map हैश तालिका में all के प्रत्येक तत्व के सूचकांक भंडारण, और फिर special के तत्वों कि हैश तालिका में देखने के आधार पर के बीच तुलना करने से एक अंतरिक्ष/समय तालमेल बना सकता है। यह ओ (एन) के पहले चरण की समय जटिलता को कम करता है (के < एन मानते हैं), लेकिन हैश तालिका के लिए भंडारण के ओ (एन) जोड़ता है।