C++ std::map 的 Key Iterator

情境

我的 map
std::map<std::string, int> animals;
animals["cat"] = 3;
animals["cow"] = 10;
animals["dog"] = 20;
animals["lion"] = 100;

若我只想要印出 Key 值

預期 Output
cat
cow
dog
lion

問題

標準作法只能取 map 的 pair,還要轉 first,比較難讀。

for(const auto& item: animals)
{
    std::cout << item.first << std::endl;
}

目標

預期的簡單用法

for(const auto& key: map_key_adaptor(animals))
{
    std::cout << key << std::endl;
}

解法

三個步驟

  1. 做出只取 mapkey 的 Iterator Class
  2. 做出支援 begin()/end() 的 Adaptor Class
  3. 做出入口 function map_key_adaptor,可以由傳入的 map 參數,來推斷 map 中的 KeyT 參數,免去手打的麻煩。

Iterator Class

Iterator 中不要存放 map 本身, pointer, 或是 reference,存放輕量的 iterator 即可。

  • m_map_cur 代表目前的 map iterator
  • m_map_end 用來判斷是否已走到 map 底部
  • m_end
    • 如果 m_map_cur 走到 m_map_end 時,會被設為 true,表示此 iterator 已終結。
    • 算是一種為了無參數代表 end iterator 的表示法,與判斷 end 的快取。

這裡參考 iostream_iterator 的做法,把沒有參數的 iterator 當做是 end 旗標。
此時 end iterator 的 m_map_curm_map_end, 將沒有意義。

data member 與建構子
template<typename KeyT, typename ValueT>
class map_key_iterator
{
    typename std::map<KeyT, ValueT>::const_iterator m_map_cur;
    typename std::map<KeyT, ValueT>::const_iterator m_map_end;
    bool m_end;
public:
    map_key_iterator(const std::map<KeyT, ValueT>& map)
        : m_map_cur(map.begin())
        , m_map_end(map.end())
        , m_end(map.begin() == map.end()) 
    {}    
        
    map_key_iterator()
        :m_end(true) 
    {}
取值運算子,直接 return map 的 key 值 (iterator 的 first)
    KeyT operator*() const
    {
        return m_map_cur->first;
    }
前進 m_map_cur 的同時,也更新 m_end
    map_key_iterator& operator++()
    {
        m_end = (++m_map_cur == m_map_end);
        return *this;
    }
    
    map_key_iterator operator++(int)
    {
        map_key_iterator origin(*this);
        ++(*this);
        return origin;
    }
  • 雙方都為 end iterator 時,當然相等,都代表已結束
  • 只有其中一方為 end iterator,代表一定不相等
  • 當雙方都不是 end iterator,代表雙方的 m_map_cur 都有效,再進行 cur 的比較。
== 與 != 最常用在判斷是否已達 end iterator
    friend bool operator ==(const map_key_iterator& lhs, const map_key_iterator& rhs)
    {
        if(lhs.m_end && rhs.m_end) return true;
        if(lhs.m_end || rhs.m_end) return false;
        return lhs.m_map_cur == rhs.m_map_cur;
    }

    friend bool operator !=(const map_key_iterator& lhs, const map_key_iterator& rhs)
    {
        return !(lhs == rhs);
    }
};

Adaptor Class

  • constructor 會製做好 map 的 begin iterator
  • begin() always 傳出 begin iterator 的複本。
  • end() 則是 傳出一份無參數的 Iterator 即可。
template<typename KeyT, typename ValueT>
class map_key
{
    IterT m_begin;
public:
    typedef map_key_iterator<KeyT, ValueT> IterT;
    
    map_key(const std::map<KeyT, ValueT>& m)
        :m_begin(IterT(m)) 
    {};

    IterT begin() const{ return m_begin;}
    IterT end() const{ return IterT();}
};

map_key_adaptor 入口 function

此 function 最大的用處就是可以省去手打 template parameter 的麻煩
map_key<std::string, int>(animals) 變成 map_key_adaptor(animals)
Compiler 可以幫你去從參數的 map 抓取 KeyTValueT

template<typename KeyT, typename ValueT>
map_key<KeyT, ValueT> map_key_adaptor(const std::map<KeyT, ValueT>& m)
{
    return map_key<KeyT, ValueT>(m);
}

結果

map key adaptor,使用上相當清楚與簡單。

std::map<std::string, int> animals;

animals["cat"] = 3;
animals["cow"] = 10;
animals["dog"] = 20;
animals["lion"] = 100;

for(const auto& key: map_key_adaptor(animals))
{
    std::cout << key << std::endl;
}
comments powered by Disqus