博客
关于我
【4】STL容器之 list vector deque map set 容器的异同点
阅读量:167 次
发布时间:2019-02-28

本文共 2478 字,大约阅读时间需要 8 分钟。

【1】list容器的特点

list是一种序列式容器。list容器完成的功能实际上和数据结构中的双向链表是极其相似的,list中的数据元素是通过链表指针串连成逻辑意义上的线性表,也就是list也具有链表的主要优点,即:在链表的任一位置进行元素的插入、删除操作都是快速的。

(list只能在首尾进行元素的插入与删除,并不能在中间进行任意元素的删除和插入,vector只能删除末尾元素,dequeue则在两端都可以进行删除和添加,底部近顶部出)

list的实现大概是这样的:list的每个节点有三个域:前驱元素指针域、数据域和后继元素指针域。

前驱元素指针域保存了前驱元素的首地址;数据域则是本节点的数据;后继元素指针域则保存了后继元素的首地址。由于list元素节点并不要求在一段连续的内存中,显然在list中是不支持快速随机存取的,因此对于迭代器,只能通过“++”或“--”操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作,这点,是与vector等不同的地方。

【2】list   vector   deque的异同点比较

vector : vector和built-in数组类似,拥有一段连续的内存空间,能非常好的支持随即存取,即[]操作符,但由于它的内存空间是连续的,所以在中间进行插入和删除会造成内存块的拷贝,另外,当插入较多的元素后,预留内存空间可能不够,需要重新申请一块足够大的内存并把原来的数据拷贝到新的内存空间。这些影响了vector的效率,但是实际上用的最多的还是vector容器,建议大多数时候使用vector效率一般是不错的。

list:list就是数据结构中的双向链表(根据sgi stl源代码),因此它的内存空间是不连续的,通过指针来进行数据的访问,这个特点使得它的随即存取变的非常没有效率,因此它没有提供[]操作符的重载。但由于链表的特点,它可以以很好的效率支持任意地方的删除和插入。

deque: deque是一个double-ended queue,它的具体实现不太清楚,但知道它具有以下两个特点:它支持[]操作符,也就是支持随即存取,并且和vector的效率相差无几,它支持在两端的操作:push_back,push_front,pop_back,pop_front等,并且在两端操作上与list的效率也差不多。

如何选择这三个容器中哪一个,应根据你的需要而定,具体可以遵循下面的原则
1. 如果你需要高效的随即存取,而不在乎插入和删除的效率,使用vector
2. 如果你需要大量的插入和删除,而不关心随即存取,则应使用list
3. 如果你需要随即存取,而且关心两端数据的插入和删除,则应使用deque。

 

【3】list的具体使用方法

(1)构造函数

     list<int> c0; //空链表

  list<int> c1(3); //建一个含三个默认值是0的元素的链表

  list<int> c2(5,2); //建一个含五个元素的链表,值都是2

  list<int> c4(c2); //建一个c2的copy链表

  list<int> c5(c1.begin(),c1.end()); c5含c1一个区域的元素[_First, _Last)。

(2)成员函数

     list <int> c;  //定义一个list容器

     c.begin()     // 返回指向链表第一个元素的迭代器,即返回指向容器的起始位置的地址;

     c.end()      //返回指向链表最后一个元素之后的迭代器,即返回指向容器的末尾位置的地址;

    c.front()    //返回第一个位置的元素

    c.back()    //返回最后一个位置的元素

    push_back()    //其中push_back()从list的末端插入

    push_front()   //而 push_front()实现的从list的头部插入。

    pop_back()      通过pop_front()删除第一个元素;

    pop_front()       通过删除最后一个元素。序列必须不为空,如果当list为空的时候调用pop_back()和pop_front()会使程序崩掉。

    erase():删除一个元素或一个区域的元素(两个重载)

    empty( )   判断容器是否为空

   resize()      如果调用resize(n)将list的长度改为只容纳n个元素,超出的元素将被删除。

   clear(): 清空list中的所有元素。

    swap():交换两个链表(两个重载),一个是l1.swap(l2); 另外一个是swap(l1,l2),都可能完成连个链表的交换。

    merge():合并两个链表并使之默认升序(也可改)

【4】迭代器访问

#include "pch.h"    #include 
#include
//队列 #include
//双端队列 #include
#include
#include
int main() { vector
myvector; for (size_t i = 0; i < 5; i++) { myvector.push_back(i); } //正向迭代 auto ibegin = myvector.begin(); auto iend = myvector.end(); for(ibegin; ibegin!=iend; ibegin++) { cout << *ibegin << endl; }; //反向迭代 auto rbegin = myvector.rbegin(); auto rend = myvector.rend(); for (rbegin; rbegin != rend; rbegin++) { cout << *rbegin << endl; }; return 0; }

 

转载地址:http://inxc.baihongyu.com/

你可能感兴趣的文章
Mysql 常见错误
查看>>
mysql 常见问题
查看>>
MYSQL 幻读(Phantom Problem)不可重复读
查看>>
mysql 往字段后面加字符串
查看>>
mysql 快照读 幻读_innodb当前读 与 快照读 and rr级别是否真正避免了幻读
查看>>
MySQL 快速创建千万级测试数据
查看>>
mysql 快速自增假数据, 新增假数据,mysql自增假数据
查看>>
MySql 手动执行主从备份
查看>>
Mysql 批量修改四种方式效率对比(一)
查看>>
Mysql 报错 Field 'id' doesn't have a default value
查看>>
MySQL 报错:Duplicate entry 'xxx' for key 'UNIQ_XXXX'
查看>>
Mysql 拼接多个字段作为查询条件查询方法
查看>>
mysql 排序id_mysql如何按特定id排序
查看>>
Mysql 提示:Communication link failure
查看>>
mysql 插入是否成功_PDO mysql:如何知道插入是否成功
查看>>
Mysql 数据库InnoDB存储引擎中主要组件的刷新清理条件:脏页、RedoLog重做日志、Insert Buffer或ChangeBuffer、Undo Log
查看>>
mysql 数据库中 count(*),count(1),count(列名)区别和效率问题
查看>>
mysql 数据库备份及ibdata1的瘦身
查看>>
MySQL 数据库备份种类以及常用备份工具汇总
查看>>
mysql 数据库存储引擎怎么选择?快来看看性能测试吧
查看>>