iterator adaptor介绍
标签: iterator adaptor介绍 博客 51CTO博客
2023-04-02 18:23:34 139浏览
STL中适配器包括容器适配器、迭代器适配器和仿函数适配器,本文结合源码介绍STL中常见的迭代器适配器(iterator adaptor),以及如何自定义一个iterator adaptor;涉及到的知识点包括adaptor 设计模式,Facade设计模式,CRTP等设计范式;
adaptor & Facade 设计模式介绍
既然是iterator adaptor,那首先简单介绍下adaptor设计模式,Facade设计由于在“自定义迭代器适配器实现”一节中会进行应用,所以在此一并进行介绍,已经熟知的同学可跳过;
adaptor设计模式
适配器模式是将一个类进行封装转换成业务兼容的接口,例如生活中的电源适配器,代码实现通常有继承和委托方式;
adaptor实现接口类,同时继承被适配类Adaptee(被适配者),将NewMethod 转换成 Method方法;
对象委托方式的主要变化为adaptor与Adaptee为聚合关系,即adaptor持有Adaptee的指针或者引用,相比继承方式耦合更小,下文中介绍的iterator adaptor即为委托方式实现;
补充:继承虽然耦合更紧密,但在某些场景下能起到更好的设计效果,如EBO优化和Mixins模式,所以还是需要根据具体的业务场景选择合适的实现方式,并非绝对;
facade设计模式
上图中用户依赖子系统内部各模块的接口,当模块接口发生变化时可能需要多个客户进行修改;同时带来系统构建时依赖关系的复杂;门面模式用于为子系统提供一个统一的门面,将依赖简化;client不直接依赖各个Module;
详细的设计模式读者可以参阅【1】
STL库常见iterator adaptor及实现
STL中提供迭代器适配器如上所示【6】,本文中取常用的两个适配器结合源码进行说明原理;
std::back_insert_iterator
std::vector<int> src {1, 2, 3, 4, 5};
std::vector<int> dst;
std::copy(src.begin(), src.end(), std::back_insert_iterator(dst));
以上代码实现的功能为将src拷贝到dst中,结合源码分析如下:
其中back_insert_iterator 删除了部分实现,保留了相关部分,相信不难理解;front_inserter_iterator实现类似;
std::ostream_iterator
std::vector<int> v {1, 2, 3, 4, 5};
std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ", "));
// output: 1, 2, 3, 4, 5,
以上代码实现对vector的遍历输出,同样源码展开如下:
上述代码中将将所有元素拷贝到std::cout,利用cout进行输出;类似istream_iterator拷贝到std::cin,其他迭代器适配器实现类似。
自定义迭代器及适配器实现
上文中提到不同iterator_adaptor的iterator_category 有所不同,也意味这他们 所适配的迭代器也有所区别,本文先对迭代器及其分类进行介绍;
迭代器及其分类介绍
在使用STL进行业务编码时,常使用的容器和迭代器其实不多,所以对iterator_category 开发者通一般不会涉及,就像std::allocator,但在开发一些基础模板库并且配合STL时对其中原理有所理解能更好的进行开发;
不同的容器具有不同的迭代器类型,可以通过iterator_traits来获取对应的iterator_category:
template<typename C>
typename std::iterator_traits<decltype(std::declval<C>().begin())>::iterator_category
GetCategoryType(C&& c) { return {}; }
void Print(std::random_access_iterator_tag)
{ std::cout << "random_access_iterator_tag" << std::endl; }
void Print(std::bidirectional_iterator_tag)
{ std::cout << "bidirectional_iterator_tag" << std::endl; }
void Print(std::output_iterator_tag)
{ std::cout << "output_iterator_tag" << std::endl; }
void Print(std::forward_iterator_tag)
{ std::cout << "forward_iterator_tag" << std::endl; }
通过调用即可打印不同container的iterator_category如下:
上图中不包含容器适配器,由于容器不是本文的重点,在此不做展开介绍;而不同iterator_category存在继承关系且对应支持的迭代器操作有所不同,源码如下:
struct input_iterator_tag { };
struct output_iterator_tag { };
struct forward_iterator_tag : public input_iterator_tag { };
struct bidirectional_iterator_tag : public forward_iterator_tag { };
struct random_access_iterator_tag : public bidirectional_iterator_tag { };
- 输入迭代器:即读取迭代器值作为输入(只读,解引用返回const引用),支持operator*,operator->,operator++,operator==,operator !=;
input_iterator (C++20)
std::istream_iterator
- 输出迭代器:可迭代器进行赋值(只写),支持operator*,operator++;
对应的部分迭代器适配器的category type
std::ostream_iterator
std::ostreambuf_iterator
std::insert_iterator
std::back_insert_iterator
std::front_insert_iterator
- 前向迭代器:支持读写;
- 双向迭代器:在前向迭代器的基础上增加了operator--;
- 随机访问迭代器:在双向迭代器的基础上增加了operator[],opeator+,operator-,operator+=,operator-=和比较运算等;
iterator facade
实现一个迭代器,每个category的迭代器各自实现一套则显然违反了DRY原则,因此需要提取公共的接口实现并且不引入额外的开销,此处引入facade门面模式提供迭代器归一的接口,目标利用iterator facade 方便的实现迭代器和迭代器适配器;
那么如何设计iterator facade?除了上文中介绍的facade基础,观察现有迭代器需要支持的操作:
根据上文当前容器的iterator_category的种类,将forward_iterator_tag的迭代器接口提取作为公共部分,通过bidirectional和random两个bool变量的组合来构成不同的iterator_facade;【4】
如此便可以实现不同iterator包括forward_iterator_tag,bidirectional_iterator_tag,random_iterator_tag;
其中output_iterator_tag 和 input_iterator 用于迭代器适配器,如ostream_iterator和istream_iterator;
参考【3】实现代码如下:
class IteratorFacadeAccess {
template<typename Derived, typename Value, typename Category,
typename VauleReference, typename Distance, bool IsBidirectional, bool IsRandom>
friend class IteratorFacade;
template<typename VauleReference, typename Iterator, typename Distance = std::ptrdiff_t>
static VauleReference dereference(const Iterator& i, Distance n = 0)
{
return i.dereference(n);
}
template<typename Iterator>
static void increment(Iterator& i)
{
i.increment();
}
template<typename Iterator>
static void decrement(Iterator& i)
{
return i.decrement();
}
template<typename Iterator, typename Distance>
static void advance(Iterator& i, Distance n)
{
return i.advance(n);
}
public:
template<typename Iterator>
static bool equals(const Iterator& il, const Iterator& ir)
{
return il.equals(ir);
}
};
template<typename Derived, typename Value, typename Category,
typename Reference, typename Distance, bool IsBidirectional, bool IsRandom>
class IteratorFacade;
template<typename Derived,typename Value, typename Category,
typename VauleReference, typename Distance>
class IteratorFacade<Derived, Value, Category, VauleReference, Distance, false, false> {
public:
// 命名兼容stl库中的实现
using value_type = typename std::remove_const<Value>::type;
using reference = VauleReference;
using pointer = Value*;
using difference_type = Distance;
using iterator_category= Category;
public:
Derived& operator++()
{
IteratorFacadeAccess::increment(this->asDerived());
return this->asDerived();
}
Derived operator++(int)
{
Derived result(this->asDerived());
IteratorFacadeAccess::increment(this->asDerived());
return result;
}
reference operator*() const
{
return IteratorFacadeAccess::dereference<reference>(this->asDerived());
}
pointer operator->() const
{
return &(IteratorFacadeAccess::dereference<reference>(this->asDerived()));
}
// The Barton-Nackman Trick
friend bool operator == (const IteratorFacade& left, const IteratorFacade& right)
{
return IteratorFacadeAccess::equals(left.asDerived(), right.asDerived());
}
friend bool operator != (const IteratorFacade& left, const IteratorFacade& right)
{
return !(left == right);
}
protected:
Derived& asDerived()
{
return *static_cast<Derived*>(this);
}
Derived const& asDerived() const
{
return *static_cast<Derived const*>(this);
}
};
template<typename Derived,typename Value, typename Category, typename VauleReference, typename Distance>
class IteratorFacade <Derived, Value, Category, VauleReference, Distance, true, false>
: public IteratorFacade <Derived, Value, Category, VauleReference, Distance, false, false> {
public:
Derived& operator--()
{
IteratorFacadeAccess::decrement(this->asDerived());
return this->asDerived();
}
Derived operator--(int)
{
Derived tmp(this->asDerived());
--*this;
return tmp;
}
};
template<typename Derived, typename Value, typename Category, typename VauleReference, typename Distance>
class IteratorFacade <Derived, Value, Category, VauleReference, Distance, true, true>
: public IteratorFacade <Derived, Value, Category, VauleReference, Distance, true, false> {
public:
using BaseType = IteratorFacade <Derived, Value, Category, VauleReference, Distance, true, false>;
using reference = typename BaseType::reference;
using difference_type = typename BaseType::difference_type;
reference operator[](difference_type n)
{
return IteratorFacadeAccess::dereference<reference>(this->asDerived(), n);
}
Derived& operator+=(difference_type n)
{
IteratorFacadeAccess::advance(this->asDerived(), n);
return this->asDerived();
}
Derived& operator+(difference_type n)
{
IteratorFacadeAccess::advance(this->asDerived(), n);
return this->asDerived();
}
Derived& operator-=(difference_type n)
{
IteratorFacadeAccess::advance(this->asDerived(), -n);
return this->asDerived();
}
Derived& operator-(difference_type n)
{
IteratorFacadeAccess::advance(this->asDerived(), -n);
return this->asDerived();
}
};
代码注释中提及的The Barton-Nackman Trick,请参见笔者之前的《The Barton-Nackman Trick介绍》;而IteratorFacadeAccess的存在为了继承类的接口暴露;
指针改造为指针迭代器
这里借助上述实现的iterator_facade将指针转换为指针迭代器:
template<typename T>
class PtrIterator
: public IteratorFacade<PtrIterator<T>, T, std::random_access_iterator_tag, T&, std::ptrdiff_t, true, true> {
friend class IteratorFacadeAccess;
public:
PtrIterator(T* ptr = nullptr) : m_ptr(ptr) {}
private: // IteratorFacadeAccess的存在时为了以下接口不会设置为public,不用对外暴露
T* m_ptr = nullptr;
T& dereference(std::ptrdiff_t n) const
{
return *(m_ptr + n);
}
void increment()
{
m_ptr += 1;
}
void decrement()
{
m_ptr -= 1;
}
void advance(std::ptrdiff_t n)
{
m_ptr += n;
}
bool equals(const PtrIterator& others) const
{
return m_ptr == others.m_ptr;
}
};
PersonalInfo *ptr = new PersonalInfo[10];
PtrIterator<PersonalInfo> iterBegin(ptr);
PtrIterator<PersonalInfo> iterEnd(ptr + 10);
iterBegin->name = "小龙总";
iterBegin->discription = "秀儿";
std::cout << (*iterBegin).name << ":" << (*iterBegin).discription << std::endl;
// 输出 小龙总:如此优秀
实现PtrIterator用户需要知道定义的iterator的类型,由于这里指定random_access_iterator_tag,因此需要实现advance,否则如果使用forward_iterator_tag,则不需要实现advance;
自定义迭代器适配实现
更进一步基于PtrIterator,实现一个迭代器适配器,将PersonalInfo中的两个string进行拼接输出;
template<typename Iterator, typename T>
class PtrIteratorAdaptor
: public IteratorFacade<PtrIteratorAdaptor<Iterator, T>, T, std::output_iterator_tag, T&,
typename std::iterator_traits<Iterator>::difference_type, false, false> {
friend class IteratorFacadeAccess;
public:
PtrIteratorAdaptor(Iterator iterAdaptee): m_iter(iterAdaptee)
{
}
const T& operator*()
{
m_string = (*m_iter).name + "~~~" + (*m_iter).discription;
return m_string;
}
private:
void increment()
{
++m_iter;
}
bool equals(const PtrIteratorAdaptor& others) const
{
return m_iter == others.m_iter;
}
std::string m_string;
Iterator m_iter;
};
int main()
{
PersonalInfo *ptr = new PersonalInfo[5];
PtrIterator<PersonalInfo> iterBegin(ptr);
PtrIterator<PersonalInfo> iterEnd(ptr + 5);
std::for_each(iterBegin, iterEnd, [](auto &Info){
Info.discription = "✿✿ヽ(°▽°)ノ✿";
});
iterBegin[2].name = "小龙总";
iterBegin[2].discription = "秀儿";
PtrIteratorAdaptor<PtrIterator<PersonalInfo>, std::string> adapterBegin(iterBegin);
PtrIteratorAdaptor<PtrIterator<PersonalInfo>, std::string> adapterEnd(iterEnd);
std::copy(adapterBegin, adapterEnd, std::ostream_iterator<std::string>(std::cout, ", "));
return 0;
}
~~~✿✿ヽ(°▽°)ノ✿, ~~~✿✿ヽ(°▽°)ノ✿, 小龙总~~~秀儿, ~~~✿✿ヽ(°▽°)ノ✿, ~~~✿✿ヽ(°▽°)ノ✿,
总结:上述实现总体的思想还是分离变化的过程,抽取公共稳定的部分,依赖于稳定
参考资料
【1】《设计模式- 可复用面向对象软件的基础 》
【2】《STL源码剖析》
【3】C++ templates
【4】boost库
【5】The Barton-Nackman Trick介绍
【6】https://en.cppreference.com/w/cpp/iterator
好博客就要一起分享哦!分享海报
此处可发布评论
评论(0)展开评论
展开评论