一、STL容器:

  • 顺序容器:

(1)vector 向量容器,底层是由数组实现的。

       初始化默认内存容量是0,有第一个元素时开辟一个元素大小,接下来的扩容以2倍的大小自动增长。(VS下是1.5倍)

       vector也可以在定义时直接指定空间大小和初始值:vector<type> iv(2,9);

       vetor扩充空间包括三个步骤:重新配置内存,移动数据,释放原空间。所以一旦进行空间重新配置,用户自己定义的指向原vector的所有迭代器就都失效了,而vector自带的迭代器会被调整,指向新的vector。

       重新配置空间时,先确定空间大小,再通过空间配置函数去配置空间

       常用操作方法:begin()  end()

               size() 返回元素个数  

               capacity() 返回空间总大小  

               push_back(val)  插入一个元素   

               insert(it,n,val)  在it迭代器前插入n个val

               pop_pack()   从最后删除一个元素  

               erase(it)  删除it迭代器指向的元素     该操作会使it迭代器失效,但会返回it下一个元素的迭代器

               clear()  清除所有元素    

               erase(first,last)  删除first和last之间的所有元素

 

(2)list 双向链表容器,底层由双向链表实现(含尾节点(为了保证迭代器的通用性))

       SGI list 是一个环状双向循环链表,所以只需要一个指针便可以表现整个链表。

       迭代器失效:list的插入(insert)和接合(splice)都不会造成迭代器的失效。

元素删除(erase)只有指向被删除元素的迭代器才会失效。

       常用操作方法:begin()   end()

         size()  返回当前节点个数(元素)

         push_back(val)  后插

         push_front(val)  前插

         pop_back()   后删

         pop_front()   前删

         insert(it,val)   在it迭代器之前插入值为val的节点

         erase(it)  删除it迭代器指向的节点

         clear()   清除所有节点(整个链表)

         remove(val)  将val之前的所有元素移除

         unique()   移除链表中相同的连续元素,相同的只剩余一个

         splice(it,list1)   将list1整个链表结合于it之前,不能是同一个list

         splice(it,list, it1)    将i所指元素结合于it之前,可以是同一个list

         splice(it,list,first,last)   将(first,last)内的所有元素接合到it之前

         merge(list1)    将list1 合并到 *this上,但两个list都必须是递增序列

         reverse()   将*this的内容逆向重置

         sort()  对元素排序,list自身的成员函数。因为通用算法sort只接受随机迭代器。

 

(3)deque  双端队列容器,底层用双端队列实现 【可以下标操作】

    缓冲区:实际存放数据的内存空间。大小默认为512bytes/sizeof(T),可以由用户自行设定,

map:中控器 ,管理的节点数:最小为8,最多是 所需要节点数加2(所需节点数:(元素个数/每个缓冲区可容纳的元素个数) +1 )。

当所有map结点都使用完了,一样要进行空间的重新配置(配置更大的,拷贝原来的,释放原来的)。

   

例:元素形态为int,缓冲区去大小为8的deque(指定了的deque<int,alloc,8>)。假设deque有20 个数据。所以就需要20/8 = 3个缓冲区,所以map使用了3个节点。

  数据结构如下:(空白是申请的空间,阴影部分为备用空间)

常用操作方法:pop_back()   pop_front()   clear()   erase(it)  erase(first,last)

                       push_back(val)   push_front(val)   size()   insert(it,val)

 

三者的比较:

vector和deque:①deque允许常数时间内对起头端进行元素的插入和移除。vector的头部插入和删除效率是十分低的

②deque没有容量的概念。因为deque是动态的以分段连续空间组合而成的,随时可以增加一段新的空间并连接起来,不会因为内存不足而重新配置空间【一定情况下也需要重新配置空间:当map使用率已经满载,便需要一块更大的空间作为map,但相比vector的重新配置空间,deque对map的重新配置要比vector要代价小】

③deque的迭代器不是普通的指针,其复杂度远远大于vector,所以在运算层面上来说,vector要比deque的效率要高的多。

vector和list:list相对于vector和deque来说,对于任意位置的元素插入和删除效率要远远大于其他两个。

 

  • 关联容器:

底层使用红黑树(平衡树,排序树,【数据有序】,add、delete、query(查询)

时间复杂度都是O(log2n))

【所有元素会根据元素的键值自动被排序。】

(1)set   单重集合

     multiset  多重集合

性质:元素值就是键值。

set不允许有两个相同的元素/键值,multiset允许有相同的元素/键值。

不可以通过迭代器改变set的元素值,因为set的元素值就是键值,改变键值会破坏set组织

元素删除后只有指向被删除元素的迭代器会失效。

       常用操作方法:

               增:insert(val);   时间复杂度: O(log2n)

               删:erase(val);   时间复杂度: O(log2n)

               查:find(key);<--set的成员方法【原因与map一致】 时间复杂度: O(log2n)

      另一个重要方法:count(val);统计该值存在的个数,但在单重集合中不允许关键字重复

(2)map:映射表<key,value>  底层也能用哈希表实现。根据key排序

     multimap :多重集合,允许key重复

       性质:同时拥有键值(key)和实值(value)。第一个元素是键值,第二个元素是实值。

                map不允许有两个相同的键值。multimap允许有相同的键值。

                不可以通过迭代器修改map的键值,但可以修改实值。

元素删除后只有指向被删除元素的迭代器会失效。

       常用操作方法:

增:insert(make_pair(key,value));   O(log2n)

                       map[key] = value;  也可以使用下标的方式进行插入

                删:erase(key);    O(log2n)

                查:find(key);<---map的成员方法     O(log2n)

               【map的成员方法是根据map的底层结构来进行实现的,效率自然比全局的泛型算法高】

              【顺序容器没有find的成员方法,因而只能用全局的find算法】

               STL还提供了一个通过val查找的方法:find_if(first,last,pred);pred是用于比较数值的函数或者函数对象。

(3)hashtable:散列表  底层数据结构:以vector为buckets,以开链处理哈希碰撞。

如图:

     hashtable:bucktes的个数以28个质数为底。如:用户定义一个n为50的hashtable,得到的散列表实际桶数量为53(第一个质数),这里直接用vector下的空间申请函数reserve去处理,并用<vector>insert将恐案件初始化为0

对于插入元素操作,有两个函数:①insert_unique,不允许key重复,②insert_equal,允许key重复。

      1)两个插入在开始时都要先判断是否需要重新建表。这里调用resize<hashtable>函数,原则是:当元素个数(加上新增元素)大于“桶”的个数时,就重建表格。

重建表格当然首先要重新申请新的空间<大小为下一个质数>,将原buckets脸上的元素拷贝到新表中,然后新旧buckets对调,最后将旧表释放。

     2)插入新元素时,先要对新元素进行hash。这里讲hash function进行包装,以_bkt_num函数为接口,该函数去调用bkt_bun_key函数,在bkt_num_key中将hash function得到的值进行取模运算。

所以hash function只需将原值返回即可,对char*类型字符串则要进行特殊处理。

hash function是仿函数,重载operator()运算符,在该重载函数中进行值的返回即可。但也有部分类型未被重载,所以不可处理。

(4)hash_set、hash_map、hash_multiset、hash_multimap

     这四种关联式容器,底层机制都是hashtable,元素不会被自动排序。

    除此之外他们与原身(set、map、multiset、multimap)的特性完全相同。当然hash_table不能处理的型别,他们也无法处理。

 

二、容器适配器:

1、stack:栈  底层默认使用deque的数据结构,将一端封闭,实现后进先出的行为。

只能在顶端进行元素的插入、删除、取得(get),所以不允许进行遍历,没有迭代器。

用户也可以自己指定底层的数据结构,如:stack<int,list<int> >。这个stack底层使用的额数据结构就是list。因为list也是双向开口的数据结构,所需的成员函数list也都有,所以以list为底部结构并封闭其端口开口,实现stack的先进先出特性。

              常用操作方法:

                     top 【返回栈顶元素】

                     push 【入栈,插到栈顶】

                     pop 【栈顶元素出栈】

                     size 【返回栈中元素的个数】

                     empty 【判断栈是否为空】

2、queue:队列  底层默认使用deque的数据结构,封闭低端的出口和顶端的入口,实现先进先出(从底端入,从顶端出的性质。

            因为只能从底端入,从顶端出,所以也不允许遍历行为。没有迭代器。

                     同理,用户也可以自己指定queue的底层数据结构:queue<int ,list<int> >。用list作为queue的底层容器。

            常用操作方法:

                   push 【入队插到队尾】

                   pop 【队首元素出队】

                   size 【返回队列中元素的个数】

                   front 【返回队列中第一个元素】

                   back 【返回队列中最后一个元素】

                   empty 【判断队列是否为空】

3、qriority_queue:带权队列  即queue中的元素不是按照被推入的次序排列,而是按照元素的权值(实值)排列,权值最高的,排在最前面。

       默认情况下qriority_queue底层使用max_heap(以vector)实现,可以满足以“权值高低自动排序”的特性。

       与queue一样,qriority_queue不提供遍历的功能,也不提供迭代器。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐