सी ++ बिडरेक्शनल यादृच्छिक अभिगम के लिए कुशल डेटा संरचना

Question

मेरे पास दो सेट ए और बी के तत्व ए और बी हैं। अब ये एक दूसरे से संबंधित हैं (0..1: एन कार्डिनालिटी) ताकि प्रत्येक में बी में सबसे अधिक भागीदार हो। और प्रत्येक ख ए में कई (कम से कम एक) आइटम के लिए संघों हो सकता है एक पूर्णांक जोड़े और बी का एक सेट कर रहे हैं पूर्णांक है।

वहाँ इस तरह के एक "द्वि-दिशात्मक" नक्शा स्टोर करने के लिए कारगर तरीका है?

map<pair<unsigned int, unsigned int>, unsigned int> AtoB 
map<unsigned int, vector<pair<unsigned int, unsigned int> > > BtoA 

लेकिन शायद के साथ इस और अधिक कुशलता से निपटने के लिए अच्छा तरीका है: एक साधारण दृष्टिकोण दो नक्शे का उपयोग करने के लिए होगा।

आपकी मदद

Answer 1

बूस्ट में दो पुस्तकालय शामिल हैं: Boost.Bimap और Boost.MultiIndex। जबकि दूसरे अधिक सामान्य है और कुछ मनमाने ढंग से अनुक्रमित के साथ एक में स्मृति डेटाबेस के लिए समान लागू करता है पूर्व, द्विभाजित ("द्विदिश") नक्शे की समस्या के लिए विशिष्ट है।

यह देखते हुए कि आपकी unsigned int कुंजी आपके जोड़े को विशिष्ट रूप से मानचित्र नहीं बनाती हैं, मुझे लगता है कि मल्टीइंडेक्स अधिक क्रम में है। यह एक लंबे समय के बाद से मैं पिछले इस पुस्तकालय का उपयोग किया है, लेकिन ट्यूटोरियल को देखते हुए, आप तो आप कम से कम अपने मौजूदा सेटअप सरल बना सकते हैं की तरह

struct YourData { 
    unsigned key; 
    std::pair<unsigned, unsigned> value; 
}; 

typedef multi_index_container< 
    YourData, 
    indexed_by< 
     ordered_non_unique<member<YourData, unsigned, &YourData::key> >, 
     ordered_unique<member<YourData, std::pair<unsigned, unsigned>, 
           &YourData::value> > 
    > 
> YourContainer; 

कुछ चाहिए आप बूस्ट का उपयोग नहीं करना चाहते हैं जाएगा,

map<unsigned int, vector<pair<unsigned int, unsigned int> > > 

std::multimap<unsigned, std::pair<unsigned, unsigned>> द्वारा प्रतिस्थापित करके।

Answer 2

के बारे में कैसे boost::bimap के लिए धन्यवाद? http://www.boost.org/doc/libs/1_47_0/libs/bimap/doc/html/index.html मुझे लगता है कि यह आप के लिए है।

Answer 3

मानचित्र और मल्टीमैप हे (लॉग एन) के एक दक्षता अमीर है, तो, मुझे लगता है कि सबसे अच्छा तरीका है अपने डेटा स्टोर करने के लिए है। मैं

map<pair<unsigned int, unsigned int>, unsigned int> AtoB 
multimap<pair<unsigned int, unsigned int>, unsigned int> BtoA 

उपयोग करने के लिए सुझाव है