एक std :: multimap में अद्वितीय कुंजी भर में एक पुनरावर्तक है?

Question

क्या मल्टीमैप इटरेटर के लिए एक सरल या मानक तरीका है जो मल्टीमैप में अनन्य कुंजियों में फिर से चलाता है? {1, "a"}, {1, "lemon"}, {2, "peacock"}, {3, "angel"} पुनरावर्तक जो {1, "a"} पर शुरू तो {2, "peacock"} को इंगित होता incrementing हैं और उसके बाद फिर बढ़ाने {3, "angel"} को इंगित होगा:

एक सेट है कि तरह लग रहा है के लिए

अर्थात?

Answer 1

आप upper_bound उपयोग कर सकते हैं ++ के बजाय इटरेटर स्थिति को बढ़ाने के लिए:

#include <map> 
#include <string> 
#include <iostream> 

using namespace std; 

int main() 
{ 
    multimap<int,string> mm; 
    mm.insert(make_pair(1, "a")); 
    mm.insert(make_pair(1, "lemon")); 
    mm.insert(make_pair(2, "peacock")); 
    mm.insert(make_pair(3, "angel")); 

    for(auto it = mm.begin(), end = mm.end(); 
     it != end; 
     it = mm.upper_bound(it->first) 
) 
    cout << it->first << ' ' << it->second << endl; 
    return 0; 
} 

Answer 2

upper_bound का उपयोग पढ़ने में आसान करने के लिए लूप में परिणाम होगा लेकिन प्रत्येक कॉल एक द्विआधारी पेड़ खोज प्रदर्शन करेंगे, एक में जिसके परिणामस्वरूप ओ (एन लॉग एन)ओ (एन) ट्रैवर्सल के बजाय। यदि आप तो आप के बजाय std :: मानचित्र का उपयोग कर सकते जल्दी से सभी अद्वितीय चाबियाँ पर पारित करने के लिए है

typedef std::multimap<std::string, int> MapType; 
MapType container; 
for (MapType::iterator it = container.begin(); it != container.end();) { 
    std::string key = it->first; 

    doSomething(key); 

    // Advance to next non-duplicate entry. 
    do { 
    ++it; 
    } while (it != container.end() && key == it->first); 
} 

Answer 3

;: दक्षता मामलों में अंतर, तो आप इस तरह अपने ट्रेवर्सल संरचना कर सकते हैं

typedef std::map< KeyType, std::list<ValueType> > MapKeyToMultiValue; 

निवेशन, और अधिक मुश्किल होगा लेकिन अगर आप डुप्लिकेट प्रविष्टियों के साथ परेशान करने के लिए बिना सभी चाबियाँ पर पुनरावृति कर सकते हैं। प्रविष्टि के रूप में विचार करेंगे इस प्रकार है:

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value) 
{ 
    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< MapKeyToMultiValue::iterator, bool > ret = 
     map.insert(MapKeyToMultiValue::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 

या आपको लगता है कि बहुत टेम्प्लेटेड बना सकते हैं:

#include <map> 
#include <list> 
#include <string> 
#include <stdio.h> 

typedef std::string KeyType; 
typedef int ValueType; 

typedef std::map< KeyType, std::list<ValueType> > MapKeyToMultiValue; 

void insert_m(MapKeyToMultiValue &map, const KeyType key, const ValueType value) 
{ 
    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< MapKeyToMultiValue::iterator, bool > ret = 
     map.insert(MapKeyToMultiValue::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 


template<typename KeyType, typename ValueType, 
    typename MapType = std::map< KeyType, std::list<ValueType> > > 
void insert_multi(MapType &map, const KeyType key, const ValueType value) 
{ 

    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< typename MapType::iterator, bool > ret = 
     map.insert(typename MapType::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 


int main() 
{ 
    MapKeyToMultiValue map; 


    insert_m(map, std::string("aaa"), 1); 
    insert_m(map, std::string("aaa"), 2); 
    insert_m(map, std::string("bb"), 3); 
    insert_m(map, std::string("cc"), 4); 


    insert_multi(map, std::string("ddd"), 1); 
    insert_multi(map, std::string("ddd"), 2); 
    insert_multi(map, std::string("ee"), 3); 
    insert_multi(map, std::string("ff"), 4); 


    for(auto i = map.begin(); i != map.end(); ++i) 
    { 
     printf("%s\n", i->first.c_str()); 
    } 


    return 0; 
} 

Answer 4

यह https://stackoverflow.com/a/24212648/895245 पर एक मामूली सुधार है:

template<typename KeyType, typename ValueType, 
    typename MapType = std::map< KeyType, std::list<ValueType> > > 
void insert_multi(MapType &map, const KeyType key, const ValueType value) 
{ 

    auto it = map.find(key); 
    if (it == map.end()) 
    { 
    std::list<ValueType> empty; 
    std::pair< typename MapType::iterator, bool > ret = 
     map.insert(typename MapType::value_type(key, empty)); 
    it = ret.first; 
    } 

    it->second.push_back(value); 
} 

पूर्ण परीक्षण कार्यक्रम इस प्रकार है लग रहा है के साथ:

• एक "इकाई परीक्षण"

#include <cassert> 
#include <map> 
#include <vector> 

int main() { 

    // For testing. 
    auto m = std::multimap<int, int>{ 
     {1, 2}, 
     {1, 3}, 
     {2, 4} 
    }; 
    std::vector<int> out; 

    // The algorithm. 
    auto it = m.begin(); 
    auto end = m.end(); 
    while (it != end) { 
     auto key = it->first; 

     // Do what you want to do with the keys. 
     out.push_back(key); 

     do { 
      if (++it == end) 
       break; 
     } while (it->first == key); 
    } 

    // Assert it worked. 
    assert(out == std::vector<int>({1, 2})); 
} 

Answer 5

चयनित जवाब में बताया गया है, multimap::upper_bound का बार-बार इस्तेमाल एक हे की ओर जाता है (एन लॉग इन करें n) नक्शे के ट्रेवर्सल। बाहरी upper_bound फ़ंक्शन का उपयोग करके आप ओ (एन) देते हैं। हालांकि, अगर आप आप केवल मानचित्र के प्रमुख की तुलना सुनिश्चित करने की आवश्यकता: - यानी रैखिक खोज -

std::multimap<int, std::string> myMap = ... ; 
const auto compareFirst = [](const std::pair<const int, std::string>& lhs, const std::pair<const int, std::string>& rhs) { 
    return lhs.first < rhs.first; 
}; 

for(auto it = myMap.begin(); it != myMap.end(); it = std::upper_bound(it, myMap.end(), *it, compareFirst)) { 
    // Do stuff... 

} 

अंतर्निहित दृष्टिकोण अनिवार्य रूप से user3701170 के समाधान के रूप में ही है, लेकिन हम for बयान में वेतन वृद्धि कदम रखा उचित, नहीं लूप का शरीर उछाल डालने के अलावा जहां यह "आमतौर पर" रहता है, इसका मतलब यह भी है कि लूप में continue स्टेटमेंट अपेक्षित व्यवहार करेंगे।