您现在的位置是:首页 >其他 >STL常用梳理——STACK、QUEUE网站首页其他

STL常用梳理——STACK、QUEUE

Code_uu 2024-06-10 00:00:02
简介STL常用梳理——STACK、QUEUE

1、List

STL list 容器介绍

STL list 容器,又称双向链表容器,即该容器的底层是以双向链表的形式实现的。这意味着,list 容器中的元素可以分散存储在内存空间里,而不是必须存储在一整块连续的内存空间中。
在这里插入图片描述
可以看到,list 容器中各个元素的前后顺序是靠指针来维系的,每个元素都配备了 2 个指针,分别指向它的前一个元素和后一个元素。其中第一个元素的前向指针总为 null,因为它前面没有元素;同样,尾部元素的后向指针也总为 null。
基于这样的存储结构,list 容器具有一些其它容器(array、vector 和 deque)所不具备的优势,即它可以在序列已知的任何位置快速插入或删除元素(时间复杂度为O(1))。并且在 list 容器中移动元素,也比其它容器的效率高。
使用 list 容器的缺点是,它不能像 array 和 vector 那样,通过位置直接访问元素。

list使用

1、list构造

构造函数接口介绍
list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素
list()构造空的list
list (const list& x)拷贝构造函数
list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list
 	list<int> l1;                         // 构造空的l1
    list<int> l2(4, 100);                 // l2中放4个值为100的元素
    list<int> l3(l2.begin(), l2.end());  // 用l2的[begin(), end())左闭右开的区间构造l3
    list<int> l4(l3);                    // 用l3拷贝构造l4

2、list迭代器

begin + end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下个位置的reverse_iterator,即begin位置
void PrintList(const list<int>& l)
{
    // 注意这里调用的是list的 begin() const,返回list的const_iterator对象
    for (list<int>::const_iterator it = l.begin(); it != l.end(); ++it)
    {
        cout << *it << " ";
       
    }

    cout << endl;
}

void TestList2()
{
    int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };
    list<int> l(array, array + sizeof(array) / sizeof(array[0]));
    // 使用正向迭代器正向list中的元素
    // list<int>::iterator it = l.begin();   // C++98中语法
    auto it = l.begin();                     // C++11之后推荐写法
    while (it != l.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

    // 使用反向迭代器逆向打印list中的元素
    // list<int>::reverse_iterator rit = l.rbegin();
    auto rit = l.rbegin();
    while (rit != l.rend())
    {
        cout << *rit << " ";
        ++rit;
    }
    cout << endl;
}

3、增删查改
在这里插入图片描述

int main()
{
	
	int arr[] = {0 };
	int n = sizeof(arr) / sizeof(arr[0]);
	list<int> lt(arr, arr + n);
	list<int> list(10,1);//使用10个1初始化list

	lt.push_front(2);
	PrintList(lt);

	lt.push_back(1);
	PrintList(lt);
	
	lt.pop_back();
	PrintList(lt);

	lt.pop_front();
	PrintList(lt);

	lt.insert(lt.begin()++, 2);
	PrintList(lt);

	lt.erase(lt.begin());
	PrintList(lt);

	lt.swap(list);
	PrintList(lt);

	lt.clear();
	PrintList(lt);

	return 0;
}

运行结果参考:
在这里插入图片描述

2、适配器介绍

适配器就是接口,对容器、迭代器、算法进行包装,但其实质还是容器、迭代器和算法,只是不依赖于具体的标准容器、迭代器和算法类型。概念源于设计模式中的适配器模式:将一个类的接口转化为另一个类的接口,使原本不兼容而不能合作的类,可以一起运作。

容器适配器可以理解为容器的模板,迭代器适配器可理解为迭代器的模板,算法适配器可理解为算法的模板。
在数据结构中就有着对于栈、队列的结构实现,有物理结构连续的(数组结构),不连续的(链表结构)。底层结构就决定了效率问题。对于OPP语言就有些许不方便使用。

3、Deque容器

特定的库可能以不同的方式实现deque,通常是某种形式的动态数组。但在任何情况下,它们都允许通过随机访问迭代器直接访问单个元素,并根据需要通过扩展和收缩容器来自动处理存储。因此,它们提供了类似于vector的功能,但在序列的开始部分,而不仅仅是在序列的末尾,都可以有效地插入和删除元素。但是,与vector不同,deque不能保证将其所有元素存储在连续的存储位置:通过偏移指向另一个元素的指针来访问deque中的元素会导致未定义的行为。vector和deque都提供了非常相似的接口,可以用于类似的目的,但两者在内部的工作方式却大不相同:vector使用单个数组,偶尔需要为增长重新分配,而deque的元素可以分散在不同的存储块中,容器内部保留必要的信息,以便在恒定时间内使用统一的顺序接口(通过迭代器)直接访问其任何元素。因此,deque在内部比vector更复杂,但这使得它们在某些情况下更有效地增长,特别是对于非常长的序列,重新分配变得更加昂贵。对于涉及频繁插入或删除除开始或结束位置以外的元素的操作,deque的性能更差,迭代器和引用的一致性也不如列表和前向列表。

在这里插入图片描述
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际deque类似于一个动态的二维数组
在这里插入图片描述

与vector比较,deque的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是必vector高的。
与list比较,其底层是连续空间,空间利用率比较高,不需要存储额外字段。
但是,deque有一个致命缺陷:不适合遍历,因为在遍历时,deque的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构时,大多数情况下优先考虑vector和list,deque的应用并不多,而目前能看到的一个应用就是,STL用其作为stack和queue的底层数据结构。

Stack、Queue适配器实现

namespace uu

{

#include<deque>
//第一个模板参数是类型,第二个是容器类型
    template<class T, class Con = deque<T>>
    class stack
    {

    public:

        stack()
        {
            
        }

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

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

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

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

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

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

    private:

        Con _c;

    };
  

    template<class T, class Con = deque<T>>
    class queue
    {

    public:

        queue()
        {

        }

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

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

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

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

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

        const T& front()const
        {
            return _c.front();

        }

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

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

    private:

        Con _c;

    };

    void test_queue()
    {
        queue<int> q;
        q.push(1);
        q.push(2);
        q.push(3);
        q.push(4);

        while (!q.empty())
        {
            cout << q.front() << " ";
            q.pop();
        }
        cout << endl;

    }

    void test_stack()
    {
        stack<int> st;
        st.push(1);
        st.push(2);
        st.push(3);
        st.push(4);
        st.push(5);

        cout << st.size() << endl;
        while (!st.empty())
        {
            cout << st.top() << " ";
            st.pop();
        }
        cout << endl;
    }

};

运行结果:
在这里插入图片描述
为什么选择deque作为stack和queue的底层默认容器
stack是一种后进先出的特殊线性数据结构,因此只要具有push_back()和pop_back()操作的线性结构,都可以作为stack的底层容器,比如vector和list都可以;queue是先进先出的特殊线性数据结构,只要具有push_back和pop_front操作的线性结构,都可以作为queue的底层容器,比如list。但是STL中对stack和queue默认选择deque作为其底层容器,主要是因为:

  1. stack和queue不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  2. 在stack中元素增长时,deque比vector的效率高(扩容时不需要搬移大量数据);queue中的元素增长时,deque不仅效率高,而且内存使用率高。

结合了deque的优点,而完美的避开了其缺陷。

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。