美文网首页
(Boolan) STL与泛型编程第三周笔记

(Boolan) STL与泛型编程第三周笔记

作者: 留胡子的熊 | 来源:发表于2017-09-06 23:33 被阅读0次

c++stack(堆栈)是一个容器的改编,它实现了一个先进后出的数据结构(FILO)
使用该容器时需要包含#include<stack>头文件;
定义stack对象的示例代码如下:
stack<int>s1;
stack<string>s2;
stack的基本操作有:
1.入栈:如s.push(x);
2.出栈:如 s.pop().注意:出栈操作只是删除栈顶的元素,并不返回该元素。
3.访问栈顶:如s.top();
4.判断栈空:如s.empty().当栈空时返回true。
5.访问栈中的元素个数,如s.size();
下面举一个简单的例子:

#include<iostream>  
#include<stack>  
using namespace std;  
int main(void)  
{  
    stack<double>s;//定义一个栈  
    for(int i=0;i<10;i++)  
        s.push(i);  
    while(!s.empty())  
    {  
        printf("%lf\n",s.top());  
        s.pop();  
    }  
    cout<<"栈内的元素的个数为:"<<s.size()<<endl;  
    return 0;  
}

1.容器deque

deque是一种分段连续的容器,特点是双向开口,可以认为它是一段连续的内存空间,不仅可以向前方增加内存空间,也可以向后方增加内存空间。
在实际内存中实现双向扩充是比较复杂的事情,那么deque中是如何实现的呢?deque通过一个控制器来串联一系列的缓冲器(buffer),从而达到逻辑上的连续效果。
deque的内存管理示意图,如下图所示:


deque是通过一个vector在维护自身的控制器,在控制器中存储的是指向buffer的指针,因此我们需要用一个指向指针的指针来指向这个vector的地址。
deque能在逻辑上实现内存连续,最关键的是iterator在起作用。迭代器运行到边界的时候,都需要检测是否到边界,然后通过回到控制buffer的那个vector来管理边界的buffer了。在iterator中,cur、first、last和node分别指向了用户使用时的当前的数据,first指向了buffer的第一块空间,last指向了buffer之后那个不在buffer中的空间,而node指向了控制buffer的指针序列中的实际位置
deque的源代码如下所示(参考课程PPT):

deque iterator的源代码如下所示:

deuqe的插入问题:
元素插入的时候因为是按顺序排列,如果插入元素不在两头在中间,会改变其他元素的位置,如果插入点距离前段比较近,那么移动前段比较合适,效率较高;
如果插入点距离后端比较近,那么将插入点之后的元素向后移动比较快。
deque insert函数的源代码如下:

iterator insert(iterator postion, const value_type& x){  
    if(postion.cur == start.cur)  //如果安插点是deque的最前端  
    {  
        push_front(x);  //直接使用push_front  
        return start;  
    }  
    else if(postion.cur == finish.cur)  //如果安插点是deque的最末位  
    {  
        push_back(x);  //直接交给push_back  
        iterator tmp = finish;  
        --tmp;  
        return tmp;  
    }  
    else  
    {  
        return insert_aux(postion, x);  
     }  
}  
  
template <class T, class Alloc, size_t BufSize>  
typename deque<T, Alloc, BufSize>::iterator_deque<T, Alloc, BufSIze>:: itert_aux(iterator pos, const value_type& x){  
    difference_type index = pos - start;    //安插点之前的元素个数  
    value_type x_copy = x;  
    if(index < size() / 2){  //如果安插点之前的元素较少  
        push_front(front());  //在最前端加入第一个元素同值的元素  
        .......  
        copy(front2, pos1, front1);  //元素搬移  
    }  
    else {    //安插点之后的元素较少  
        push_back(back());//在尾端加入最末元素同值的元素  
        ......  
        copy_backward(pos, back2, back1);//元素搬移  
    }  
    *pos = x_copy;//在安插点上设定新值  
    return pos;  
}  

deque如何模拟连续空间,全是的确iterators的功劳

具体代码如下:

reference operator[](size_type n)  
{  
      return start[difference_type(n)];  
}  
reference front()  
{  
    return *start;  
}  
reference back()  
{  
    iterator tmp = finish;  
    --tmp;  
    return *tmp;  
}  
size_type size() const  
{  
    return finish - start;   
}  
bool empty() const  
{  
    return finish == start;  
}  
reference operator* () const  
{  
    return *cur;  
}  
pointer operator->() const  
{  
    return &(operator*());  
}  
//两个iterator之间的距离相当于  
//(1)两个iterator之间的buffer的总长度+  
//(2)itr至buffer末尾的长度+  
//(3)x至buffer开头的长度  
difference_type  
operator- (const self& x) const  
{  
    return difference_type(buffer_size()) * (node - x.node - 1) + (cur - first) + (x.last - x.cur);  
    //buffer size * 首尾buffer之间的buffer之间的数量 + 末尾(当前)buffer的元素量 + 起始buffer的元素量  
}  
self& operator++()  
{  
    ++cur;                   //切换至下一个元素  
    if(cur == last){         //如果抵达缓冲区的末尾  
        set_node(node + 1);  //就跳至下一个节点(缓冲区)的起点  
        cur = first;    
    }  
    return *this;  
}  
self operator++(int)  
{  
    self tmp = *this;  
    ++*this;  
     return tmp;  
}  
  
self& operator--()  
{  
    if(cur == first){         //如果目前在缓冲区开头,  
        set_node(node - 1);   //就跳至前一节点(缓冲区)的最末端。  
        cur = last;  
    }  
    --cur;                   //往前移动一个元素(最末元素)  
    return *this;  
}  
self operator--(int)  
{  
    self tmp = *this;  
    --*this;  
    return tmp;  
}  
  
void set_node(map_pointer new_node)  
{  
    node = new_node;  
    first = *new_node;  
    last = first + difference_type(buffer_size));  
}  
  
self& operator+=(difference_type n ){  
    difference_type offset = n + (cur - first);  
    if(offset >= 0 && offset < difference_type(buffer_size())  
    //目标位置在同一级缓存区  
         cur += n;  
     else{  
       //目标位置不在同一级缓存区内  
         difference_type node_offset = offset > 0? offset / difference_type(buffer_size()): -difference_type((-offset - 1) / buffer_size;  
          //切换至正确的的缓存区  
          set_node(node + node_offset);  
          cur = first + (offset - node_offset * difference_type(buffser_size());  
      }  
      return *this;  
}  
  
operator+(difference_type n) const   
{  
     self tmp = *this;  
     return tmp += n;  
}  
  
self& operator-=(difference_type n)  
{  
    return *this += - n;  
}  
self operator-(difference_type n)  
{  
    self tmp = *this;  
    return tmp -= n;  
}  
reference operator[] (difference_type n)const  
{  
    return *(*this + n);  
}  

GNU 4.9版本中实现的dequeUML图,如下图所示:

2.容器 queue

容器queue是以deque为底层结构实现的,具体代码如下:

template <class T, class Sequence = deque<T>>  
class queue  
{  
............  
public:  
    typedef typename Sequence::value_type value_type  
    typedef typename Sequence::size_type size_type  
    typedef typename Sequence::reference reference;  
    typedef typename Sequence::const_reference const_reference;  
protected:  
    Sequence c;  //底层容器  
 public:  
    bool empty() const{return c.empty();}  
    size_type size() const{return c.size();}  
    reference front() const {return c.front();}  
    const_reference front() const{ return c.front();}  
    reference back(){return c.back(); }  
    const_reference back() const {return c.back();}  
    void push (const value_type& x){ c.push_back(); }  
    void pop(){c.pop.front();}  
}  

3.容器 stack

容器stack也是以deque为底层结构实现的,需要注意的是queue和stack都不允许遍历,也不提供iterator,具体代码如下:

template <class T, class Sequence = deque<T>>  
class stack  
{  
............  
public:  
    typedef typename Sequence::value_type value_type  
    typedef typename Sequence::size_type size_type  
    typedef typename Sequence::reference reference;  
    typedef typename Sequence::const_reference const_reference;  
protected:  
    Sequence c;  //底层容器  
 public:  
    bool empty() const{return c.empty();}  
    size_type size() const{return c.size();}  
    reference top() const {return c.back();}  
    const_reference top() const{ return c.back();}  
    void push (const value_type& x){ c.push_back(); }  
    void pop(){c.pop.back();}  
}  

4.容器 rb_tree

Red-Black tree(红黑树)是平衡二元搜寻树(balanced Binary search tree)中常被使用的一种。
平衡二院搜寻树的特征:排列规律,有利于search和insert,并保持适度平衡,无任何节点过深。


红黑树的实现代码:

5.容器 set,multiset

容器set的实现代码:

template <class Key, class Compare = less<Key>, class Alloc = alloc>  
class set{  
public:  
      //typedefs:  
      typedef Key key_type;  
      typedef Key value_type;  
      typedef Compare key_compare;  
      typedef Compare value_compare;  
private:  
    typedef rb_tree<key_type, value_type, identity<value_type<. key_compare, Alloc> rep_type;  
     rep_type t;  
 public:  
      typedef typename rep_type::const_iterator iterator;    
...  
//set的所有操作,都调用底层rb_tree的函数,从这点看来,set实际应该为container adapter  
}  

容器multiset的实现代码如下:

6.容器 map和multimap

map的实现代码如下:

multimap实现代码如下:


容器map独特的operator[]

相关文章

网友评论

      本文标题:(Boolan) STL与泛型编程第三周笔记

      本文链接:https://www.haomeiwen.com/subject/ksrbjxtx.html