欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

简述STL

程序员文章站 2024-02-11 23:37:22
...

一、STL简介

STL(standard template linbrary) 标准模板库，是C++程序设计语言的标准程序库，是一个包罗算法与数据结构的软件框架。
使用了泛型编程的思想，对我们常用的数据结构：顺序表、链表、树、哈希以及常用的查找、排序等算法使用模板进行了封装，而且从运行效率以及内存使用上都基本达到了最优。

二、STL六大组件

简述STL

1.容器

简述STL

解释：对不同数据结构的封装
根据数据在容器中排序特性：关联性容器、序列式容器
序列式容器：按照其加入容器的先后次序，不一定有序
关联式容器：存放的是一个一个键值对，即KV模型，键值对实际上是结构体

1.1 vector

vector具体函数

vector(动态数组),一段连续的空间，当容器中的元素存放满时，扩容具体操作：动态开辟原空间大小两倍的空间，接着将原空间的元素拷贝到新空间中，释放原空间。

1.1.1 vector的基本使用

这里演示部分接口的使用

void Testvector1()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);
    vector<int>::iterator it1 = v1.begin();
    //while (it1 != v1.end())
    //{
    //  cout << *it1 << " ";
    //  ++it1;
    //}
    //cout << endl;
    while (it1 != v1.end())
    {
        if (*it1 % 2 == 0)
        {
            *it1 *= 2;

        }
        cout << *it1 << " ";
        ++it1;
    }
    cout << endl;
    cout << v1.size() << endl;
    cout << v1.capacity() << endl;
}

void Testvector2()
{
    vector<int> v1;
    v1.push_back(1);
    v1.push_back(2);
    v1.push_back(3);
    v1.push_back(4);
    v1.push_back(5);


    //在末尾插入3个4
    //v1.insert(v1.end(), 3, 4);

    //删除区间内元素
    //v1.erase(v1.begin(), v1.begin() + 2);

    // assign()方法是给vector进行赋值
    // 在进行赋值之前，该方法会先将vector中原有的旧元素erase掉
    // 然后再将新元素插入进去
    // 给vector中5个值为10的元素
    //v1.assign(5, 10);

    ////清空元素
    //v1.clear();

    // resize(n，data):将vector中的元素改变到n个
    // 第二个参数可以不用传，默认情况下使用缺省值
    // 将vector中的元素缩小到5个，注意缩小时底层容量不变
    //v1.resize(2);

    //v1.resize(5);

    //大于原数组元素的默认补0
    //v1.resize(10);

    //只扩容不初始化
    //v1.reserve(30);

    cout<<v1.at(2)<<endl;
    vector<int>::iterator it1 = v1.begin();
    while (it1 != v1.end())
    {
        cout << *it1 << " ";
        ++it1;
    }
    cout << endl;

}

1.1.2 模拟实现Myvector.h

template <class T>
class Myvector
{
public:
    typedef T* Iterator;
    typedef const T* ConstIterator;

    Myvector()
        :_start(0)
        , _finish(0)
        , _endofstorage(0)
    {}

    ~Myvector()
    {
        delete[]_start;
        _start = _endofstorage = _finish = 0;
    }

    size_t Capacity()
    {
        return _endofstorage - _start;
    }

    size_t Size()
    {
        return _finish - _start;
    }

    //扩容不初始化
    void Reverse(size_t n)
    {
        Expand(n);
    }

    //扩容并且将元素初始化为0
    void Resize(size_t n, const T& val = T())
    {
        //若n<Size(),将数组截断至n
        if (n < Size())
        {
            _finish = _start + n;
        }
        else
        {
            //n>Capacity(),扩容并初始化,参数2可使用默认值0
            if (n>Capacity())
            {
                Expand(n);
            }
            while (_finish != _start + n)
            {
                *_finish = val;
                ++_finish;
            }
        }

    }
    void Expand(size_t n)
    {
        //扩容思路：如果空间已满，开辟一段空间，将原有数据拷贝置新开辟的空间，在释放原有空间即可
        if (n > Capacity())
        {
            size_t size = Size();
            T *tmp = new T[n];
            for (size_t i = 0; i < size; ++i)
            {
                tmp[i] = _start[i];
            }
            delete[]_start;
            _start = tmp;
            _finish = _start + size;
            _endofstorage = _start + n;
        }
    }

    void PushBack(const T& x)
    {
        //判满
        if (_finish == _endofstorage)
        {
            //扩容
            size_t capcacity = Capacity() * 2;
            //只有一个元素
            if (capcacity == 0)
            {
                capcacity = 3;
            }
            Expand(capcacity);
        }
        *_finish = x;
        ++_finish;
    }

    T& operator[](size_t pos)
    {
        assert(pos < Size());
        return _start[pos];
    }

    T& at(size_t pos)//越界会抛异常
    {
        if (pos >= Size())
        {
            throw out_of_range("pos out of range");
        }
        return _start[pos];
    }

    Iterator Begin()
    {
        return _start;
    }

    Iterator End()
    {
        return _finish;
    }
    ConstIterator Begin() const
    {
        return _start;
    }
    ConstIterator End() const
    {
        return _finish;
    }

protected:

    Iterator _start;
    Iterator _finish;
    Iterator _endofstorage;
};

void Print_Myvector(const Myvector<int>& v1)
{
    Myvector<int>::ConstIterator it1 = v1.Begin();
    while (it1 != v1.End())
    {
        cout << *it1 << " ";
        ++it1;
    }
    cout << endl;
}
void TestMyvector()
{
    Myvector<int> v1;
    v1.PushBack(1);
    v1.PushBack(2);
    v1.PushBack(3);
    v1.PushBack(4);
    v1.PushBack(5);
    Print_Myvector(v1);
    v1.Resize(8,5);
    Print_Myvector(v1);
}

1.2 list

list(带头结点的双向循环链表),当集合中需要进行大量的插入和删除操作时，使用list比vector好，在任意位置进行数据插入操作的时间复杂度均为O(1)

1.2.1 list基本使用

void Testlist()
{
    list<int> l1;
    l1.push_back(1);
    l1.push_back(2);
    l1.push_back(3);
    l1.push_back(4);


    list<int> l2;
    l2.push_back(7);
    l2.push_back(8);
    l2.push_back(9);

    //清空list
    //l1.clear();


    ////逆向遍历list
    //list<int> ::reverse_iterator it1 = l1.rbegin();
    //while (it1 != l1.rend())
    //{
    //  cout << *it1 << " ";
    //  ++it1;
    //}
    //cout << endl;

    //list的尾删
    //l1.pop_back();

    //头插
    //l1.push_front(9);

    //任意位置插入
    /*list<int>::iterator pos = find(l1.begin(), l1.end(), 3);
    if (pos != l1.end())
    {
        pos = l1.insert(pos, 0);

    }*/

    //l1.assign(3,10);
    //cout<<l1.front() << endl;
    //cout << l1.back() << endl;

    //l1.remove(3);

    //去除重复元素
    //l1.unique();

    //按升序排序
    //l1.sort();

    //反转链表
    //l1.reverse();

    //合并两个有序链表
    l1.merge(l2);
    list<int>::iterator it = l1.begin();
    while (it != l1.end())
    {
    /*  if (*it % 2 == 0)
        {
            *it *= 2;
        }*/
        cout << *it << " ";
        ++it;
    }
    cout << endl;

}

1.2.2 模拟实现Mylist.h

#pragma once

template <class T>

struct ListNode
{
    ListNode<T>* _next;
    ListNode<T>* _prev;
    T _data;

    ListNode(const T& data = T())
        :_next(NULL)
        , _prev(NULL)
        , _data(data)
    {}

};

template<class T,class Ref,class Ptr>

struct __ListIterator
{
    typedef ListNode<T> Node;
    typedef __ListIterator<T, Ref, Ptr> Self;

    Node* _node;

    __ListIterator(Node* node)
        :_node(node)
    {}

    Ref operator*()
    {
        return _node->_data;
    }

    Ptr operator->()
    {
        return &(operator*());
    }

    Self& operator++()
    {
        _node = _node->_next;
        return *this;
    }

    Self& operator++(int)
    {
        Self tmp(_node);
        _node = _node->_next;
        return tmp;
    }

    Self& operator--()
    {
        _node = _node->_prev;
        return *this;
    }

    Self& operator--(int)
    {
        Self tmp(_node);
        _node = _node->_prev;
        return tmp;
    }

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

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


};

template <class T>
class Mylist
{
    typedef ListNode<T> Node;
public:
    typedef __ListIterator<T, T&, T*> Iterator;
    typedef __ListIterator<T, const T&, const T*> ConstIterator;

    Iterator Begin()
    {
        return _head->_next;
    }

    ConstIterator Begin()const
    {
        return _head->_next;
    }

    Iterator End()
    {
        return _head;
    }

    ConstIterator End() const
    {
        return _head;
    }

    Mylist()
    {
        _head = new Node;
        _head->_next = _head;
        _head->_prev = _head;
    }

    void PushBack(const T& x)
    {
        Node* tail = _head->_prev;

        //连接tail newnode _head
        Node* newnode = new Node(x);
        tail->_next = newnode;
        newnode->_prev = tail;

        newnode->_next = _head;
        _head->_prev = newnode;
    }

    void Insert(Iterator pos, const T& x)
    {
        Node* cur = pos._node;
        Node* prev = cur->_prev;
        Node* newnode = new Node(x);

        prev->_next = newnode;
        newnode->_prev = prev;
        newnode->_next = cur;
        cur->_prev = newnode;
    }




protected:
    Node* _head;

};


void TestMylist()
{
    Mylist<int> l1;
    l1.PushBack(1);
    l1.PushBack(2);
    l1.PushBack(3);
    l1.PushBack(4);
    l1.PushBack(5);

    Mylist<int>::Iterator it = l1.Begin();
    while (it != l1.End())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;

}
相关标签： STL vector list deque

上一篇： 【JZOJ 5456】【NOIP2017提高A组冲刺11.6】奇怪的队列 (线段树)

下一篇： linux dns 配置

推荐阅读