C++ STL: Yineleyici kod, yineleyici ve reverse_iterator için eksik temel sınıf nedeniyle kopyalanıyor

Question

Geçerli C++ - projemde, tamsayı tuşlarını nesnelerin üzerine eşleyen bir STL haritasına sahibim. Bir algoritma bir dizi giriş döndürür. Dönen veri algoritmanın giriş bağlıdır ve dolayısıyla tahmin edilemez:

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]); 
     } 
    } 
    } 

Ben Bul ile map::count() ve operator[] -calls yerini alabilir örnekte belirtildiği gibi. STL-reference, map :: find() 'ın karmaşıklığının logaritmik boyutta olduğunu bildiriyor (O(log n)).

Çoğu durumda, myMap'teki girdilerin sonuçta iki sıralı girdi için çok yakın olduğunu keşfettim. Bu nedenle ben map.find (değiştirilir eğer iyi performans elde ederim sonuca) geldi yineleyiciler tarafından çağırır:

 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); 
     } 
    } 

Bu kavram eserlerini ama büyük bir sorun var: InputData bağlı olarak, bunu yapmak zorunda ileriye veya geriye doğru arama. Kodu main()'un içinde birçok kez aradığımı ve bu çağrılar için inputData'nın değiştiğini düşünün. while -loop içerisindeki yineleyicinin artırılıp artırılmayacağına karar vermek yerine, for -loop girmeden önce karar verebilirim.

Ben sadece map<>::reverse_iterator için map<>::iterator anahtarlama ve rbegin()/ rend() yerine begin()/ end() kullanmasının bir sakıncası yok düşündük. Ama sonra reverse_iterator ve iterator ortak temel sınıfa sahip olduğunu fark etti:

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

çok iyi olurdu, ancak hiçbir base_iterator yoktur.

bu sorun için basit bir çözüm biliyorum: Sadece iki durum için bütün for -loop kopyalayıp ayarlamak gerekir:

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

Çok kötü ... Eğer daha iyi bir çözüm biliyor musunuz?

Answer 1

Dil, Genel Programlamaya izin verdiğinde ortak bir taban türü gereksizdir.

Sadece farkında olmanız gereken şey, yol boyunca çeşitli seçeneklerle uzun sargılı doğrusal işlevler yerine, her seçimin farklı bir aramaya yol açtığı birkaç yuvalanmış işleve sahip olabilirsiniz.

senin örneğini alarak:

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 

Sen içine kodu dönüştürebilir aşağıdaki:

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 
} 

Sonra düz if/else vücuda çağrı enjekte

Ve iyi bir şey şu ki İşlevlerinizdeki durumların sayısını ve dolayısıyla karmaşıklıklarını azaltırsınız.

Answer 2

Şunları kullanabilirsiniz şablonlar:

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

templated işlevini kullanın. Kalıtımın şablonlar üzerinde kullanıldığı Standart kitaplıktaki tek yer, farkında olduğum sürece IOstreams'tır (ve bu bir hataydı). sadece bir unordered_map gibi bir zaman O (1) konteynıra değişen daha iyi olurdu eğer

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

Ancak, ben soru.