C++ STL: Mã trùng lặp do thiếu lớp cơ sở cho trình lặp và reverse_iterator

Question

Trong dự án C++ hiện tại của tôi, tôi có một bản đồ STL ánh xạ các phím số nguyên lên các đối tượng. Một thuật toán trả về một tập các mục. Các dữ liệu trả về phụ thuộc vào đầu vào của thuật toán và do đó không thể được dự đoán:

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

Như đã đề cập trong ví dụ tôi có thể thay thế map::count() và operator[] -calls với find. Các STL-reference nói rằng bản đồ :: tìm() 's phức tạp là logarithmic trong kích thước (O(log n)).

Tôi phát hiện ra rằng trong hầu hết các trường hợp, các mục trong myMap rất gần với hai mục nhập liên tiếp trong kết quả. Vì vậy, tôi đi đến kết luận rằng tôi sẽ đạt được hiệu suất tốt hơn nếu tôi thay thế map.find() gọi bằng lặp:

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

khái niệm này hoạt động nhưng tôi có một vấn đề lớn: Tùy thuộc vào inputData, tôi phải tìm kiếm tiến hoặc lùi. Hãy xem xét rằng tôi gọi mã bên trong main() nhiều lần và các thay đổi inputData cho các cuộc gọi này. Thay vì kiểm tra xem có tăng hoặc giảm bộ lặp trong vòng while vòng lặp hay không, tôi có thể quyết định rằng trước khi bước vào vòng lặp for.

Tôi nghĩ rằng tôi là tốt với chỉ cần chuyển đổi các map<>::iterator-map<>::reverse_iterator và sử dụng rbegin()/rend() thay vì begin()/end(). Nhưng sau đó tôi nhận ra rằng reverse_iterator và iterator không có lớp cơ sở chung:

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

Đó sẽ là tuyệt vời, nhưng không có base_iterator.

Tôi biết một workaround đơn giản cho vấn đề này: Tôi chỉ cần sao chép toàn bộ for -loop và điều chỉnh nó cho cả hai trường hợp:

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

Rất xấu ... Bạn có biết một giải pháp tốt hơn?

Answer 1

Loại cơ sở chung là không cần thiết khi ngôn ngữ cho phép Lập trình chung.

Điều bạn chỉ cần nhận ra là thay vì có một hàm tuyến tính dài có nhiều lựa chọn trên đường đi, bạn có thể có một số chức năng lồng nhau trong đó mỗi lựa chọn dẫn đến một cuộc gọi khác.

Lấy ví dụ của bạn:

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 

Bạn có thể chuyển đổi mã vào như sau:

// 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 
} 

Và sau đó tiêm cuộc gọi thẳng vào if/else cơ thể:

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

Và một điều tốt là bạn giảm số lượng thay đổi của các trạng thái trong các hàm của bạn và do đó chúng phức tạp.

Answer 2

Bạn có thể sử dụng các mẫu:

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

Sử dụng chức năng templated. Nơi duy nhất trong thư viện chuẩn, nơi thừa kế được sử dụng trên mẫu là IOstreams, theo như tôi biết (và đó là một sai lầm).

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

Tuy nhiên, tôi đặt câu hỏi nếu bạn chỉ đơn giản là thay đổi tốt hơn sang một thùng chứa O (1) như unordered_map.