专门化 iterator_traits

发布于 2024-12-12 13:11:37 字数 1481 浏览 0 评论 0原文

我想将 std::iterator_traits<> 专门用于容器类模板的迭代器,该模板具有通常的嵌套 typedef(例如 value_type) code>、difference_type 等),我不应该修改其源代码。基本上我想做这样的事情:

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

除了这不起作用,因为编译器无法从 Container::iterator 推导出 T

有什么可行的方法可以达到同样的目的吗?


例如:

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::difference_typeiterator_traits 的主要模板仅执行 typedef typename I::difference_type Difference_type。与其他嵌套类型相同。

现在,在我们的示例中,这显然行不通,因为没有 Container::iterator::difference_type。我认为我可以通过将 iterator_traits 专门用于任何 Container 的迭代器来解决这个问题,而无需修改迭代器类。

最后,我只是希望能够使用 std 算法,如计数、查找、排序等,最好不修改任何现有代码。我认为 iterator_traits 的全部要点就是:能够为迭代器类型指定类型(如 value_type、diff_type 等),不支持它们内置。不幸的是,我无法弄清楚如何为 Container 的所有实例专门化特征类。

I'd like to specialize std::iterator_traits<> for iterators of a container class template that does not have the usual nested typedefs (like value_type, difference_type, etc.) and whose source I shouldn't modify. Basically I'd like to do something like this:

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

except that this doesn't work, as the compiler is unable to deduce T from Container<T>::iterator.

Is there any working way to achieve the same?


For example:

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() { ... }
    ...
}; 

Now suppose I call std::count() using an instance of this class. As far as I know, in most STL implementations, count() returns iterator_traits<Iterator>::difference_type. The primary template of iterator_traits<I> simply does typedef typename I::difference_type difference_type. Same with the other nested types.

Now in our example this obviously won't work, as there's no Container::iterator::difference_type. I thought I could work around this without modifying the iterator class, by specializing iterator_traits for iterators of any Container<T>.

In the end, I just want to be able to use std algorithms like count, find, sort, etc., preferably without modifying any existing code. I thought that the whole point of iterator_traits is exactly that: being able to specify types (like value_type, diff_type etc.) for iterator types that do not support them built-in. Unfortunately I can't figure out how to specialize the traits class for all instances of Container<T>.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(4

一笔一画续写前缘 2024-12-19 13:11:37

是的。编译器无法从 Container::iterator 推断出 T,因为它是不可推断的上下文,换句话说,给定 Container: :iteratorT的值不能唯一可靠地推导(参见详细说明)。

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

Yes. The compiler cannot deduce T from Container<T>::iterator because it is non-deducible context, which in other words means, given Container<T>::iterator, the value of T cannot uniquely and reliably be deduced (see this for detail explanation).

The only solution to this problem is that you've to fully specialize iterator_traits for each possible value of iterator which you intend to use in your program. There is no generic solution, as you're not allowed to edit the Container<T> class template.

南风几经秋 2024-12-19 13:11:37

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

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

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(); }
    }; 
}

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

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*>
    {
    };
}

然后,对于我们希望能够使用 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 处所需的 includeusing .com/gJyGxU。输出:

a=Hello, world
count(a, a + sizeof(a), 'l')=3
count(container.begin(), container.end(), 0)=[in adapter version of count]0

不幸的是,有一些警告:

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

关于最后一个,问题是在哪个命名空间中放置重载(以及如何调用 std 版本)。理想情况下,它应该位于 ThirdPartyLib 中,以便可以通过参数相关的查找找到它,但我假设我们无法更改这一点。下一个最佳选择是在 MyLib 中,但调用必须经过 using 限定或在其前面。在任何一种情况下,最终用户都应该使用 using std::count; 或注意哪些调用需要使用 std:: 进行限定,因为 if std: :count 被错误地与 SomeContainerFromAThirdPartyLib::iterator 一起使用,它显然会失败(这个练习的全部原因)。

不建议但出于完整性考虑而在此提出的另一种选择是将其直接放在std命名空间中。这会导致未定义的行为;虽然它可能对您有用,但标准中没有任何内容可以保证它。如果我们专门化 count 而不是重载它,那么这将是合法的。

Nawaz's answer is likely the right solution for most cases. However, if you're trying to do this for many instantiated SomeContainerFromAThirdPartyLib<T> classes and only a few functions (or an unknown number of instantiations but a fixed number of functions, as might happen if you're writing your own library), there's another way.

Assume we're given the following (unchangeable) code:

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(); }
    }; 
}

We define an adapter class template containing the necessary typedefs for iterator_traits and specialize it to avoid problems with pointers:

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*>
    {
    };
}

Then, for each function we want to be able to call with a SomeContainerFromAThirdPartyLib::iterator, we define an overload and use 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);
}

We can then use it as follows:

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;
}

You can find a runnable example with the required includes and usings at http://ideone.com/gJyGxU. The output:

a=Hello, world
count(a, a + sizeof(a), 'l')=3
count(container.begin(), container.end(), 0)=[in adapter version of count]0

Unfortunately, there are caveats:

  • As I said, an overload needs to be defined for each function you plan to support (find, sort, et cetera). This obviously won't work for functions in algorithm that haven't been defined yet.
  • If not optimized out, there may be small run-time performance penalties.
  • There are potential scoping issues.

In regards to that last one, the question is in which namespace to put the overload (and how to call the std version). Ideally, it would be in ThirdPartyLib so that it could be found by argument-dependant lookup, but I've assumed we can't change that. The next best option is in MyLib, but then the call has to be qualified or preceded by a using. In either case the end-user should either use using std::count; or be careful about which calls to qualify with std::, since if std::count is mistakenly used with SomeContainerFromAThirdPartyLib::iterator, it will obviously fail (the whole reason for this exercise).

An alternative that I do not suggest but present here for completeness would be to put it directly in the std namespace. This would cause undefined behavior; while it might work for you, there's nothing in the standard that guarantees it. If we were specializing count instead of overloading it, this would be legal.

已下线请稍等 2024-12-19 13:11:37

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

如果第三方库在各自的命名空间中没有提供任何免费的 beginend 函数,则可以编写自己的函数(如果需要启用 ADL,则可以写入该命名空间)并包装将迭代器放入自己的包装类中,该包装类又提供必要的类型定义和运算符。

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

#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 继承 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());
  }
}

也可以将它们放在与 SomeContainer 不同的命名空间中,但是如果有宽松的ADL。 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));
}

此类代码可以与 std::vector 以及 ThirdPartyLib::SomeContainer 一起使用,只要 ADL 找到 begin()>end() 返回包装迭代器。

In the specialization in question, T is in a nondeducible context but there is neither a third party library container code change nor any specialization in the std namespace required.

If the third party library does not provide any free begin and end functions in the respective namespace one can write own functions (into that namespace if desired to enable ADL) and wrap the iterator into an own wrapper class which in turn provides the necessary typedefs and operators.

First one needs the Iterator wrapper.

#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;
    }
  };

}

Note: It would also be possible to make iterator_wrapper inherit from Iterator, or to make it more generic and have another helper to enable the wrapping of other iterators as well.

Now begin() and 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());
  }
}

(It is also possible to have them in a different namespace than SomeContainer but loose ADL. IF there are begin and end functions present in the namespace for that container I'd tend to rename the adaptors to be something like wbegin and wend.)

The standard algorithms can be called using those functions now:

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

If begin() and end() are included into the library namespace, the container can even be used in more generic contexts.

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));
}

Such code can be used with std::vector as well as ThirdPartyLib::SomeContainer, as long as ADL finds begin() and end() returning the wrapper iterator.

陌伤浅笑 2024-12-19 13:11:37

您可以很好地使用 Container 作为 iterator_traits 的模板参数。对于 STL 的其余部分来说,重要的是特征类中的 typedef,例如 value_type。这些应该正确设置:

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

然后您将在之前使用 T 的地方使用 value_type

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

iterator_traits<TheContainer> traits;

当然,这假设 TheContainer 符合常见的 STL 容器的约定并具有 value_type 定义正确。

You can very well use the Container as template parameter to your iterator_traits. What matters to the rest of STL are the typedefs inside your traits class, such as value_type. Those should be set correctly:

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

You would then use value_type where you would previously use T.

As for using the traits class, you of course parametrize it with the type of your external container:

iterator_traits<TheContainer> traits;

Naturally, this assumes TheContainer is conforms to the common STL containers' contract and has value_type defined correctly.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文