C++——STL中三种顺序容器的简要差别

时间:2021-04-10 05:37:20

C++ STL 提供了3个顺序容器 :vector, deque, list

Vector动态数组。支持高速訪问;list双向链表,支持高速插入和删除。

vector 中的元素是顺序存放的。所以随机訪问非常快,可是要插入和删除,这个时间复杂度就非常高了,vector初始化时有一个capacity,假设元素个数超出capacity,那vector就会又一次分配一个新的空间。并把旧值拷贝到新的空间中,释法原空间,这个也要耗费非常多时间,所以假设你知道元素的最大值,最好用reserve()函数初始最大空间,避免又一次分配空间造成的时间。

Deque是双端队列,差点儿全部的操作都和vector一样,出了能够在头加入和删除,多了个push_front(), pop_front()。仅仅有Vector和Deque有下标操作符,list没有。

list 是双链表,元素在内存中是分散的不连续的,它使用指针left,right,指向前一个元素和后一个元素。

所以要删除和加入仅仅要动动指针。所以非常快。可是由于是不连续的所以要訪问一个元素,你仅仅能遍历序列。

$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('

    ').addClass('pre-numbering').hide();
    $(this).addClass('has-numbering').parent().append($numbering);
    for (i = 1; i ').text(i));
    };
    $numbering.fadeIn(1700);
    });
    });