एसडीडी लाइब्रेरी में कौन सा फ़ंक्शन बाइनरी खोजना है और एक तत्व ढूंढना है?

Question

मैं एक नोड struct

struct Node{CString text, int id;}; 

एक क्रमबद्ध वेक्टर में मिल गया है।

मुझे आश्चर्य है कि क्या एल्गोरिदम में कोई फ़ंक्शन है जो वेक्टर की बाइनरी खोज करेगा और एक तत्व ढूंढ पाएगा।

Answer 1

std::binary_search() आपको पता चलेगा कि एक मूल्य के कंटेनर में मौजूद है लिख सकते हैं।

std::lower_bound()/std::upper_bound() एक मूल्य के प्रथम/अंतिम घटना के लिए एक इटरेटर वापस आ जाएगी।

आपका वस्तुओं 01 लागू करने की आवश्यकता काम करने के लिए इन एल्गोरिदम के लिए।

Answer 2

हाँ, वहाँ एक समारोह "binary_search" std :: binary_search

आप इसे पहले देना कहा जाता है, पिछले और एक मूल्य या एक विधेय है।

एक नमूने के लिए here देखें

कम्बाइन कि Martin York's ऑपरेटर के साथ == और आप ठीक होना चाहिए (वैकल्पिक रूप से आप एक विधेय functor

Answer 3

सॉर्ट किए गए वेक्टर < नोड >
मानचित्र का उपयोग क्यों न करें। यह एक क्रमबद्ध कंटेनर है। तो std :: find() के माध्यम से इस पर किए गए किसी भी खोज में स्वचालित रूप से बाइनरी खोज के समान गुण होते हैं।

Answer 4

सॉर्ट किए गए वेक्टर में तत्वों की एक श्रृंखला खोजने के लिए std::equal_range का उपयोग करें। std::equal_range इटरेटर के std::pair लौटाता है, जो आपको प्रदान किए गए तर्क के बराबर तत्वों के वेक्टर में एक रेंज देता है। यदि सीमा खाली है, तो आपका आइटम वेक्टर में नहीं है, और सीमा की लंबाई आपको बताती है कि वेक्टर में आपका आइटम कितनी बार दिखाई देता है।

यहाँ struct Node के बजाय ints का उपयोग कर एक उदाहरण है:

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

int main(int argc, const char * argv[]) 
{ 
    std::vector<int> sorted = { 1, 2, 2, 5, 10 }; 

    auto range = std::equal_range(sorted.begin(), sorted.end(), 20); 
    // Outputs "5 5" 
    std::cout << std::distance(sorted.begin(), range.first) << ' ' 
       << std::distance(sorted.begin(), range.second) << '\n'; 

    range = std::equal_range(sorted.begin(), sorted.end(), 5); 
    // Outputs "3 4" 
    std::cout << std::distance(sorted.begin(), range.first) << ' ' 
       << std::distance(sorted.begin(), range.second) << '\n'; 

    range = std::equal_range(sorted.begin(), sorted.end(), -1); 
    // Outputs "0 0" 
    std::cout << std::distance(sorted.begin(), range.first) << ' ' 
       << std::distance(sorted.begin(), range.second) << '\n'; 

    return 0; 
} 

struct Node के साथ इस काम करने के लिए आप या तो struct Node के लिए एक operator < प्रदान करने या std::equal_range करने के लिए एक तुलनित्र में पारित करने के लिए होगा। आप अपने structs की तुलना करने के लिए std::equal_range पर एक लैम्बडा प्रदान करके ऐसा कर सकते हैं।

std::vector<Node> nodes = { Node{"hello", 5}, Node{"goodbye", 6} }; 
Node searchForMe { "goodbye", 6 }; 
auto range = std::equal_range(nodes.begin(), nodes.end(), searchForMe, 
           [](Node lhs, Node rhs) { return lhs.id < rhs.id; });