c++ - 使用 boost 迭代器针对映射的每个键在值容器的每个元素上实现迭代器

Question

如何使用 boost::iterator_adaptor 实现一个只包含 map/unordered_map 值的迭代器？我尝试了以下代码，但由于带有注释的行而无法正常工作。是否有避免该问题的解决方案？

这里的问题与 boost 代码中显示的 map_values 适配器示例略有不同，因为这里 map 中的值字段是另一个容器，如列表或 vector ，这里的要求是为每个键迭代这些列表的所有元素的 map 。迭代器的 deref 是那些列表/vector 的 value_type 类型。迭代器的末尾是最后一个键的列表的末尾

#include <vector>
#include <boost/unordered_map.hpp>
#include <cassert>
#include <iostream>
#include <boost/iterator/iterator_adaptor.hpp>


class DS {
public:
    DS() : _map() {}

    ~DS() {
        for (Map::iterator it = _map.begin(); it != _map.end(); ++it) {
            delete (it->second);
        }
    }

    void add(int key_, const std::vector< int > &value_)
    {
        IntList *ptr = new IntList(value_);
        assert(ptr);

        _map.insert(Map::value_type(key_, ptr));
    }

private:
    typedef std::vector< int > IntList;
    typedef boost::unordered_map< int, IntList* > Map;

    Map      _map;

public:
    class KeyIter : public boost::iterator_adaptor< KeyIter,
                                                    Map::const_iterator,
                                                    int,
                                                    boost::forward_traversal_tag,
                                                    int>
    {
    public:
        KeyIter() : KeyIter::iterator_adaptor_() {}

    private:

        friend class DS;
        friend class boost::iterator_core_access;

        explicit KeyIter(Map::const_iterator it) : KeyIter::iterator_adaptor_(it) {}
        explicit KeyIter(Map::iterator       it) : KeyIter::iterator_adaptor_(it) {}

        int        dereference() const { return this->base()->first; }
    };

    class ValueIter : public boost::iterator_adaptor< ValueIter,
                                                      Map::const_iterator,
                                                      int,
                                                      boost::forward_traversal_tag,
                                                      int>
    {
    public:
        ValueIter()
                : ValueIter::iterator_adaptor_()
                , _lIt()
        {}

    private:
        friend class DS;
        friend class boost::iterator_core_access;

        explicit ValueIter(Map::const_iterator it)
                : ValueIter::iterator_adaptor_(it)
                , _lIt()
                , _mIt(it)
        {
            IntList *pt = it->second; // <<-- issue here is I can't find if I've already reached the end of the map
            if (pt) {
                _lIt = it->second->begin();
            }
        }

        int                dereference() const { return *_lIt; }
        void               increment()
        {
            if (_lIt == _mIt->second->end()) {
                ++_mIt;
                _lIt = _mIt->second->begin();
            } else {
                ++_lIt;
            }
        }

        IntList::iterator        _lIt;
        Map::const_iterator      _mIt;
    };

    KeyIter       beginKey() const { return KeyIter(_map.begin()); }
    KeyIter       endKey()   const { return KeyIter(_map.end());  }
    ValueIter     beginValue() const { return ValueIter(_map.begin()); }
    ValueIter     endValue()   const { return ValueIter(_map.end());   }
};





int main(int argc, char** argv)
{

    DS ds;

    std::vector< int > v1;
    v1.push_back(10);
    v1.push_back(30);
    v1.push_back(50);

    ds.add(90, v1);

    std::vector< int > v2;
    v2.push_back(20);
    v2.push_back(40);
    v2.push_back(60);

    ds.add(120, v2);

    std::cout << "------------ keys ---------------" << std::endl;
    for (DS::KeyIter it = ds.beginKey(); it != ds.endKey(); ++it) {
        std::cout << (*it) << std::endl;
    }

    std::cout << "------------ values ---------------" << std::endl;
    // std::cout << (*(ds.beginValue())) << std::endl;
    for (DS::ValueIter it = ds.beginValue(); it != ds.endValue(); ++it) {
        std::cout << (*it) << std::endl;
    }

    return 0;
}

Answer 1

在 C++11 中实现。您应该能够相当简单地完成到 boost/c++03 的转换。

这个迭代器是 FORWARD ONLY 并且它非常脆弱(参见比较运算符)。

建议用户自行决定。

#include <iostream>
#include <vector>
#include <unordered_map>

typedef std::vector< int > IntList;
typedef std::unordered_map< int, IntList* > Map;

struct whole_map_const_iterator
{
    using C1 = IntList;
    using C2 = Map;

    using I1 = C1::const_iterator;
    using I2 = C2::const_iterator;

    using value_type = I1::value_type;
    using reference = I1::reference;

    whole_map_const_iterator(I2 i2) : _i2(i2) {}

    bool operator==(const whole_map_const_iterator& r) const {
        if (_i2 != r._i2)
            return false;

        if (deferred_i1 && r.deferred_i1)
            return true;

        if (deferred_i1 != r.deferred_i1)
            return false;

        return _i1 == r._i1;
    }
    bool operator!=(const whole_map_const_iterator& r) const { return !(*this == r); }

    reference operator*() const {
        check_deferred();
        return *_i1;
    }

    void check_deferred() const {
        if (deferred_i1) {
            _i1 = _i2->second->begin();
            _i1limit = _i2->second->end();
            deferred_i1 = false;
        }
    }

    void go_next()
    {
        check_deferred();
        if (++_i1 == _i1limit) {
            ++_i2;
            deferred_i1 = true;
        }
    }

    whole_map_const_iterator& operator++() {
        go_next();
        return *this;
    }

    whole_map_const_iterator operator++(int) {
        auto result = *this;
        go_next();
        return result;
    }

    I2 _i2;
    mutable I1 _i1 = {}, _i1limit = {};
    mutable bool deferred_i1 = true;

};

IntList a { 1, 2, 3, 4, 5 };
IntList b { 6, 7, 8, 9, 10 };
Map m { { 1, &a }, { 2, &b } };


int main()
{
    using namespace std;
    auto from = whole_map_const_iterator(m.begin());
    auto to = whole_map_const_iterator(m.end());
    for ( ; from != to ; ++from) {
        std::cout << *from << std::endl;
    }
    return 0;
}

示例输出:

6
7
8
9
10
1
2
3
4
5

对于奖励积分，请回答这个问题:

问:为什么延迟标志会出现那么多该死的复杂情况？