STL像迭代器在散列圖的集合

Question

我正在尋找一種方法來創建一個前向迭代器，它允許迭代散列圖的集合。

保存幾張地圖的示例類如下所示。 （我正在使用unordered_map和shared_ptr的提升，但C++ 11也會提供這些類）。 在我的特定應用程序中，我使用這個構造來表示稀疏的分層2D網格位置;即KeyT是一個2D位置，ValueT是一個整數計數器，不同的水平代表不同的網格分辨率。

template <typename KeyT, typename ValueT> 
class MapCollection 
{ 
public: 
    // type-definitions for the map and a shared pointer to the map 
    typedef boost::unordered_map<KeyT, ValueT> Map; 
    typedef boost::shared_ptr<Map> MapPtr; 

    // Constructor for class 
    MapCollection (int num_levels) 
    { 
    levels_.reserve (num_levels); 
    for (int i = 0; i < num_levels; ++i) 
     levels_.push_back (MapPtr (new Map())); 
    } 

    // adds a key-value pair to the map on the given level 
    void addValue (const KeyT &key, const ValueT &value) 
    { 
    int level = getLevelForKey (key); 
    (*levels_[level])[key] = value; 
    } 

    // TODO define const_iterator for this class 
    // TODO define member function begin(), returning levels_.front()->begin() 
    // TODO define member function end(), returning levels_.back()->end() 

private: 
    // return the hierarchy level for the given key 
    int getLevelForKey (const KeyT &key) { return /* ... */ }; 

    // collection of maps 
    std::vector<MapPtr> levels_; 
}; 

中的應用程序現在我希望能夠遍歷所有地圖的所有條目，同樣如果僅僅過了一個地圖迭代，什麼是可能的，即

int main (int argc, char *argv[]) 
{ 
    int num_levels = 5; 
    MapCollection maps (num_levels); 

    // fill maps 
    maps.addValue (/* ... */) 

    // iterator over all entries 
    MapCollection::const_iterator iter = maps.begin(); 
    for (; iter != maps.end(); ++iter) 
    { 
    std::cout << "Key: " << iter->first << " | Value: " << iter->second << std::endl; 
    } 

    return EXIT_SUCCESS; 
} 

顯然，將有可能遍歷不同的層次和每個層次上的地圖，但我想隱藏爲用戶創建不同的層次。

定義MapCollection類(const_)iterator的正確方法是什麼？

感謝您的幫助！

Answer 1

您可以使用boost迭代器外觀，這將幫助您執行自定義迭代器的任務。這個想法是：

1-維護對包含地圖的向量的引用（levels_）。
2-iterator指示自定義迭代器迭代（std::vector<MapPtr>::iterator或std::vector<MapPtr>::const_iterator類型）或具有相同信息的索引（檢索level_[index]的結尾）的前一個向量的元素。
3-a迭代器，帶有前一迭代器迭代的當前元素（迭代的實際元素）。

一些示例代碼：

#include <boost/iterator/iterator_facade.hpp> 

namespace impl 
{ 
    template <class Value> 
    class iterator 
     : public boost::iterator_facade< 
      config_iterator<Value> 
      , Value 
      , boost::forward_traversal_tag 
     > 
    { 
    public: 
     config_iterator() {...} 
     explicit config_iterator(parameters) { /*your specific contructor*/ } 

    private: 
     template <class OtherValue> 
     config_iterator(config_iterator<OtherValue> const& other); 

     friend class boost::iterator_core_access; 
     template <class> friend class config_iterator; 

     template <class OtherValue> 
     bool equal(config_iterator<OtherValue> const& other) const { } // Verify is two iterators are equals (used to verify if it == end) 

     void increment() {} // Logic for incrementing the iterator 
     Value& dereference() const {} // Returning the actual value 

     // members 
    }; 
} 

typedef impl::iterator<type> iterator; 

這是非常簡單的迭代器（向前）的模板文件，讀取Iterator Help更多的信息，同樣可以實現重載正確的運營商（++發佈預先增量，*， - >等），通過增加提供了一種方法來定義實現其餘部分所需的最小值。