C++ 中 STL Vector 和 STL List 的區別
本文解釋並演示了 C++ 中 STL vector
和 list
容器之間的主要區別。
確定何時使用 C++ 中的 std::vector
與 std::list
容器
C++ STL 容器通常共享類似的介面來操作元素。儘管如此,還是應該探索這些資料結構的內部差異,為給定的問題選擇最優化的容器。std::vector
函式通常被稱為動態陣列。它在內部自動管理動態記憶體並保持連續儲存的元素類似於 C 型別陣列。後一個特性使得在恆定時間內訪問元素成為可能。
另一方面,std::list
命令實現了一種資料結構,其中元素作為雙向連結串列進行管理。我們按原樣表述前一句是因為 C++ 標準通常不會強制執行確切的實現為雙向連結串列。儘管如此,它還是指定了標準庫實現者需要滿足的某些特徵。
std::list
命令作為模板類提供,儲存類似於 std::vector
的任何型別的物件。我們可以使用 push_back
或 push_front
成員函式將新元素儲存到 std::list
物件中,它們都具有恆定的時間複雜度。至於 std::vector
,我們只有 push_back
,它具有平均常數複雜度。請注意,這些函式用於在給定物件的開頭/結尾新增元素。
下面的示例程式碼演示了上述函式在每種容器型別上的基本用法。
#include <algorithm>
#include <iostream>
#include <list>
using std::cout; using std::endl;
using std::list; using std::vector;
int main() {
vector<int> v = { 1, 2, 13, 84 };
list<int> l = { 1, 2, 13, 84 };
v.push_back(25);
v.push_back(13);
l.push_back(25);
l.push_front(13);
return EXIT_SUCCESS;
}
相反,如果我們想在給定位置插入一個新元素,我們需要利用 insert
成員函式。現在,此操作是 std::list
和 std::vector
之間的主要區別之一。通常,insert
操作對向量
物件的開銷比對列表
物件的開銷更大。
由於向量內容是連續儲存的,每個新插入的元素都會迫使後面的元素向右移動,這取決於向量本身的大小。因此,如果我們需要在物件開頭的中間進行多次插入,我們應該避免使用 vector
容器。如果是後者,我們寧願使用 list
容器,因為一旦位置已知,在列表中的任何位置插入新元素需要恆定的時間。
我們在下一個程式碼示例中演示了插入時間差異,其中兩個容器都用任意 100000
整數初始化,然後我們對每個物件的單個插入操作進行計時。請注意,我們為兩個容器選擇了一個相對中間的位置(39999
),使用 std::search
函式檢索。因此,在 list
的 vector
中插入一個新元素需要數百個因素。
由於元素刪除操作與插入操作類似,與 vector
相比,它在 list
物件上的效率更高。不利的一面是,除了第一個和最後一個元素之外,list
元素沒有固定時間訪問操作。
#include <algorithm>
#include <iostream>
#include <list>
#include <random>
#include <sys/time.h>
using std::cout; using std::endl;
using std::list; using std::vector;
float time_diff(struct timeval *start, struct timeval *end)
{
return (end->tv_sec - start->tv_sec) + 1e-6*(end->tv_usec - start->tv_usec);
}
const int MIN = 1;
const int MAX = 100;
const int CAPASITY = 100000;
int main() {
struct timeval start{};
struct timeval end{};
std::random_device rd;
std::mt19937 eng(rd());
std::uniform_int_distribution<int> distr(MIN, MAX);
vector<int> vec1;
list<int> list1;
vec1.reserve(CAPASITY);
for (int i = 0; i < CAPASITY; ++i) {
if (i % 39999 == 0) {
vec1.push_back(111);
continue;
}
vec1.push_back(distr(eng));
}
for (int i = 0; i < CAPASITY; ++i) {
if (i % 39999 == 0) {
list1.push_back(111);
continue;
}
list1.push_back(distr(eng));
}
auto iter = std::find(vec1.begin(), vec1.end(), 111);
gettimeofday(&start, nullptr);
vec1.insert(iter, 1111);
gettimeofday(&end, nullptr);
printf("insert vector: %0.8f sec\n", time_diff(&start, &end));
auto iter2 = std::find(list1.begin(), list1.end(), 111);
gettimeofday(&start, nullptr);
list1.insert(iter2, 1111);
gettimeofday(&end, nullptr);
printf("insert list : %0.8f sec\n", time_diff(&start, &end));
return EXIT_SUCCESS;
}
輸出:
insert vector: 0.00053000 sec
insert list : 0.00000100 sec
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn