C++ 利用容器适配器,仿函数实现栈,队列,优先级队列(堆),反向迭代器,deque的介绍与底层

C++ 利用容器适配器,仿函数实现栈,队列,优先级队列【堆】,反向迭代器,deque的介绍与底层

• 一.容器适配器的介绍
• 二.利用容器适配器实现栈和队列
• • 1.stack
  • 2.queue
• 三.仿函数介绍
• • 1.什么是仿函数
  • 2.仿函数的使用
  • 3.函数指针的使用
  • • 1.函数指针的用处
    • 2.利用函数指针完成回调
    • 3.利用仿函数完成回调
  • 4.仿函数的玩法
  • • 1.取出Key/Key-Value模型中的Key
    • 2.自定义排序
• 四.利用容器适配器和仿函数实现优先级队列
• 五.利用正向迭代器作为适配器实现反向迭代器
• • 1.STL库里面的实现逻辑
  • • 1.rbegin和rend的实现
  • 2.反向迭代器的实现
  • 3.画图模拟反向迭代器具体的遍历流程
  • • 1.vector
    • 2.list
  • 4.具体实现
  • 5.对于list的适用
  • 6.对于vector的适用
  • 7.const_reverse_iterator的实现
  • 8.验证
  • • 1.list
    • 2.vector
• 六.deque的介绍
• 七.deque的底层原理

一.容器适配器的介绍

适配器是一种设计模式(所谓的设计模式就是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结,是很多大佬的编程的过程中总结下来的经验,类似于”武林秘籍”),

该种模式是将一个类的接口转换成客户希望的另外一个接口。

我们来看一下STL库中stack的源码,了解一下容器适配器模式到底是什么

下面就让我们借助容器适配器来实现一下栈和队列吧

实现之后大家就会对容器适配器模式有更加深刻的理解

二.利用容器适配器实现栈和队列

1.stack

#pragma once
//容器适配器:vector可以,list可以,deque也可以,库里面默认使用deque
namespace wzs
{
    template<class T, class Container = deque>
    class stack
    {
    public:
        //直接使用编译器默认生成的默认成员函数即可
        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_back();
        }

        T& top()
        {
            return _con.back();
        }

        const T& top()const
        {
            return _con.back();
        }

        size_t size()const
        {
            return _con.size();
        }

        bool empty()const
        {
            return _con.empty();
        }

    private:
        Container _con;
    };
}

可见,非常的easy

就是容器的复用而已

对于stack而言

它的适配器必须满足:

push_back,pop_back,back,size,empty这几个接口

因此stack的适配器可以是

vector

list

deque中的任何一个

验证完毕

2.queue

#pragma once
//容器适配器:list可以,deque也可以,库里面是deque,不过vector不可以,因为vector没有头删这个接口
namespace wzs
{
    template<class T, class Container = deque>
    class queue
    {

    public:
        //使用编译器默认生成的默认成员函数即可

        void push(const T& x)
        {
            _con.push_back(x);
        }

        void pop()
        {
            _con.pop_front();
        }

        T& back()
        {
            return _con.back();
        }

        const T& back()const
        {
            return _con.back();
        }

        T& front()
        {
            return _con.front();
        }

        const T& front()const
        {
            return _con.front();
        }

        size_t size()const
        {
            return _con.size();
        }

        bool empty()const
        {
            return _con.empty();
        }

    private:

        Container _con;

    };
}

可见,非常的easy

就是容器的复用而已

对于queue而言

它的适配器必须满足:

push_back,pop_front,back,front,size,empty这几个接口

因此stack的适配器可以是

list

deque中的任何一个

而vector因为没有pop_front这个接口,因此不能作为queue的适配器

验证完毕

三.仿函数介绍

1.什么是仿函数

仿函数,又叫做函数对象,它是一个类

只不过这个类重载了operator()这个运算符,使得这个类实例化出的对象在调用operator()这个函数时使用起来特别像一个函数,

也就是说这个类实例化出的对象能够像函数一样调用,因此这个类被称为仿函数

下面给大家演示一下

这是比较两个T类型的大小

只要一个类重载了operator(),这个类就是一个仿函数类

这个类实例化出的对象就能像函数一样进行调用

2.仿函数的使用

算法库里面的sort函数就使用了仿函数

默认情况下sort是排升序的

如果我们想要排降序呢?

就要用到仿函数了

我们来演示一下,顺便学习一下仿函数的语法和特性

默认排升序

排降序

sort的第三个参数要求传入仿函数对象,所以可以这样做

其实我们也可以自己实现一个仿函数

一般来说仿函数写出来就是为了给外界用的,所以定义成class的话要加public访问限定符调整成公有成员

不过也可以直接用struct定义这个类,毕竟struct定义的类的访问限定符默认就是public

template
struct greater
{
    bool operator()(const T& a, const T& b)
    {
        return a > b;
    }
};

其实也可以直接传匿名对象,省下起名字了

3.函数指针的使用

1.函数指针的用处

可见仿函数是非常多功能的,那么它的用处是什么呢?

为什么C++创始人要设计仿函数这一语法呢?

仿函数是为了替代C语言当中的函数指针而出现的

我们知道函数指针是用来完成回调的,例如C语言库中的qsort函数

关于回调函数大家可以看我的这篇博客:征服C语言指针系列(3)

这里的比较规则就是由cmp这个函数指针来完成的

在学习堆的时候,我们曾经借助于函数指针来完成回调函数,实现无需修改具体函数的实现细节来完成大小堆的切换

数据结构-堆的实现及应用(堆排序和TOP-K问题)

2.利用函数指针完成回调

下面我们来演示一下使用函数指针完成回调

//返回a是否小于b
bool less1(int a, int b)
{
	return a < b;
}

class A
{
public:
	A(bool (*p)(int,int))
		:_p(p)
	{}

	//返回两个数中更小的那个数
	int smaller(int left, int right)
	{
		if (_p(left, right)) return left;
		else return right;
	}

private:
	bool (*_p)(int, int);
};

int main()
{
	bool (*ptr)(int, int) = less1;
	A aa(ptr);
	cout << aa.smaller(1, 7) << endl;
	cout << aa.smaller(2, 5) << endl;
	return 0;
}

需要注意的是:

1. 因为类A在回调less1这个函数时只能在类的成员函数进行

   而且可能类A的很多成员函数都需要回调less1这个函数,因此在类A当中增加了一个函数指针类型的成员变量,这个函数指针的参数类型和顺序以及返回值都需要跟less1这个函数一样

2.上面那个代码只能完成int和int的比较功能,无法完成string和string等等诸多类型的比较

并不符合泛型编程的思想

3.less1这个函数比较简单,因此这个函数指针并不复杂,可是那些很复杂的函数和类,如果使用函数指针的话…结果就让人很难受了

3.利用仿函数完成回调

下面我们来演示一下仿函数完成回调

template
class Less
{
public:
	bool operator()(const T& a, const T& b)
	{
		return a < b;
	}
};

template 
class A
{
public:
	//返回两个元素中更小的那个元素
	const T& smaller(const T& left, const T& right)
	{
		if (_cmp(left, right)) return left;
		else return right;
	}
private:
	Compare _cmp;
};

int main()
{
	//注意:这里要往类模板的参数列表中传入实参
	//应该传入类型,而不是对象!!
	A<string, Less> aa;
	cout << aa.smaller("abc", "wzs") << endl;
	A<int, Less> ab;
	cout << ab.smaller(1, 8) << endl;
	return 0;
}

这样就既符合泛型编程的思想,使用起来也非常的好用了

4.仿函数的玩法

当然,仿函数的玩法是很多的,

1.取出Key/Key-Value模型中的Key

比如下面的这个例子:

这是取出一个键或者键值对当中的键

我们之前学过的二叉搜索树当中的Key模型和Key-Value模型就可以这样玩

这里是通过函数重载和类模板的缺省参数完成的

2.自定义排序

我们要实现一个比较算法,对不同的商品按照价格分别升序和降序排序

struct Goods
{
    string _name;//名称
    double _price;//价格
    int _evaluate;//评价
    Goods(const char* str, double price, int evaluate)
        :_name(str)
        , _price(price)
        , _evaluate(evaluate)
    {}
};

//按照价格升序
struct ComparePriceLess
{
    bool operator()(const Goods& left, const Goods& right)
    {
        return left._price < right._price;
    }
};

//按照价格降序
struct ComparePriceGreater
{
    bool operator()(const Goods& left, const Goods& right)
    {
        return left._price > right._price;
    }
};

int main()
{
    vector v = { { "苹果", 2.5, 5 }, { "香蕉", 3.2, 4 }, { "橙子", 2.9, 3 }, { "菠萝", 1.5, 4 } };
    sort(v.begin(),v.end(), ComparePriceLess());
    for (auto& e : v)
    {
        cout << "商品名称: " << e._name << " 价格 :" << e._price << " 评价:" << e._evaluate << endl;
    }
    cout << endl;
    sort(v.begin(), v.end(), ComparePriceGreater());
    for (auto& e : v)
    {
        cout << "商品名称: " << e._name << " 价格 :" << e._price << " 评价:" << e._evaluate << endl;
    }
    cout << endl;
    return 0;
}

这样就可以按照我们想要的方式自定义排序规则进行排序了

当然,仿函数也有一个缺点:使用仿函数完成回调必须要定义出一个类来,有点大材小用的感觉

因此我们以后会介绍一个C++11新增的语法:lambda表达式,它可以在这种情况下替代仿函数

四.利用容器适配器和仿函数实现优先级队列

优先级队列其实就是堆,

关于堆的知识,实现,应用,大家可以看我的这篇博客,里面有详细的介绍:数据结构-堆的实现及应用(堆排序和TOP-K问题)

头文件是

它也可以用容器适配器来实现

默认是大堆,要想实现小堆的话:第三个参数仿函数传入greater类

容器适配器:vector可以,deque也可以,库里面是vector

因为要能够支持下标随机访问(也就是operator[]),而且vector的operator[]的速度远高于deque

#pragma once
//priority_queue的头文件是queue
//priority_queue默认是大堆
//要想实现小堆的话:第三个参数仿函数传入greator类
//容器适配器:vector可以,deque也可以,库里面是vector
//大堆:父亲大于孩子
//小堆:父亲小于孩子
namespace wzs
{
    template <class T, class Container = vector, class Compare = less >
    class priority_queue
    {
    public:
        //使用编译器默认生成的默认成员函数即可
        priority_queue() = default;//C++11新语法:强制生成默认构造
        template 
		//迭代器区间构造
        priority_queue(InputIterator first, InputIterator last)
            :_con(first, last)
        {
            //先调一下迭代器区间构造,构造适配器对象_con
            //然后建堆即可
            //注意:向上调整算法建堆的时间复杂度O(N*logN)
            //向下调整算法建堆的时间复杂度O(N)
            //因此这里向下建堆
            for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
            {
                adjust_down(i);
            }
        }

        bool empty() const
        {
            return _con.empty();
        }

        size_t size() const
        {
            return _con.size();
        }

        const T& top() const
        {
            return _con.front();
        }

        T& top()
        {
            return _con.front();
        }

        //向上调整算法
        void adjust_up(int child)
        {
            int parent = (child - 1) / 2;
            while (child > 0)
            {
                if (_cmp(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }

        void push(const T& x)
        {
            //先插入数据,然后向上调整
            _con.push_back(x);
            adjust_up(_con.size() - 1);
        }

        //向下调整算法
        void adjust_down(int parent)
        {
            int child = 2 * parent + 1;//默认跟左孩子比较
            int n = _con.size();
            while (child < n)
            {
                //实际要跟右孩子比较
                if (child + 1 < n && _cmp(_con[child], _con[child + 1]))
                {
                    child++;
                }
                if (_cmp(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = 2 * parent + 1;
                }
                else
                {
                    break;
                }
            }
        }

        void pop()
        {
            //先交换第一个和最后一个数据
            swap(_con[0], _con[_con.size() - 1]);
            //然后删除最后一个数据
            _con.pop_back();
            //最后向下调整
            adjust_down(0);
        }

    private:

        Container _con;

        Compare _cmp;

    };
    //仿函数greater
    template
    struct greater
    {
        bool operator()(const T& a, const T& b)
        {
            return a > b;
        }
    };
};

注意:

建小堆传入仿函数时:

因为优先级队列的类模板中规定仿函数传入类

因此不能传入对象,而且缺省参数也不支持跳着传

priority_queue<int, greater> heap;//err:仿函数是第三个参数,只有在第二个参数传了之后才能传第3个参数
priority_queue<int,vector, greater()> heap;//err:仿函数是类模板,必须传入类型,不能传入对象
priority_queue<int, vector, greater> heap;//yes,正确的传法

五.利用正向迭代器作为适配器实现反向迭代器

下面我们来通过适配器的知识借助vector和list的正向迭代器实现它们的反向迭代器

首先要说明的是,反向迭代器是这么使用的

会反向打印这个容器中的数据

这里以vector为例,对于其他支持迭代器的容器来说也是这样的

1.STL库里面的实现逻辑

1.rbegin和rend的实现

2.反向迭代器的实现

3.画图模拟反向迭代器具体的遍历流程

1.vector

2.list

可见STL大佬的实现体现出了一种对称美(rbegin就是end,rend就是begin)

下面我们就来实现一下

4.具体实现

// 适配器 -- 复用
template
struct Reverse_iterator
{
	typedef Reverse_iterator Self;
	//构造函数
	Reverse_iterator(Iterator it)
		:_it(it)
	{}

	Iterator _it;
	Ref operator*()
	{
		Iterator tmp(_it);
		return *(--tmp);
	}
	Ptr operator->()
	{
		return &(operator*());
	}

	//前置++
	Self& operator++()
	{
		--_it;
		return *this;
	}

	//前置--
	Self& operator--()
	{
		++_it;
		return *this;
	}

	//后置++
	Self& operator++(int)
	{
		Self tmp(*this);
		--_it;
		return tmp;
	}

	//后置--
	Self& operator--(int)
	{
		Self tmp(*this);
		++_it;
		return tmp;
	}

	bool operator==(const Self& s)
	{
		return _it == s._it;
	}
	bool operator!=(const Self& s)
	{
		return _it != s._it;
	}
};

5.对于list的适用

template
class list
{
	typedef list_node Node;
public:
	typedef __list_iterator iterator;

	typedef __list_iterator const_iterator;

	typedef Reverse_iterator reverse_iterator;


	iterator begin()
	{
		return iterator(_head->_next);
	}

	iterator end()
	{
		return iterator(_head);
	}

	const_iterator begin() const
	{
		return const_iterator(_head->_next);
	}

	const_iterator end() const
	{
		return const_iterator(_head);
	}

	reverse_iterator rbegin()
	{
		return reverse_iterator(end());
	}

	reverse_iterator rend()
	{
		return reverse_iterator(begin());
	}

	//其他成员....无需改动
}

6.对于vector的适用

template
class vector
{
public:
	typedef T* iterator;
	typedef const T* const_iterator;
	typedef Reverse_iterator reverse_iterator;

	/
	// 迭代器相关
	iterator begin()
	{
		return _start;
	}

	iterator end()
	{
		return _finish;
	}

	const_iterator begin() const
	{
		return _start;
	}

	const_iterator end() const
	{
		return _finish;
	}

	reverse_iterator rbegin()
	{
		return reverse_iterator(end());
	}

	reverse_iterator rend()
	{
		return reverse_iterator(begin());
	}
	其他成员.... 无需改动

7.const_reverse_iterator的实现

关于const_reverse_iterator的实现,我们需要实现支持使用普通的reverse_iterator来构造const_reverse_iterator

因此我们需要增加一个模板参数T

template
struct Reverse_iterator
{
	typedef Reverse_iterator Self;
	typedef Reverse_iterator reverse_iterator;
	
	Iterator cur;
	Reverse_iterator(Iterator it)
		:cur(it)
	{}

	//支持reverse_iterator向const_reverse_iterator的构造
	Reverse_iterator(const reverse_iterator& it)
		:cur(it.cur)
	{}

	//运算符重载都是一样的
};

因为const迭代器中const保护迭代器指向的内容不被修改的功能是由解引用操作的返回值类型即Ref和Ptr所决定的,

因此可以在list和vector当中这么定义const_reverse_iterator

这份代码在list和vector当中都是一样的

typedef Reverse_iterator const_reverse_iterator;

const_reverse_iterator rbegin() const
{
	return const_reverse_iterator(end());
}

const_reverse_iterator rend() const
{
	return const_reverse_iterator(begin());
}

8.验证

1.list

class AA
{
public:
	AA(int a = 1,int b = 2)
		:_a(a)
		,_b(b)
	{}
	int _a;
	int _b;
};

void TestReverseIterator()
{
	list lt;
	int a[] = { 1,2,3,4,5,6,7,8,9,10 };
	for (auto& e : a)
	{
		lt.push_back(e);
	}
	list::reverse_iterator it = lt.rbegin();
	while (it != lt.rend())
	{
		*it -= 5;//可以修改
		cout << *it << " ";
		++it;
	}
	cout<<endl;
	list lt2;
	for (auto& e : a)
	{
		lt2.push_back(AA(e,e));
	}
	list::const_reverse_iterator it2 = lt2.rbegin();
	while (it2 != lt2.rend())
	{
		//it2->_b -= 2;//不可修改
		cout <_a << ":" <_b << endl;
		++it2;
	}

}

验证成功

2.vector

void TestReverseIterator2()
{
	vector v;
	int a[] = { 1,2,3,4,5,6,7,8,9,10 };
	for (auto& e : a)
	{
		v.push_back(e);
	}
	vector::reverse_iterator it = v.rbegin();
	while (it != v.rend())
	{
		*it -= 5;//可以修改
		cout << *it << " ";
		++it;
	}
	cout<<endl;
	vector v2;
	for (auto& e : a)
	{
		v2.push_back(AA(e,e));
	}
	vector::const_reverse_iterator it2 = v2.rbegin();
	while (it2 != v2.rend())
	{
		//it2->_b -= 2;//不可修改
		cout <_a << ":" <_b << endl;
		++it2;
	}
}

验证成功

六.deque的介绍

deque:双端队列,名字叫做双端队列,但是跟队列没有任何关系

七.deque的底层原理

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的

deque的底层是一个指针数组

deque为了维护其“整体连续”以及随机访问的假象，所以它的迭代器就比较复杂了

通过保证每一个tmp数组的大小都是一样的,这样就能实现O(1)的operator[]了,

假设每个tmp数组的大小都是n,要查找下标为pos的元素 那么就是第pos/n个tmp数组的第pos%n个元素

对于deque来说我们了解即可,因为deque无法取代vector和list

实际并不常用

以上就是C++ 利用容器适配器,仿函数实现栈,队列,优先级队列(堆),反向迭代器,deque的介绍与底层的全部内容,希望能对大家有所帮助!