如何在不使用原始指针的情况下为 class 类型编写自定义 STL 迭代器?这有实际优势吗?
How can I write a custom STL iterator for a class type without using raw pointers? Is there a practical advantage to this?
这个问题的标题曾经是:与 return 从开始和结束函数中获取原始指针相比,创建迭代器 class 有实际优势吗?
最近我一直在研究使用 MFC 和 objects 的代码库,例如 CArray<T, U>
.
已编写的部分新代码使用了 STL 和 <algorithm>
库。
例如
CArray<int int> carray;
carray // do stuff
std::vector<int> stlvector(begin(carray), end(carray));
stlvector.dostuff() // do stuff
我最近问了一个 question 关于为 class 创建迭代器的问题,比如 CArray
,我无权访问。
我现在对此有一些进一步的疑问。第一题可以查到here。这是我的第二个问题:
begin
和 end
函数 return 应该是原始指针还是迭代器?
在上面的链接问题中,提供了一个示例作为 return 原始指针的答案。这个答案与我使用的实现非常相似。
template<typename T, typename U>
auto begin(const CArray<T, U> &array>)
{
return &array[0];
}
template<typename T, typename U>
auto end(const CArray<T, U> &array>)
{
return (&array[array.GetCount() - 1]) + 1;
}
这些函数return 原始指针。但是我试图实现一个迭代器解决方案。到目前为止我还没有成功。
我在研究中使用的主要参考资料可以在这里找到:
第一次尝试
这是我第一次尝试寻找解决方案。
你可以玩这个代码here。
#include <iostream>
#include <iterator>
#include <algorithm>
template <typename U>
class CArrayForwardIt
{
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = U;
using pointer = U*;
using reference = U&;
public:
CArrayForwardIt(pointer ptr)
: m_ptr(ptr)
{
}
// = default?
//CArrayForwardIt(CArrayForwardIt<U> other)
// : m_ptr(ptr)
// {
// }
reference operator*() const
{
return *m_ptr;
}
// what does this do, don't understand why operator-> is needed
// or why it returns a U* type
pointer operator->()
{
return m_ptr;
}
CArrayForwardIt& operator++()
{
++ m_ptr;
return *this;
}
CArrayForwardIt operator++(int)
{
CArrayForwardIt tmp(*this);
++ (*this);
return tmp;
}
friend bool operator==(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
{
return lhs.m_ptr == rhs.m_ptr;
}
friend bool operator!=(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
{
return !(lhs == rhs);
}
private:
pointer m_ptr;
};
template<typename T, typename U>
auto begin(const CArray<T, U> &array)
{
return CArrayForwardIt<U>(&array[0]);
}
template<typename T, typename U>
auto end(const CArray<T, U> &array)
{
return CArrayForwardIt<U>((&array[array.GetCount() - 1]) + 1);
}
int main()
{
CArray<int, int> c;
// do something to c
std::vector<int> v(begin(c), end(c));
return 0;
}
这是我尝试编译它时发生的情况(使用 Visual Studio 2019 Pro)。
no instance of constructor "std::vector<_Ty, _Alloc>::vector [with _Ty=int, _Alloc=std::allocator<int>]" matches argument list
'<function-style-cast>': cannot convert from 'contt TYPE*' to 'std::CArrayForwardIt<U>'
'std::vector<int, std::allocator<int>>::vector(std::vector<int, std::allocator<int>> &&, const _Alloc &) noexcept(<expr>)': cannot convert from argument 1 from 'void' to 'const unsigned int'
我对gcc比较熟悉,对如何理解这一点知之甚少
第二次尝试
我又做了两次尝试,但它们非常相似。
一个是将我的 class CArrayForwardIt
更改为从 iterator<std::forward_iterator_tag, std::ptrdiff_t, U, U*, U&>
继承,并删除 class 顶部的 using...
行。这似乎并没有让我更接近解决方案。
此外,我查看了 std::vector
的构造函数定义。参见 here。
我在这里可能有误解,但看起来 std::vector
需要一个 InputIt
类型的参数。
因此我尝试将我的 class 改成这样:
#include <iostream>
#include <iterator>
#include <algorithm>
template <typename U>
class forward_iterator
{
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = U;
using pointer = U*;
using reference = U&;
public:
forward_iterator(pointer ptr)
: m_ptr(ptr)
{
}
// = default?
//forward_iterator(forward_iterator<U> other)
// : m_ptr(ptr)
// {
// }
reference operator*() const
{
return *m_ptr;
}
// what does this do, don't understand why operator-> is needed
// or why it returns a U* type
pointer operator->()
{
return m_ptr;
}
forward_iterator& operator++()
{
++ m_ptr;
return *this;
}
forward_iterator operator++(int)
{
forward_iterator tmp(*this);
++ (*this);
return tmp;
}
friend bool operator==(const forward_iterator& lhs, const forward_iterator& rhs)
{
return lhs.m_ptr == rhs.m_ptr;
}
friend bool operator!=(const forward_iterator& lhs, const forward_iterator& rhs)
{
return !(lhs == rhs);
}
private:
pointer m_ptr;
};
template<typename T, typename U>
auto begin(const CArray<T, U> &array)
{
return forward_iterator<U>(&array[0]);
}
template<typename T, typename U>
auto end(const CArray<T, U> &array)
{
return forward_iterator<U>((&array[array.GetCount() - 1]) + 1);
}
int main()
{
CArray<int, int> c;
// do something to c
std::vector<int> v(begin(c), end(c));
return 0;
}
这也许不足为奇,也没有编译。在这一点上,我变得困惑。 std::vector
似乎需要 InputIt
类型,forward_iterator
应该适用,但重新定义 forward_iterator
似乎没有意义,即使我写这个class 在命名空间之外 std
.
问题
我相当确定应该有一种方法可以为 MFC CArray
编写迭代器 class,它可以由 begin
和 [=] 编辑 return 20=] 函数。但是,我对如何执行此操作感到困惑。
关于编写工作解决方案的问题,我开始怀疑这样做是否有任何实际优势?我想做的事情有意义吗?原始指针解决方案显然有效,那么投入精力编写基于迭代器的解决方案有什么好处吗?例如,迭代器解决方案能否提供更复杂的边界检查?
自从我成功完成这项工作后,我想 post 一个解决方案,希望我在转录它时不会犯太多错误。
上面代码片段中没有显示的一件事是,所有这些 class 和函数定义都存在于命名空间 std
中。我之前 post 对此提出了另一个问题,并被告知这些东西不应该在命名空间 std
内。更正这个似乎解决了一些问题,使解决方案更近了一步。
你可以找到那个问题here。
这是我目前所掌握的:这是为程序员无法访问的外部 class 编写迭代器的方法。它也适用于您自己有权访问的自定义类型或容器。
// How to write an STL iterator in C++
// this example is specific to the MFC CArray<T, U> type, but
// it can be modified to work for any type, note that the
// templates will need to be changed for other containers
#include <iterator>
#include <mfc stuff...>
template<typename T, typename U>
class CArrayForwardIt : public std::iterator<std::forward_iterator_tag, std::ptrdiff_t, U, U*, U&>
{
// the names used in this class are described in this list
// using iterator_category = std::forward_iterator_tag;
// using difference_type = std::ptrdiff_t;
// using value_type = U;
// using pointer = U*;
// using reference = U&;
public:
CArrayForwardIt(CArray<T, U> &array_ref, const std::size_t index)
: m_array_ref(array_ref)
, m_index(index)
{
}
// the only way I could get this to work was to make the return type
// an explicit U&, I don't know why this is required, as using
// reference operator*() const did not seem to work
U& operator*() const
{
if(m_index < m_array_ref.GetCount())
{
return m_array_ref[m_index];
}
else
{
throw std::out_of_range("Out of range Exception!");
}
}
CArrayForwardIt& operator++()
{
++ m_index;
return *this;
}
CArrayForwardIt operator++(int)
{
CForwardArrayIt tmp(*this);
++(*this);
}
friend bool operator==(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
{
if(&(lhs.m_array_ref) == &(rhs.m_array_ref))
{
return lhs.m_index == rhs.m_index;
}
return false;
}
friend bool operator!=(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
{
return !(lhs == rhs);
}
private:
std::size_t m_index;
CArray<T, U> &m_array_ref;
};
template<typename T, typename U>
auto begin(CArray<T, U> &array)
{
return CArrayForwardIt<T, U>(array, 0);
}
template<typename T, typename U>
auto end(CArray<T, U> &array)
{
return CArrayForwardIt<T, U>(array, array.GetCount());
}
int main()
{
CArray<int, int> array;
// do stuff to array
// construct vector from elements of array in one line
std::vector<int> vector(begin(array), end(array));
// also works with other STL algorithms
}
请注意我对 U& operator*
的评论,当写成 reference operator*
时会产生一些编译器错误,这可能是 Visual Studio 编译器错误。我不确定。
我建议尽管这种方法更难实现(但当你知道如何去做时就不多了)它的优点是不使用原始指针,这意味着迭代器函数可以提供适当的异常抛出语句当试图进行非法操作时。例如,当迭代器已经结束时递增迭代器。
有用的参考资料:
为了完整起见,这里是使用原始指针的更简单的解决方案。
template<typename T, typename U>
auto begin(CArray<T, U> &array)
{
return &(array[0]);
}
template<typename T, typename U>
auto end(CArray<T, U> &array)
{
// get address of last element then increment
// pointer by 1 such that it points to a memory
// address beyond the last element. only works for
// storage containers where higher index elements
// are guaranteed to be at higher value memory
// addresses
if(array.GetCount() > 0)
{
return &(array[array.GetCount() - 1]) + 1;
}
else
{
return &(array[0]) + 1;
}
}
您可以按照其他答案中演示的方式使用它们,但是也有一种方法可以在没有 begin
和 end
函数的情况下使用 STL 向量:
CArray<int, int> array; // ... do something to array
std::vector<int> vec(&array[0], &(array[array.GetCount() - 1]) + 1);
// note only works if elements guaranteed to be in continuous
// packed memory locations
但它也适用于 begin
和 end
,后者更好
std::vector<int> vec(begin(array), end(array));
这个问题的标题曾经是:与 return 从开始和结束函数中获取原始指针相比,创建迭代器 class 有实际优势吗?
最近我一直在研究使用 MFC 和 objects 的代码库,例如 CArray<T, U>
.
已编写的部分新代码使用了 STL 和 <algorithm>
库。
例如
CArray<int int> carray;
carray // do stuff
std::vector<int> stlvector(begin(carray), end(carray));
stlvector.dostuff() // do stuff
我最近问了一个 question 关于为 class 创建迭代器的问题,比如 CArray
,我无权访问。
我现在对此有一些进一步的疑问。第一题可以查到here。这是我的第二个问题:
begin
和end
函数 return 应该是原始指针还是迭代器?
在上面的链接问题中,提供了一个示例作为 return 原始指针的答案。这个答案与我使用的实现非常相似。
template<typename T, typename U>
auto begin(const CArray<T, U> &array>)
{
return &array[0];
}
template<typename T, typename U>
auto end(const CArray<T, U> &array>)
{
return (&array[array.GetCount() - 1]) + 1;
}
这些函数return 原始指针。但是我试图实现一个迭代器解决方案。到目前为止我还没有成功。
我在研究中使用的主要参考资料可以在这里找到:
第一次尝试
这是我第一次尝试寻找解决方案。
你可以玩这个代码here。
#include <iostream>
#include <iterator>
#include <algorithm>
template <typename U>
class CArrayForwardIt
{
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = U;
using pointer = U*;
using reference = U&;
public:
CArrayForwardIt(pointer ptr)
: m_ptr(ptr)
{
}
// = default?
//CArrayForwardIt(CArrayForwardIt<U> other)
// : m_ptr(ptr)
// {
// }
reference operator*() const
{
return *m_ptr;
}
// what does this do, don't understand why operator-> is needed
// or why it returns a U* type
pointer operator->()
{
return m_ptr;
}
CArrayForwardIt& operator++()
{
++ m_ptr;
return *this;
}
CArrayForwardIt operator++(int)
{
CArrayForwardIt tmp(*this);
++ (*this);
return tmp;
}
friend bool operator==(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
{
return lhs.m_ptr == rhs.m_ptr;
}
friend bool operator!=(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
{
return !(lhs == rhs);
}
private:
pointer m_ptr;
};
template<typename T, typename U>
auto begin(const CArray<T, U> &array)
{
return CArrayForwardIt<U>(&array[0]);
}
template<typename T, typename U>
auto end(const CArray<T, U> &array)
{
return CArrayForwardIt<U>((&array[array.GetCount() - 1]) + 1);
}
int main()
{
CArray<int, int> c;
// do something to c
std::vector<int> v(begin(c), end(c));
return 0;
}
这是我尝试编译它时发生的情况(使用 Visual Studio 2019 Pro)。
no instance of constructor "std::vector<_Ty, _Alloc>::vector [with _Ty=int, _Alloc=std::allocator<int>]" matches argument list
'<function-style-cast>': cannot convert from 'contt TYPE*' to 'std::CArrayForwardIt<U>'
'std::vector<int, std::allocator<int>>::vector(std::vector<int, std::allocator<int>> &&, const _Alloc &) noexcept(<expr>)': cannot convert from argument 1 from 'void' to 'const unsigned int'
我对gcc比较熟悉,对如何理解这一点知之甚少
第二次尝试
我又做了两次尝试,但它们非常相似。
一个是将我的 class CArrayForwardIt
更改为从 iterator<std::forward_iterator_tag, std::ptrdiff_t, U, U*, U&>
继承,并删除 class 顶部的 using...
行。这似乎并没有让我更接近解决方案。
此外,我查看了 std::vector
的构造函数定义。参见 here。
我在这里可能有误解,但看起来 std::vector
需要一个 InputIt
类型的参数。
因此我尝试将我的 class 改成这样:
#include <iostream>
#include <iterator>
#include <algorithm>
template <typename U>
class forward_iterator
{
using iterator_category = std::forward_iterator_tag;
using difference_type = std::ptrdiff_t;
using value_type = U;
using pointer = U*;
using reference = U&;
public:
forward_iterator(pointer ptr)
: m_ptr(ptr)
{
}
// = default?
//forward_iterator(forward_iterator<U> other)
// : m_ptr(ptr)
// {
// }
reference operator*() const
{
return *m_ptr;
}
// what does this do, don't understand why operator-> is needed
// or why it returns a U* type
pointer operator->()
{
return m_ptr;
}
forward_iterator& operator++()
{
++ m_ptr;
return *this;
}
forward_iterator operator++(int)
{
forward_iterator tmp(*this);
++ (*this);
return tmp;
}
friend bool operator==(const forward_iterator& lhs, const forward_iterator& rhs)
{
return lhs.m_ptr == rhs.m_ptr;
}
friend bool operator!=(const forward_iterator& lhs, const forward_iterator& rhs)
{
return !(lhs == rhs);
}
private:
pointer m_ptr;
};
template<typename T, typename U>
auto begin(const CArray<T, U> &array)
{
return forward_iterator<U>(&array[0]);
}
template<typename T, typename U>
auto end(const CArray<T, U> &array)
{
return forward_iterator<U>((&array[array.GetCount() - 1]) + 1);
}
int main()
{
CArray<int, int> c;
// do something to c
std::vector<int> v(begin(c), end(c));
return 0;
}
这也许不足为奇,也没有编译。在这一点上,我变得困惑。 std::vector
似乎需要 InputIt
类型,forward_iterator
应该适用,但重新定义 forward_iterator
似乎没有意义,即使我写这个class 在命名空间之外 std
.
问题
我相当确定应该有一种方法可以为 MFC CArray
编写迭代器 class,它可以由 begin
和 [=] 编辑 return 20=] 函数。但是,我对如何执行此操作感到困惑。
关于编写工作解决方案的问题,我开始怀疑这样做是否有任何实际优势?我想做的事情有意义吗?原始指针解决方案显然有效,那么投入精力编写基于迭代器的解决方案有什么好处吗?例如,迭代器解决方案能否提供更复杂的边界检查?
自从我成功完成这项工作后,我想 post 一个解决方案,希望我在转录它时不会犯太多错误。
上面代码片段中没有显示的一件事是,所有这些 class 和函数定义都存在于命名空间 std
中。我之前 post 对此提出了另一个问题,并被告知这些东西不应该在命名空间 std
内。更正这个似乎解决了一些问题,使解决方案更近了一步。
你可以找到那个问题here。
这是我目前所掌握的:这是为程序员无法访问的外部 class 编写迭代器的方法。它也适用于您自己有权访问的自定义类型或容器。
// How to write an STL iterator in C++
// this example is specific to the MFC CArray<T, U> type, but
// it can be modified to work for any type, note that the
// templates will need to be changed for other containers
#include <iterator>
#include <mfc stuff...>
template<typename T, typename U>
class CArrayForwardIt : public std::iterator<std::forward_iterator_tag, std::ptrdiff_t, U, U*, U&>
{
// the names used in this class are described in this list
// using iterator_category = std::forward_iterator_tag;
// using difference_type = std::ptrdiff_t;
// using value_type = U;
// using pointer = U*;
// using reference = U&;
public:
CArrayForwardIt(CArray<T, U> &array_ref, const std::size_t index)
: m_array_ref(array_ref)
, m_index(index)
{
}
// the only way I could get this to work was to make the return type
// an explicit U&, I don't know why this is required, as using
// reference operator*() const did not seem to work
U& operator*() const
{
if(m_index < m_array_ref.GetCount())
{
return m_array_ref[m_index];
}
else
{
throw std::out_of_range("Out of range Exception!");
}
}
CArrayForwardIt& operator++()
{
++ m_index;
return *this;
}
CArrayForwardIt operator++(int)
{
CForwardArrayIt tmp(*this);
++(*this);
}
friend bool operator==(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
{
if(&(lhs.m_array_ref) == &(rhs.m_array_ref))
{
return lhs.m_index == rhs.m_index;
}
return false;
}
friend bool operator!=(const CArrayForwardIt& lhs, const CArrayForwardIt& rhs)
{
return !(lhs == rhs);
}
private:
std::size_t m_index;
CArray<T, U> &m_array_ref;
};
template<typename T, typename U>
auto begin(CArray<T, U> &array)
{
return CArrayForwardIt<T, U>(array, 0);
}
template<typename T, typename U>
auto end(CArray<T, U> &array)
{
return CArrayForwardIt<T, U>(array, array.GetCount());
}
int main()
{
CArray<int, int> array;
// do stuff to array
// construct vector from elements of array in one line
std::vector<int> vector(begin(array), end(array));
// also works with other STL algorithms
}
请注意我对 U& operator*
的评论,当写成 reference operator*
时会产生一些编译器错误,这可能是 Visual Studio 编译器错误。我不确定。
我建议尽管这种方法更难实现(但当你知道如何去做时就不多了)它的优点是不使用原始指针,这意味着迭代器函数可以提供适当的异常抛出语句当试图进行非法操作时。例如,当迭代器已经结束时递增迭代器。
有用的参考资料:
为了完整起见,这里是使用原始指针的更简单的解决方案。
template<typename T, typename U>
auto begin(CArray<T, U> &array)
{
return &(array[0]);
}
template<typename T, typename U>
auto end(CArray<T, U> &array)
{
// get address of last element then increment
// pointer by 1 such that it points to a memory
// address beyond the last element. only works for
// storage containers where higher index elements
// are guaranteed to be at higher value memory
// addresses
if(array.GetCount() > 0)
{
return &(array[array.GetCount() - 1]) + 1;
}
else
{
return &(array[0]) + 1;
}
}
您可以按照其他答案中演示的方式使用它们,但是也有一种方法可以在没有 begin
和 end
函数的情况下使用 STL 向量:
CArray<int, int> array; // ... do something to array
std::vector<int> vec(&array[0], &(array[array.GetCount() - 1]) + 1);
// note only works if elements guaranteed to be in continuous
// packed memory locations
但它也适用于 begin
和 end
,后者更好
std::vector<int> vec(begin(array), end(array));