C++ STL : iterator와 reverse_iterator에 기본 클래스가 누락되어 중복 코드가 발생했습니다.

Question

현재 C++ 프로젝트에는 정수 키를 객체에 매핑하는 STL 맵이 있습니다. 알고리즘은 일련의 항목을 반환합니다. 반환 된 데이터는 알고리즘의 입력에 따라 달라집니다 때문에 예측할 수 없습니다 :

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은 map :: find()의 복잡성이 로그의 크기가 (O(log n))라고 말합니다.

대부분의 경우 myMap의 항목이 결과에서 두 개의 연속 항목에 매우 가깝다는 것을 발견했습니다. 그러므로 나는 내가 map.find을 (교체하면 더 나은 성능을 달성 할 결론)에 와서는 반복자에 의해 호출

 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() 안에 코드를 여러 번 호출하고 이러한 호출에 대해 inputData가 변경되었다고 간주하십시오. 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

는 템플릿 기능을 사용합니다. 표준 라이브러리에서 템플릿 상속이 사용되는 유일한 곳은 내가 알고있는 한 IOstream입니다 (실수였습니다). 당신은 단순히 unordered_map처럼 상시 O (1) 컨테이너로 변경 나을 것인지

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

그러나, 나는 질문.