11

我想专门std::iterator_traits<>研究一个容器类模板的迭代器,它没有通常的嵌套 typedef(如value_typedifference_type等)并且我不应该修改其源代码。基本上我想做这样的事情:

template <typename T> struct iterator_traits<typename Container<T>::iterator> 
{
    typedef T value_type; 
    //  etc.
}; 

除了这不起作用,因为编译器无法TContainer<T>::iterator.

有什么可行的方法来实现同样的目标吗?


例如:

template <typename T>
class SomeContainerFromAThirdPartyLib
{
    typedef T ValueType;    //  not value_type! 
    //  no difference_type

    class iterator
    {
        typedef T ValueType;    //  not value_type! 
        //  no difference_type  
        ...
    }; 
    iterator begin() { ... }
    iterator end() { ... }
    ...
}; 

现在假设我std::count()使用这个类的一个实例来调用。据我所知,在大多数 STL 实现中,count()返回iterator_traits<Iterator>::difference_type. 的主要模板iterator_traits<I>只是typedef typename I::difference_type difference_type. 与其他嵌套类型相同。

现在在我们的示例中,这显然行不通,因为没有Container::iterator::difference_type. 我想我可以在不修改迭代器类的情况下解决这个问题,专门iterator_traits针对 any 的迭代器Container<T>

最后,我只想能够使用标准算法,如计数、查找、排序等,最好不修改任何现有代码。我认为整点iterator_traits就是:能够为不支持内置的迭代器类型指定类型(如 等)value_typediff_type不幸的是,我无法弄清楚如何为Container<T>.

4

4 回答 4

12

是的。编译器无法推断TContainer<T>::iterator因为它是不可推断的上下文,换句话说,这意味着,给定Container<T>::iterator的值T不能唯一且可靠地推断出来(有关详细说明,请参阅this)。

这个问题的唯一解决方案是您必须完全专门化您打算在程序中使用的iterator_traits每个可能的值。iterator没有通用的解决方案,因为您不允许编辑Container<T>类模板。

于 2011-10-28T10:21:44.357 回答
5

Nawaz 的答案可能是大多数情况下的正确解决方案。但是,如果您尝试对许多实例化SomeContainerFromAThirdPartyLib<T>的类和只有几个函数(或未知数量的实例化但固定数量的函数,这可能会在您编写自己的库时发生)执行此操作,那么还有另一种方法。

假设我们得到以下(不可更改的)代码:

namespace ThirdPartyLib
{
    template <typename T>
    class SomeContainerFromAThirdPartyLib
    {
        public:
            typedef T ValueType;    //  not value_type! 
            //  no difference_type

            class iterator
            {
                public:
                    typedef T ValueType;    //  not value_type! 
                    //  no difference_type

                    // obviously this is not how these would actually be implemented
                    int operator != (const iterator& rhs) { return 0; }
                    iterator& operator ++ () { return *this; }
                    T operator * () { return T(); }
            };

            // obviously this is not how these would actually be implemented      
            iterator begin() { return iterator(); }
            iterator end() { return iterator(); }
    }; 
}

我们定义了一个适配器类模板,其中包含必要typedef的 siterator_traits并对其进行专门化以避免指针问题:

namespace MyLib
{
    template <typename T>
    class iterator_adapter : public T
    {
        public:
            // replace the following with the appropriate types for the third party iterator
            typedef typename T::ValueType value_type;
            typedef std::ptrdiff_t difference_type;
            typedef typename T::ValueType* pointer;
            typedef typename T::ValueType& reference;
            typedef std::input_iterator_tag iterator_category;

            explicit iterator_adapter(T t) : T(t) {}
    };

    template <typename T>
    class iterator_adapter<T*>
    {
    };
}

然后,对于我们希望能够使用 a 调用的每个函数SomeContainerFromAThirdPartyLib::iterator,我们定义一个重载并使用 SFINAE:

template <typename iter>
typename MyLib::iterator_adapter<iter>::difference_type
count(iter begin, iter end, const typename iter::ValueType& val)
{
    cout << "[in adapter version of count]";
    return std::count(MyLib::iterator_adapter<iter>(begin), MyLib::iterator_adapter<iter>(end), val);
}

然后我们可以按如下方式使用它:

int main()
{
    char a[] = "Hello, world";

    cout << "a=" << a << endl;
    cout << "count(a, a + sizeof(a), 'l')=" << count(a, a + sizeof(a), 'l') << endl; 

    ThirdPartyLib::SomeContainerFromAThirdPartyLib<int> container;
    cout << "count(container.begin(), container.end(), 0)=";
    cout << count(container.begin(), container.end(), 0) << std;

    return 0;
}

您可以在http://ideone.com/gJyGxU找到一个带有所需includes 和usings的可运行示例。输出:

a=你好,世界
计数(a, a + sizeof(a), 'l')=3
count(container.begin(), container.end(), 0)=[在 count 的适配器版本中]0

不幸的是,有一些警告:

  • 正如我所说,需要为您计划支持的每个函数定义一个重载(find,,sort等等)。这显然不适用于algorithm尚未定义的函数。
  • 如果不进行优化,可能会有小的运行时性能损失。
  • 存在潜在的范围界定问题。

关于最后一个,问题是在哪个命名空间中放置重载(以及如何调用std版本)。理想情况下,它ThirdPartyLib可以通过依赖于参数的查找找到它,但我假设我们无法改变它。下一个最佳选项是 in MyLib,但是调用必须有限定或前面有 a using。在任何一种情况下,最终用户都应该使用using std::count;或注意哪些调用符合条件std::,因为如果std::count错误地与 一起使用SomeContainerFromAThirdPartyLib::iterator,它显然会失败(这个练习的全部原因)。

为了完整起见,我不建议但在这里展示的另一种方法是将其直接放在std名称空间中。这会导致未定义的行为;虽然它可能对您有用,但标准中没有任何东西可以保证它。如果我们专门count化而不是重载它,这将是合法的。

于 2013-06-08T21:24:54.230 回答
2

在所讨论的专业化中,T是在不可推论的上下文中,但既没有第三方库容器代码更改,也不std需要命名空间中的任何专业化。

如果第三方库在各自的命名空间中不提供任何自由beginend函数,则可以编写自己的函数(如果需要启用 ADL,则写入该命名空间)并将迭代器包装到自己的包装类中,该包装类反过来提供必要的 typedef 和运算符。

第一个需要迭代器包装器。

#include <cstddef>

namespace ThirdPartyStdAdaptor
{

  template<class Iterator>
  struct iterator_wrapper
  {
    Iterator m_it;
    iterator_wrapper(Iterator it = Iterator())
      : m_it(it) { }
    // Typedefs, Operators etc.
    // i.e.
    using value_type = typename Iterator::ValueType;
    using difference_type = std::ptrdiff_t;
    difference_type operator- (iterator_wrapper const &rhs) const
    {
      return m_it - rhs.m_it;
    }
  };

}

注意:也可以iterator_wrapper继承 from Iterator,或者使其更通用,并使用另一个帮助器来启用其他迭代器的包装。

现在begin()end()

namespace ThirdPartyLib
{
  template<class T>
  ThirdPartyStdAdaptor::iterator_wrapper<typename 
    SomeContainer<T>::iterator> begin(SomeContainer<T> &c)
  {
    return ThirdPartyStdAdaptor::iterator_wrapper<typename
      SomeContainer<T>::iterator>(c.begin());
  }
  template<class T>
  ThirdPartyStdAdaptor::iterator_wrapper < typename
    SomeContainer<T>::iterator > end(SomeContainer<T> &c)
  {
    return ThirdPartyStdAdaptor::iterator_wrapper < typename
      SomeContainer<T>::iterator > (c.end());
  }
}

(也可以将它们放在与SomeContainerADL 不同但松散的名称空间中。如果该容器的名称空间中存在beginend函数,我倾向于将适配器重命名为wbeginwend。)

现在可以使用这些函数调用标准算法:

ThirdPartyLib::SomeContainer<SomeType> test;
std::ptrdiff_t d = std::distance(begin(test), end(test));

如果begin()end()包含在库命名空间中,则容器甚至可以在更通用的上下文中使用。

template<class T>
std::ptrdiff_t generic_range_size(T const &x)
{
  using std::begin;
  using std::end;
  return std::distance(begin(x), end(x));
}

只要 ADL 找到并返回包装迭代器,此类代码就可以与std::vectoras 和一起使用。ThirdPartyLib::SomeContainerbegin()end()

于 2015-03-14T14:08:11.547 回答
0

您可以很好地将Containeras 模板参数用于您的iterator_traits. 对 STL 的其余部分而言重要的是特征类中的 typedef,例如value_type. 这些应该正确设置:

template <class Container> struct iterator_traits
{
    public:
        typedef typename Container::value_type value_type;
    // etc.
};

然后value_type,您将使用以前使用T的 .

至于使用特征类,您当然可以使用外部容器的类型对其进行参数化:

iterator_traits<TheContainer> traits;

当然,这假定TheContainer是符合通用 STL 容器的合同并已value_type正确定义。

于 2011-10-28T10:07:07.420 回答