精华内容
下载资源
问答
  • 搞定技术面试:那些你可能不知道的 vector array 的区别 最近几年,计算机工作越发难找,你必须比其他人了解的更多,才能有更多的机会找到一个更好的工作。 C++ 标准库(STL)是很多C++面试中都会问到的问题,很...

    搞定技术面试:那些你可能不知道的 vector 和 array 的区别

    最近几年,计算机工作越发难找,你必须比其他人了解的更多,才能有更多的机会找到一个更好的工作。

    C++ 标准库(STL)是很多C++面试中都会问到的问题,很多很多问题会关于 Vector 的空间分配、动态增长之类的问题,那么你了解 STL 中那些顺序容器的区别与联系吗?
    你知道在什么情况选用什么容器吗?

    先说结论,一般情况选择 vector 是很好的选择,如果你的程序目标有如下特点时,才可能需要换用别的容器:

    • 有很多小元素、空间额外开销比较重要,不要使用 list 和 forward_list;
    • 程序要求随机访问,选择 vector 和 deque;
    • 程序经常在中间插入元素,可以选择 list 和 forward_list;
    • 程序只在头尾插入元素,不常在中间插入元素,选择 deque;
    • 程序一开始插入时会在中间插入元素,但之后的使用过程中基本不在中间插入元素,先用 list 处理输入场景,再用 vector 拷贝 list 的数据,处理后续使用。

    整体介绍

    所有的顺序容器都具有可以快速按顺序访问元素的能力,但每种容器在具体的实现上又有些区别。

    顺序容器类型 含义 特点
    vector 可变大小数组 随机访问快、尾部插入元素快、其他位置插入、删除元素慢
    deque 双端队列 随机访问快、头尾插入元素快
    list 双向链表 只支持双向顺序访问、在任何位置插入、删除元素都很快
    forward_list 单向链表 只支持从前往后的单向顺序访问、在任何位置插入删除元素都很快
    array 固定大小数组 随机访问快、容器大小固定不支持插入删除元素
    string 字符串,类似vector,专门保存字符、随机访问快、在尾部插入删除元素快

    按类型介绍

    vector string

    vector 和 string 将元素保存在连续的内存空间中,分配一段连续的内存空间进行存储,其迭代器采用 C++ 指针即可,因此其支持随机访问和存储,支持下标操作符,节省空间。但是其在分配的内存不够的情况下,需要对容器整体进行重新分配、拷贝和释放等操作(空间的动态增长),而且在 vector 和 string 中间插入或删除元素效率很低。

    在这里插入图片描述
    vector的内存分配实现原理:STL内部实现时,首先分配一个非常大的内存空间预备进行存储,即capacity()函数返回的大小,当超过此分配的空间时再整体重新放分配一块内存存储(VS6.0是两倍,VS2005是1.5倍),所以这给人以vector可以不指定vector即一个连续内存的大小的感觉。通常此默认的内存分配能完成大部分情况下的存储。

    扩充空间(不论多大)都应该这样做:

    1. 配置一块新空间
    2. 将旧元素一一搬往新址
    3. 把原来的空间释放还给系统

    list forward_list

    list 和 forward_list 是以节点形式来存放数据,使用的是非连续的内存空间来存放数据,因此,在其内部插入和删除元素的时间复杂度都是O(1),但是其不支持随机访问和存取,不支持下标;因为每个结点需要额外空间存储连接的情况,他们比 vector 占用的内存要多很多。
    在这里插入图片描述

    list 是非连续存储结构,具有双链表结构,每个元素维护一对前向和后向指针,因此支持前向/后向遍历。支持高效的随机插入/删除操作,但随机访问效率低下,且由于需要额外维护指针,开销也比较大。每一个结点都包括一个信息快Info、一个前驱指针Pre、一个后驱指针Post。可以不分配必须的内存大小方便的进行添加和删除操作。使用的是非连续的内存空间进行存储。

    forward_list 底层实现上是单链表,且实质上无任何多余开销,与 list 相比,此容器在不需要双向迭代时提供更有效地利用空间的存储。在链表内或跨数个链表添加、移除和移动元素,不会非法化当前指代链表中其他元素的迭代器。forward_list 的迭代器不支持iter--操作,即不支持反向迭代;同时 forward_list 也不支持size()操作。

    deque

    vector是一个单向开口的容器,deque则是一个双向开口的容器,所谓双向开口就是再头尾两端均可以做元素的插入和删除操作。

    在这里插入图片描述
    deque 在空间增长上与 vector 不同,它是动态的以分段的连续空间组合而成,随时可以增加一段空间连接起来。
    因此,为了管理多段连接,deque有中控器的概念,此处实现上详细情况的请参见《STL源码剖析》

    array

    array 与内置数组类似,大小是固定的,因此不支持增加元素、删除元素以及改变容器大小的功能。
    在使用 array 时,必须同时指定元素类型和大小array<int,20>

    此容器是一个聚合类型,其语义等同于保有一个 C 风格数组 T[N] 作为其唯一非静态数据成员的结构体。该结构体结合了 C 风格数组的性能、可访问性与容器的优点,比如可获取大小、支持赋值、随机访问迭代器等。

    迭代器 Iterator

    迭代器的范围都是左开右闭,理解为数学上的区间则是 [xx.begin(), xx.end()),左边是可以达到的,右边是达不到的。

    Reference

    1. C++ Primer 5th
    2. STL 源码剖析
    3. Cppreference
    4. CSDN:C++三种容器:list、vector和deque的区别
    展开全文
  • 数组、vector和array的区别

    千次阅读 2018-10-24 11:33:09
    模板类vector和array都是数组替代品 1.vector: vector&amp;lt;typeName&amp;gt; vt&amp;lt;n_elem&amp;gt;; 其中参数可以是n_elem可以使hi整形常量,也是是整形变量。 可以在运行阶段时候设置...

    模板类vector和array都是数组的替代品

    1.vector:

    vector<typeName> vt<n_elem>;
    

    其中参数可以是n_elem可以使hi整形常量,也是是整形变量。
    可以在运行阶段的时候设置vector的长度,使用new和delete来管理内存,对象存储在堆上。

    2.array

    array<typeName, n_elem> arr;
    

    n_elem 不能是变量,不许是常量。
    与数组一样array的长度也是固定的,存储在栈中,因此其效率与数组相同,但是相对于数组,array对象可以直接赋值给另一个array对象。另外array并非只能存储基本数据类型,它还可存储类对象。

    展开全文
  • vector和array的区别 arrary的空间是由系统分配的,在编译时已经确定,存放在栈区 vector的空间可由程序员动态分配,可动态增长,在运行时才确定大小,存放在堆区 要想深入理解它们的区别,则就是堆和栈的区别 ...

    vector和array的区别

    arrary的空间是由系统分配的,在编译时已经确定,存放在栈区

    vector的空间可由程序员动态分配,可动态增长,在运行时才确定大小,存放在堆区

    要想深入理解它们的区别,则就是堆和栈的区别

    一、预备知识—程序的内存分配
    一个由C/C++编译的程序占用的内存分为以下几个部分
    1、栈区(stack)— 由编译器自动分配释放 ,存放函数的参数值,局部变量的值等。其
    操作方式类似于数据结构中的栈。
    2、堆区(heap) — 一般由程序员分配释放, 若程序员不释放,程序结束时可能由OS回
    收 。注意它与数据结构中的堆是两回事,分配方式倒是类似于链表,呵呵。
    3、全局区(静态区)(static)—,全局变量和静态变量的存储是放在一块的,初始化的
    全局变量和静态变量在一块区域, 未初始化的全局变量和未初始化的静态变量在相邻的另
    一块区域。 - 程序结束后由系统释放。
    4、文字常量区 —常量字符串就是放在这里的。 程序结束后由系统释放
    5、程序代码区—存放函数体的二进制代码。


    二、例子程序
    这是一个前辈写的,非常详细
    //main.cpp
    int a = 0; 全局初始化区
    char *p1; 全局未初始化区
    main()
    {
    int b; 栈
    char s[] = "abc"; 栈
    char *p2; 栈
    char *p3 = "123456"; 123456/0在常量区,p3在栈上。
    static int c =0; 全局(静态)初始化区
    p1 = (char *)malloc(10);
    p2 = (char *)malloc(20);
    分配得来得10和20字节的区域就在堆区。
    strcpy(p1, "123456"); 123456/0放在常量区,编译器可能会将它与p3所指向的"123456"
    优化成一个地方。
    }


    二、堆和栈的理论知识
    2.1申请方式
    stack:
    由系统自动分配。 例如,声明在函数中一个局部变量 int b; 系统自动在栈中为b开辟空

    heap:
    需要程序员自己申请,并指明大小,在c中malloc函数
    如p1 = (char *)malloc(10);
    在C++中用new运算符
    如p2 = new char[10];
    但是注意p1、p2本身是在栈中的。


    2.2
    申请后系统的响应
    栈:只要栈的剩余空间大于所申请空间,系统将为程序提供内存,否则将报异常提示栈溢
    出。
    堆:首先应该知道操作系统有一个记录空闲内存地址的链表,当系统收到程序的申请时,
    会遍历该链表,寻找第一个空间大于所申请空间的堆结点,然后将该结点从空闲结点链表
    中删除,并将该结点的空间分配给程序,另外,对于大多数系统,会在这块内存空间中的
    首地址处记录本次分配的大小,这样,代码中的delete语句才能正确的释放本内存空间。
    另外,由于找到的堆结点的大小不一定正好等于申请的大小,系统会自动的将多余的那部
    分重新放入空闲链表中。

    在进程退出的时候 若程序员没有释放这个堆空间,则系统会自动回收。除非程序碰到异常进程没有正常退出,才会导致潜在的内存泄漏。

    2.3申请大小的限制
    栈:在Windows下,栈是向低地址扩展的数据结构,是一块连续的内存的区域。这句话的意
    思是栈顶的地址和栈的最大容量是系统预先规定好的,在WINDOWS下,栈的大小是2M(也有
    的说是1M,总之是一个编译时就确定的常数),如果申请的空间超过栈的剩余空间时,将
    提示overflow。因此,能从栈获得的空间较小。
    堆:堆是向高地址扩展的数据结构,是不连续的内存区域。这是由于系统是用链表来存储
    的空闲内存地址的,自然是不连续的,而链表的遍历方向是由低地址向高地址。堆的大小
    受限于计算机系统中有效的虚拟内存。由此可见,堆获得的空间比较灵活,也比较大。



    2.4申请效率的比较:
    栈由系统自动分配,速度较快。但程序员是无法控制的。
    堆是由new分配的内存,一般速度比较慢,而且容易产生内存碎片,不过用起来最方便.
    另外,在WINDOWS下,最好的方式是用VirtualAlloc分配内存,他不是在堆,也不是在栈是
    直接在进程的地址空间中保留一块内存,虽然用起来最不方便。但是速度快,也最灵活。


    2.5堆和栈中的存储内容
    栈: 在函数调用时,第一个进栈的是主函数中后的下一条指令(函数调用语句的下一条可
    执行语句,函数调用前和调用后系统通用寄存器值会发生变化,尤其是程序指针会随执行程序或函数的不同而发生改变,当函数执行完后需要返回原来的位置继续执行,所以需要通过栈来保存调用前的程序指针。而调用的开始就是让程序指针转向被调用的代码,在转向之前当然要先保存程序指针,以便回来继续执行,而回来后继续执行哪里,就是“被调用函数下一行的内存地址”啦)的地址,然后是函数的各个参数,在大多数的C编译器中,参数是由右往左入栈
    的,然后是函数中的局部变量。注意静态变量是不入栈的。
    当本次函数调用结束后,局部变量先出栈,然后是参数,最后栈顶指针指向最开始存的地
    址,也就是主函数中的下一条指令,程序由该点继续运行。
    堆:一般是在堆的头部用一个字节存放堆的大小。堆中的具体内容由程序员安排。
    (关于在函数调用时,第一个进栈的是主函数中后的下一条指令,仍有争议)


    2.6存取效率的比较

    char s1[] = "aaaaaaaaaaaaaaa";
    char *s2 = "bbbbbbbbbbbbbbbbb";
    aaaaaaaaaaa是在运行时刻赋值的;
    而bbbbbbbbbbb是在编译时就确定的;
    但是,在以后的存取中,在栈上的数组比指针所指向的字符串(例如堆)快。
    比如:
    #include
    void main()
    {
    char a = 1;
    char c[] = "1234567890";
    char *p ="1234567890";
    a = c[1];
    a = p[1];
    return;
    }
    对应的汇编代码
    10: a = c[1];
    00401067 8A 4D F1 mov cl,byte ptr [ebp-0Fh]
    0040106A 88 4D FC mov byte ptr [ebp-4],cl
    11: a = p[1];
    0040106D 8B 55 EC mov edx,dword ptr [ebp-14h]
    00401070 8A 42 01 mov al,byte ptr [edx+1]
    00401073 88 45 FC mov byte ptr [ebp-4],al
    第一种在读取时直接就把字符串中的元素读到寄存器cl中,而第二种则要先把指针值读到
    edx中,再根据edx读取字符,显然慢了。


    2.7小结:
    堆和栈的区别可以用如下的比喻来看出:
    使用栈就象我们去饭馆里吃饭,只管点菜(发出申请)、付钱、和吃(使用),吃饱了就
    走,不必理会切菜、洗菜等准备工作和洗碗、刷锅等扫尾工作,他的好处是快捷,但是自
    由度小。
    使用堆就象是自己动手做喜欢吃的菜肴,比较麻烦,但是比较符合自己的口味,而且自由
    度大。 (经典!)

    展开全文
  • Vector Array 区别

    2019-10-08 21:37:09
    1:array 定义时候必须定义数组元素个数;而vector 不需要;且只能包含整型字面值常量,枚举常量或者用常量表达式初始化整型const对象, 非const变量以及需要到运行阶段才知道其值const变量都不能用来定义...
    1:array 定义的时候必须定义数组的元素个数;而vector 不需要;且只能包含整型字面值常量,枚举常量或者用常量表达式初始化的整型const对象,
    非const变量以及需要到运行阶段才知道其值的const变量都不能用来定义数组的维度.
    
    2:array 定义后的空间是固定的了,不能改变;而vector 要灵活得多,可再加或减. 3:vector有一系列的函数操作,非常方便使用.和vector不同,数组不提供 push——back或者其他的操作在数组中添加新元素,数组一经定义就不允许添加新元素; 若需要则要充许分配新的内存空间,再将员数组的元素赋值到新的内存空间。

      4.   数组和vector不同,一个数组不能用另一个数组初始化,也不能将一个数组赋值给另一个数组;

     


     

     

    vector类为内置数组提供了一种替代表示,与string类一样 vector 类是随标准 C++引入的标准库的一部分 ,为了使用vector 我们必须包含相关的头文件  :

    #include <vector>

    使用vector有两种不同的形式,即所谓的数组习惯和 STL习惯。

    一、数组习惯用法

    1. 定义一个已知长度的 vector :

      vector< int > ivec( 10 );  //类似数组定义int ia[ 10 ];

      可以通过ivec[索引号] 来访问元素

      使用 if ( ivec.empty() ) 判断是否是空,ivec.size()判断元素个数。

     

    2. vector的元素被初始化为与其类型相关的缺省值:算术和指针类型的缺省值是 0,对于class 类型,缺省值可通过调用这类的缺省构造函数获得,我们还可以为每个元素提供一个显式的初始值来完成初始化,例如  
      vector< int > ivec( 10, -1 ); 
      定义了 ivec 它包含十个int型的元素 每个元素都被初始化为-1 

      对于内置数组 我们可以显式地把数组的元素初始化为一组常量值,例如 : 
      int ia[ 6 ] = { -2, -1, 0, 1, 2, 1024 };


    我们不能用同样的方法显式地初始化 vector ,但是可以将 vector 初始化为一个已有数组的全部或一部分,只需指定希望被用来初始化 vector 的数组的开始地址以及数组最末元的下一位置来实现,例如:  
    // 把 ia 的 6 个元素拷贝到 ivec 中 
      vector< int > ivec( ia, ia+6 );  


    被传递给ivec 的两个指针标记了用来初始化对象的值的范围,第二个指针总是指向要拷贝的末元素的下一位置,标记出来的元素范围也可以是数组的一个子集,例如 :

      // 拷贝 3 个元素 ia[2], ia[3], ia[4] 
      vector< int > ivec( &ia[ 2 ], &ia[ 5 ] );


    3. 与内置数组不同 vector 可以被另一个 vector 初始化 或被赋给另一个 vector 例如  
      ```C++

      vector< string > svec; 
      void init_and_assign() 
      { 
           // 用另一个 vector 初始化一个 vector 
           vector< string > user_names( svec ); 
           // ... 
     
           // 把一个 vector 拷贝给另一个 vector 
           svec = user_names; 
      }

       ```

    二、STL习惯用法

    在 STL9中对vector 的习惯用法完全不同。我们不是定义一个已知大小的 vector,而是定义一个空 vector  
    vector< string > text;


    1. 我们向 vector 中插入元素,而不再是索引元素,以及向元素赋值,例如 push_back()操作,就是在 vector 的后面插入一个元素下面的 while 循环从标准输入读入一个字符串序列并每次将一个字符串插入到 vector 中  

    ``` C++

    string word; 
    while ( cin >> word ) { 
    text.push_back( word ); 
    // ... 
    }

    ```

    虽然我们仍可以用下标操作符来迭代访问元素  

    ``` C++

    cout << "words read are: \n"; 
     
    for ( int ix = 0; ix < text.size(); ++ix ) 
          cout << text[ ix ] << ' '; 
     
    cout << endl;

    ``` 
    但是 更典型的做法是使用 vector 操作集中的begin()和 end()所返回的迭代器 iterator  
    对 :

    ```C++
    cout << "words read are: \n"; 
     
    for ( vector<string>::iterator it = text.begin(); 
        it != text.end(); ++it ) 
               cout << *it << ' '; 
     
    cout << endl 


    iterator 是标准库中的类,它具有指针的功能 


    *it; 
    对迭代器解引用,并访问其指向的实际对象  
    ++it;

    向前移动迭代器 it 使其指向下一个元素  

    ```

    2. 注意 不要混用这两种习惯用法, 例如,下面的定义  

    ```C++
    vector< int > ivec; 
    定义了一个空vector 再写这样的语句  
    ivec[ 0 ] = 1024; 
    就是错误的 ,因为 ivec 还没有第一个元素,我们只能索引 vector 中已经存在的元素 size()操作返回 vector 包含的元素的个数 。

    ```

    3. 类似地 当我们用一个给定的大小定义一个 vector 时,例如  :

    ```C++
    vector<int> ia( 10 ); 
    任何一个插入操作都将增加vector 的大小,而不是覆盖掉某个现有的元素,这看起来好像是很显然的,但是 下面的错误在初学者中并不少见 :
    const int size = 7; 
    int ia[ size ] = { 0, 1, 1, 2, 3, 5, 8 }; 
    vector< int > ivec( size ); 
     
    for ( int ix = 0; ix < size; ++ix ) 
        ivec.push_back( ia[ ix ]); 
    程序结束时ivec 包含 14 个元素, ia 的元素从第八个元素开始插入

    ```

      

    转载于:https://www.cnblogs.com/Kernel001/p/7853441.html

    展开全文
  • java中vector和array区别

    2019-09-28 07:43:51
    java中vector和数组非常类似,两者之间也经常成对出现,下面是... 2、vector:对比于array,当更多元素被加入进来以至超出其容量时,vector的size会动态增长,而array容量是定死。同时,vector在删除一些元素后...
  • array和vector的区别

    2020-03-08 23:42:35
    记录一下array和vector的区别
  • vectorarray和数组的区别

    千次阅读 2019-07-23 23:19:22
    三者在内存的方面都使用连续内存,即在vector和array的底层存储结构均使用数组 不同点: vector属于变长容器,即可以根据数据的插入删除重新构建容器容量(1.5倍或者2倍);但array和数组属于定长容量。 ...
  • matlab中vectorarray和matrix的区别

    万次阅读 2015-04-30 14:45:19
    vector:向量,即一维矩阵,用[]或 ,或;...array:数组,可以建立任意尺寸维数,数组建立、存储与矩阵完全相同,乘法用.*,除法区分./.\,幂运算、开方运算是对数组中每个元素分别进行运算。
  • 今天看到mvuRight = vector<float>(N,-1);这段代码不理解于是开始百度把它干掉。 先来说一下vector声明及初始化 vector< int > a; //声明一个int型向量a vector< int > a(10); //声明一个初始大小...
  • 一.C++ 数组 array 和vector联系和区别 相同点: 1.都和数组类似,都可以使用标准数组表示方法来访问每个元素;array和vector都针对下标运算符[]进行了重载 2.三者存储都是使用连续内存,都可以进行随机...
  • 本文基于邓俊辉编著《数据结构(C++语言版)(第3版)》、《C++ Primer(第5版)》以及网上相关博文而写...1、定义初始化内置数组 (1)数组大小不变,(a[d],d为数组维度),数组维度必须是一个常量表...
  • array 和vector的区别

    2007-03-17 12:22:27
    array 长度固定,越界时回报错,可以存储基本类型对象类型,可以通过length属性得到数组长度。 vector长度不固定,长度会自己增加删减,可以通过size()方法获取长度,只能存储对象类型。 所以在用法上选择,只...
  • java中vector,array,list,arraylist的区别

    千次阅读 2017-06-26 23:37:59
    数组其它容器的区别主要有三方面:效率,类型,保存基本类型的能力.在Java中,数组是一种效率很高的存储随机访问对象引用序列的方式.数组是一个简单的线性序列,因此访问速度很快,但也损失了其它一些特性.创建一个...
  • ArrayList 和Vector 都是基于存储元素 object[] array 来实现 他们会在内存中开辟一块连续空间 一 从存储上来说 1)ArrayList Vector ArrayList 初始容量为10 默认扩充容量为原来1.5倍 Vector 默认扩充为...
  • vector和deque的区别

    2021-02-01 14:29:50
    vector概述 vector的数据安排以及操作方式,与array非常相似。...因此,vector的运用对于内存合理利用与运用灵活性有很大帮助,我们再也不必因为害怕空间不足而,一开始就要求一个大块头array了,
  • 一、ArrayList和Vector的区别 ArrayList与Vector主要从以下方面来说. 1.同步性: Vector是线程安全的,也就是说是同步的,而ArrayList是线程序不安全的,不是同步的。 2.操作: 由于Vector支持多线程操作,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 429
精华内容 171
关键字:

vector和array的区别