सी ++ एसटीएल: लापता आधार स्तरीय इटरेटर और reverse_iterator

Question

मेरे वर्तमान सी ++ में के लिए की वजह से कोड की नकल - परियोजना मैं एक एसटीएल नक्शा जो वस्तुओं पर पूर्णांक कुंजी के नक्शे की है। एक एल्गोरिदम प्रविष्टियों का एक सेट देता है। दिए गए डेटा एल्गोरिथ्म के इनपुट पर निर्भर करता है और इसलिए भविष्यवाणी नहीं की जा सकती है:

class MyClass 
    { 
    //... 
    }; 

    int myAlgorithm(vector<int>::iterator inputIt) 
    { 
    // return a key for myMap which is calculated by the current value of inputData 
    } 

    int main(int argc, char *argv[]) 
    { 
    vector<int> inputData; 
    map<int, MyClass> myMap; 
    //<fill map with some data> 
    //<fill inputData> 

    vector<MyClass> result; 

    for (vector<int>::iterator it = inputData.begin(); it != inputData.end(); it++) 
    { 
     int myMapKey = myAlgorithm(*it); 
     // count() > 0 means "check whether element exists. Performance can be improved by replacing 
     // the operator[] and count() calls by map::find(). However, I want to simplify things 
     // in this example. 
     if (myMap.count(myMapKey) > 0) 
     { 
      // in some cases there is no entry in myMap 
      result.push_back(myMap[myMapKey]); 
     } 
    } 
    } 

उदाहरण में उल्लेख किया है मुझे लगता है के साथ map::count() और operator[] -calls बदल सकते हैं। STL-reference कहता है कि नक्शा :: ढूंढें() की जटिलता आकार में लॉगरिदमिक है (O(log n))।

मुझे पता चला कि ज्यादातर मामलों में myMap में प्रविष्टियों परिणाम में दो सिलसिलेवार प्रविष्टियों के लिए बहुत करीब हैं। इसलिए मैं निष्कर्ष है कि मैं अपना प्रदर्शन सुधार होगा अगर मैं map.find (प्रतिस्थापित) के लिए आया था iterators द्वारा कॉल:

 map<int, MyClass>::iterator myMapIt = myMap.begin(); 
    for (vector<int>::iterator it = inputData.begin(); it != inputData.end(); it++) 
    { 
     int myMapKey = myAlgorithm(*it); 
     // just increment iterator 
     while (myMapKey != myMapIt->first) 
     { 
      myMapIt++; 
      // we didn't find anything for the current input data 
      if (myMapIt == myMap::end() || myMapIt->first > myMapKey) 
      { 
       break; 
      } 
     } 

     // I know that I'm checking this twice, but that's not the point of my 
     // question ;) 
     if (myMapIt == myMap::end() || myMapIt->first > myMapKey) 
     { 
      // probably it would be better to move the iterator back to the position 
      // where we started searching, to improve performance for the next entry 
      myMapIt = myMap.begin(); 
     } 
     else 
     { 
      result.push_back(myMapIt.second); 
     } 
    } 

इस अवधारणा काम करता है लेकिन मैं एक बड़ी समस्या है: inputData के आधार पर, मैं करने के लिए है आगे या पीछे खोजें। इस बात पर विचार करें कि मैं कोड को main() के अंदर कई बार कॉल करता हूं और इनपुट कॉल इन कॉल के लिए बदलता है। को बढ़ा या while -loop अंदर इटरेटर घटती है कि क्या जाँच करने के बजाय, मैं तय कर सकता है कि for -loop प्रवेश करने से पहले।

मैंने सोचा था कि मैं सिर्फ map<>::reverse_iterator करने के लिए map<>::iterator स्विचिंग और rbegin()/rend() बजाय begin()/end() उपयोग करने के साथ ठीक हूँ। लेकिन तब मुझे एहसास हुआ कि reverse_iterator और iterator कोई आम आधार वर्ग है:

 map<int, MyClass>::base_iterator myIt; 
    if (/* ... */) 
    { 
     myMapIt = myMap::begin(); 
     myMapEndIt = myMap::end(); 
    } 
    else 
    { 
     myMapIt = myMap::rbegin(); 
     myMapEndIt = myMap::rend(); 
    } 
    /* for (...) ... */ 

कि बहुत अच्छा होगा, लेकिन कोई base_iterator है।

मैं इस समस्या के लिए एक सरल समाधान का पता: मैं बस दोनों ही मामलों के लिए पूरी for -loop को कॉपी करें और समायोजित करने की आवश्यकता:

 if (/* ... */) 
    { 
     /* for(...) which uses normal iterator in the while-loop */ 
    } 
    else 
    { 
     /* for(...) which uses reverse iterator in the while-loop */ 
    } 

बहुत बुरा ... क्या आप एक बेहतर समाधान पता है?

Answer 1

एक आम आधार प्रकार अनावश्यक है।

आपको केवल यह समझने की आवश्यकता है कि रास्ते में कई विकल्पों के साथ लंबे समय तक चलने वाले रैखिक कार्यों के बजाय, आपके पास कई नेस्टेड फ़ंक्शन हो सकते हैं जिसमें प्रत्येक विकल्प एक अलग कॉल का कारण बनता है।

अपने उदाहरण ले रहा है:

boost::any_iterator start, end; 
if (/* ... */) { 
    start = map.begin(), end = map.end(); 
} else { 
    start = map.rbegin(), end = map.rend(); 
} 

// do something with start and end 

आप में कोड बदल सकता है निम्नलिखित:

if (/* ... */) { 
    dosomething(map.begin(), map.end()); 
} else { 
    dosomething(map.rbegin(), map.rend()); 
} 

:

// Define a free-function in the .cpp to help factor common stuff 
template <typename FwdIt> 
static void dosomething(FwdIt start, FwdIt end) { 
    // do something with start and end 
} 

और फिर सीधे if/else शरीर में कॉल इंजेक्षन

और एक अच्छी बात यह है कि आप अपने कार्यों के भीतर राज्यों के परिवर्तनों की संख्या को कम करते हैं और इस प्रकार उनकी जटिलता को कम करते हैं।

Answer 2

आप इस्तेमाल कर सकते हैं टेम्पलेट्स:

template <typename T> 
void myFunction(T start, T end) 
{ 
    /* for (...) ... */ 
} 

map<int, MyClass>::base_iterator myIt; 
if (/* ... */) 
{ 
    myFunction(myMap.begin(), myMap.end()); 
} 
else 
{ 
    myFunction(myMap.rbegin(), myMap.rend()); 
} 

Answer 3

एक टेम्प्लेटेड समारोह का उपयोग करें। मानक लाइब्रेरी में एकमात्र जगह जहां टेम्पलेट्स पर विरासत का उपयोग किया जाता है IOstreams है, जहां तक ​​मुझे पता है (और यह एक गलती थी)।

template<typename Iterator> ... stuff(Iterator begin, Iterator end) { 
    // implement loop here 
} 
if (/*...*/) { 
    stuff(map.rbegin(), map.rend()); 
} else { 
    stuff(map.begin(), map.end()); 
} 

हालांकि, मैं सवाल करता है, तो आप बस एक हमेशा हे (1) कंटेनर के लिए बदल रहा है, एक unordered_map की तरह से बेहतर होगा। जब भाषा जेनेरिक प्रोग्रामिंग की अनुमति देता है