文档章节

C++中list和vector的区别

旮旯儿
 旮旯儿
发布于 2014/08/25 10:52
字数 752
阅读 70
收藏 0

C++面试题:listvector有什么区别?
考点:理解listvector的区别
出现频率:★★★★
解析:
vector
和数组类似,它拥有一段连续的内存空间,并且起始地址不变,因此它能非常好的支持随机存取(即使用[]操作符访问其中的元素),但由于它的内 存空间是连续的,所以在中间进行插入和删除会造成内存块的拷贝(复杂度是O(n)),另外,当该数组后的内存空间不够时,需要重新申请一块足够大的内存并 进行内存的拷贝。这些都大大影响了vector的效率。
list
是由数据结构中的双向链表实现的,因此它的内存空间可以是不连续的。因此只能通过指针来进行数据的访问,这个特点使得它的随机存取变的非常没有效 率,需要遍历中间的元素,搜索复杂度O(n),因此它没有提供[]操作符的重载。但由于链表的特点,它可以以很好的效率支持任意地方的删除和插入。
由于listvector上面的这些区别,因此list::iteratorvector::iterator也有一些不同。请看下面的例子:
#include <iostream>
#include <vector>
#include <list>
using namespace std;
        
int main()
{
    vector<int> v;
    list<int> l;
               
    for (int i=0; i<8; i++)     //
vl中分别添加元素
    {
        v.push_back(i);
          l.push_back(i);
    }
               
     cout << "v[2] = " << v[2] << endl;
     //cout << "l[2] = " << l[2] << endl;       //
编译错误,list没有重载[]
     cout << (v.begin() < v.end()) << endl;
     //cout << (l.begin() < l.end()) << endl;   //
编译错误,list::iterator没有重载<>
      cout << *(v.begin() + 1) << endl;
               
      vector<int>::iterator itv = v.begin();
      list<int>::iterator itl = l.begin();
      itv = itv + 2;
      //itl = itl + 2;                  //
编译错误,list::iterator没有重载+
      itl++;itl++;                    //list::iterator
中重载了++,只能使用++进行迭代访问。
      cout << *itv << endl;
      cout << *itl << endl;         

      return 0;

}

由于vector拥有一段连续的内存空间,能非常好的支持随机存取,因此vector<int>::iterator支持“+”“+=”“<”等操作符。
list的内存空间可以是不连续,它不支持随机访问,因此list<int>::iterator则不支持“+”“+=”“<” 等操作符运算,因此代码2026行会有编译错误。只能使用“++”进行迭代,例如代码27行,使用两次itl++来移动itl。还有list也不支持 []运算符,因此代码18行出现编译错误。
总之,如果需要高效的随即存取,而不在乎插入和删除的效率,使用vector;如果需要大量的插入和删除,而不关心随即存取,则应使用list

答案:
vector拥有一段连续的内存空间,因此支持随机存取,如果需要高效的随即存取,而不在乎插入和删除的效率,使用vector

list拥有一段不连续的内存空间,因此支持随机存取,如果需要大量的插入和删除,而不关心随机存取,则应使用list



本文转载自:

旮旯儿
粉丝 2
博文 14
码字总数 4307
作品 0
程序员
私信 提问
STL vector 介绍连载1-2-3

STL简介: STL = Standard Template Library,标准模板库,惠普实验室开发的一系列软件的统称。它是由Alexander Stepanov、Meng Lee和David R Musser在惠普实验室工作时所开发出来的。这可能是...

天远
2012/05/20
152
0
《Effective STL》读书总结--关于STL 你不一定都懂的

春节期间一次用手机上网无意间发现了这本书,说起来还得感谢智能手机的发展,有时候还是很方便的。当时随便的翻了几页,于是我停不下来了,因为我发现原来我不知道的东西太多了。 我第一次接...

长平狐
2012/06/08
148
0
十STL容器

STL容器 顺序容器 顺序容器将单一类型的元素聚集起来,然后根据位置来存储和访问这些元素。顺序容器的元素排列次序与元素值无关,而是由元素添加到容器里的次序决定。 STL中最常用的顺序容器...

长平狐
2012/08/28
288
0
Effective STL - 容器

STL(standard template library)提供了一组表示容器,迭代器,函数对象和算法的模板。容器是一个与数组类似的单元,可以存若干个值。 STL容器是同质的,即存储的值的类型相同;算法是完成特...

積木leayn
2013/10/07
148
0
是技术太次,还是要得太高。面试屡屡失败!

先来个背景介绍。 本人计算机科学与技术专业,C++方向,2013年毕业。非211,非985,但是在学校期间主攻技术,基础和知识面还是不错的。从C、C++、C#、java、php、Qt都有接触,数据库、多线程...

changnet
2015/04/25
2.8K
16

没有更多内容

加载失败,请刷新页面

加载更多

PCB设计-Allegro软件入门系列-铺铜操作(下)

铺铜是PCB很常见的操作,PCB的敷铜一般都是覆地铜,增大地线面积,有利于地线阻抗降低,使电源和信号传输稳定,在高频的信号线附近敷铜,可大大减少电磁辐射干扰,起屏蔽作用。 本讲讲解啊一...

demyar
11分钟前
1
0
如何通过WASI SDK 在Linux上编译ZXing C++

Mozilla在今年三月份的时候公布了WASI。WASI的目标就是让WebAssembly在任何地方都可以运行,而不仅仅像现在这样只能运行在Node.js和Web浏览器中。WASI目前依然处于初级阶段,这篇文章分享下如...

yushulx
13分钟前
1
0
.Net界面开发神器—DevExpress官方汉化包免费下载!还在等什么?

点击获取DevExpress v19.1.7新版试用下载 DevExpress Localization Service允许您创建一组自定义的附属程序集,要将语言包添加到程序集中,请查看本文中为大家列出的对应版本的汉化包,下载并...

FILA6666
13分钟前
2
0
php生成二维码

        header('Content-Type: image/png');        //清除缓冲区,防止之前面不知道的情况下被加头部信息导致不显示图片内容        ob_clean();        $...

横着走的螃蟹
19分钟前
2
0
伪类和伪元素

伪类和伪元素 伪类和伪元素,对于绝大多数同学来说,都是耳熟能详的名字,但确实又有很多人搞不清楚它们之间的区别,以致于混淆概念。而当概念都混淆的时候,也往往意味着你不会经常使用它,...

不负好时光
21分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部