C++笛卡尔积迭代器在第一次迭代时调用基类函数

Question

我正在开发一组 n 维笛卡尔积类，基于此 解决方案。我有许多不同的数据类型适用于相同的基本算法，所以我想：“啊哈！我将使用模板来减少我的工作量！”直到现在，这个想法一直很好。我正在使用 Boost 的 iterator_facade。

我的问题是，我制作了一个派生类来处理 map<char, boost::integer_range<int> >。每次迭代都会生成一个 map<char,int>，但我排除了第二个值为 0 的键值对，因为它们从算法的角度来看只是浪费空间。

这个派生类重载了生成迭代器返回值的函数，并且它起作用了。然而，在第一次迭代期间，基类的生成器被调用了。我非常困惑。有人有什么想法吗？

以下是相关的代码片段：

#include <boost/container/flat_map.hpp>
#include <boost/tuple/tuple.hpp>
#include <boost/iterator/iterator_facade.hpp>
#include <boost/range/irange.hpp>
#include <utility>
#include <iostream>

using namespace boost;
using namespace boost::tuples;
using namespace std;

template <class Container2DMap,
    class return_type = boost::container::flat_map<typename Container2DMap::value_type::first_type,
    typename Container2DMap::value_type::second_type::value_type> >
class CartProductIterator2DMap : public boost::iterator_facade<
CartProductIterator2DMap<Container2DMap, return_type>,
const return_type,
boost::forward_traversal_tag> {
public:
    typedef typename Container2DMap::value_type::first_type first_type;
    typedef typename Container2DMap::const_iterator first_iterator;
    typedef typename Container2DMap::value_type::second_type::value_type second_type;
    typedef typename Container2DMap::value_type::second_type::const_iterator second_iterator;

    CartProductIterator2DMap(const Container2DMap &container) {
        rangeIterSetup(container);
    }

    CartProductIterator2DMap() : _finished(true) {}
    virtual ~CartProductIterator2DMap() {}
private:
    virtual bool equal(const CartProductIterator2DMap &other) const {
        if (_finished || other._finished) {
            if (_finished && other._finished) {
                return true;
            } else {
                return false;
            }
        } else if (_currentIter == other._currentIter) {
            return true;
        } else {
            return false;
        }
    }
    virtual void increment() { advance(); }
    virtual void advance() {
        advanceIter();
    }

    virtual const return_type& dereference() const { return _currentIter; }

protected:
    struct mode {
        const static bool stopIter = false;
        const static bool continueIter = true;
    };
    typedef boost::tuple<second_iterator,
            second_iterator,
            second_iterator> SecondIterDescription;
    typedef boost::container::flat_map<first_type, SecondIterDescription> RangeIterMap;
    friend class boost::iterator_core_access;
    return_type _currentIter;
    RangeIterMap _rangeIter;
    bool _finished;
    bool _iterMode;

    virtual void advanceIter() {
        if (_iterMode == mode::continueIter) {
            _currentIter = genReturnValue(_rangeIter);
            _iterMode = advanceRangeIter(_rangeIter);
        } else {
            _finished = true;
        }
    }
    virtual void rangeIterSetup(const Container2DMap &container) {
        _finished = false;
        if (container.empty()) {
            _iterMode = mode::stopIter;
        } else {
            _iterMode = mode::continueIter;
            for (typename Container2DMap::const_iterator it =  container.begin();
                    it != container.end(); ++it) {
                _rangeIter.insert(
                        make_pair(it->first,
                                SecondIterDescription(it->second.begin(), it->second.end(), it->second.begin())
                                )
                                );
            }
            advance();
        }
    }


    virtual return_type genReturnValue(const RangeIterMap &rangeIter) {
        std::cout << "Calling base class." << std::endl;
        return_type returnValue;
            for( typename RangeIterMap::const_iterator it = rangeIter.begin();
                    it != rangeIter.end(); ++it) {
                returnValue.insert(
                        make_pair(it->first, *get<2>(it->second))
                        );
            }
        return returnValue;
    }

    virtual bool advanceRangeIter(RangeIterMap &rangeIter) {
        for (typename RangeIterMap::iterator it = rangeIter.begin(); ; ) {
            ++(get<2>(it->second));
            if (get<2>(it->second) == get<1>(it->second)) {
                if (it + 1 == rangeIter.end()) {
                    return mode::stopIter;
                } else {
                    // cascade
                    get<2>(it->second) = get<0>(it->second);
                    ++it;
                }

            } else {
                // normal break point
                return mode::continueIter;
            }
        }
        return mode::continueIter;
    }
};

typedef boost::integer_range<int> _intRange;
typedef boost::container::flat_map<char, _intRange> CharRange;
typedef boost::container::flat_map<char, int> ResidueCount;

template <class Container2D,
    class return_type = boost::container::flat_map<typename Container2D::value_type::first_type,
    typename Container2D::value_type::second_type::value_type> >
struct BaseIterContainer {
    typedef CartProductIterator2DMap<Container2D, return_type> const_iterator;
    const Container2D &_container;
    BaseIterContainer( const Container2D &container) : _container(container) {}
    const_iterator begin() const { return const_iterator(_container); }
    const_iterator end() const { return const_iterator(); }
};

typedef BaseIterContainer<CharRange, ResidueCount> BaseCharRangeIter;

typedef CartProductIterator2DMap<CharRange, ResidueCount> BaseCPIterator;
class DerivedCPIterator : public BaseCPIterator {
public:
    DerivedCPIterator() : BaseCPIterator() {}
    DerivedCPIterator(const CharRange & charRange) : BaseCPIterator(charRange) {}
protected:
    ResidueCount genReturnValue(const RangeIterMap &rangeIter) {
        std::cout << "Calling derived class." << std::endl;
        ResidueCount returnValue;
            for( RangeIterMap::const_iterator it = rangeIter.begin();
                    it != rangeIter.end(); ++it) {
                    const char aa = it->first;
                    const int aaCount = *get<2>(it->second);
                    if (aaCount > 0) {
                        returnValue.insert(
                                make_pair(aa, aaCount)
                        );
                    }
            }
        return returnValue;
    }
};

struct DerivedCharRangeIter {
    typedef DerivedCPIterator const_iterator;
    const CharRange &_container;
    DerivedCharRangeIter( const CharRange &container) : _container(container) {}
    const_iterator begin() const { return const_iterator(_container); }
    const_iterator end() const { return const_iterator(); }
};

std::ostream& operator<<(std::ostream& out, const ResidueCount &rCount) {
    foreach(const ResidueCount::value_type& aaCount, rCount) {
        char aa = aaCount.first;
        int totalAACount = aaCount.second;
        out << "(" << aa << "," << totalAACount << ")";
    }
    return out;
}



int main(int argc, char **argv) {
    cout << "Base Container" << endl;
    CharRange test;
    test.insert(make_pair('a', _intRange(0, 3)));
    test.insert(make_pair('b', _intRange(0, 3)));
    BaseCharRangeIter t(test);
    BaseCharRangeIter::const_iterator it = t.begin();
    for( ;it != t.end(); ++it) {
        cout << *it << endl;
    }
    cout << endl;
    cout << "Derived Container: " << endl;
    DerivedCharRangeIter r(test);
    DerivedCharRangeIter::const_iterator rt = r.begin();
    for( ; rt != r.end(); ++rt) {
        cout << *rt << endl;
    }
    return 0;
}

我得到的结果：

---

Base Container
Calling base class.
(a,0)(b,0)
Calling base class.
(a,1)(b,0)
Calling base class.
(a,2)(b,0)
Calling base class.
(a,0)(b,1)
Calling base class.
(a,1)(b,1)
Calling base class.
(a,2)(b,1)
Calling base class.
(a,0)(b,2)
Calling base class.
(a,1)(b,2)
Calling base class.
(a,2)(b,2)

Derived Container: 
Calling base class.
(a,0)(b,0)
Calling derived class.
(a,1)
Calling derived class.
(a,2)
Calling derived class.
(b,1)
Calling derived class.
(a,1)(b,1)
Calling derived class.
(a,2)(b,1)
Calling derived class.
(b,2)
Calling derived class.
(a,1)(b,2)
Calling derived class.
(a,2)(b,2)

每个genReturnValue在每次调用时都会打印其类（基类或派生类）。基类函数按照预期工作。然而，派生类没有。第一次迭代调用了基类的genReturnValue，并且0没有被过滤掉。但是，进一步的迭代则可以。

由于这是我第一次尝试使用模板和派生类，我肯定错过了一些显而易见的东西，但是我无法弄清楚。GCC 4.6.3和Clang 3.0-6提供相同的输出。

帮忙！

另外，我相对新于C++编程。如果您有任何批评，风格或其他方面，我很乐意接受。谢谢！

- notwithoutend

Answer 1

实际上，这与指针无关；而是由于虚函数在构造和析构期间的基类和派生类销毁顺序限制，因此它们被静态解析。

也就是说，在Base的构造函数或析构函数中调用virtualfunc时，会（以某种方式）将其解析为Base::virtualfunc。如果这是一个纯虚函数，则会导致未定义行为。

因此，一般的准则是：

• 永远不要从构造函数或析构函数中调用虚函数。

例如：

struct Base {
    Base() { call(); }

    virtual call() { std::cout << "Base\n"; }
};

struct Derived: Base {
    Derived(int i): _i(i);

    virtual call() { std::cout << "Derived" << _i << "\n"; }

    int _i;
};

int main() {
    Derived d(1);
};

这将打印出Base，而不是你可能期望的Derived1；这有一个很好的理由：记住事物的构建顺序：

• 调用Derived()
• 它自动调用Base()
• 它调用_i(i)
• 进入Derived()的主体，什么也不做

因此，当调用Base()时，_i还没有被初始化，所以调用call将是愚蠢的。幸运的是，标准在这里提供了一个很好的解决方法，尽管大多数情况下，这不是你最初期望的。

- Matthieu M.

---

哇，太棒了。非常感谢你。现在我知道了底层策略，原因变得非常合理。感谢你抽出时间来回答我的问题。 - notwithoutend

Answer 2

你的基类 CartProductIterator2DMap 有一个调用虚函数的构造函数：

CartProductIterator2DMap(const Container2DMap &container) {
    rangeIterSetup(container);
}

这个虚函数最终会调用另一个虚函数：genReturnValue。

现在，在基类构造函数执行时，派生类尚未被构造。因此，来自基类构造函数的对 genReturnValue 的调用会调用 CartProductIterator2DMap::genReturnValue。但是，在对象完全构造之后的后续调用将调用：DerivedCPIterator::genReturnValue。

您需要确保您的基类构造函数不会调用任何虚函数。

- zdan