C++에서 STL 벡터와 STL 목록의 차이점
이 기사에서는 C++에서 STL vector및list컨테이너 간의 주요 차이점을 설명하고 보여줍니다.
C++의std::list컨테이너와 반대로std::vector를 사용할시기 결정
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의 주요 차이점 중 하나입니다. 일반적으로삽입작업은list객체보다vector객체에서 더 많은 비용이 듭니다.
벡터 내용이 연속적으로 저장되기 때문에 새로 삽입 된 각 요소는 벡터 자체의 크기에 따라 다음 요소가 오른쪽으로 이동하도록합니다. 따라서 객체 시작 중간에 많은 삽입을 수행해야하는 경우vector컨테이너를 사용하지 않아야합니다. 후자의 경우 위치가 알려지면 목록의 아무 곳에 나 새 요소를 삽입하는 데 일정한 시간이 걸리므로list컨테이너를 사용하는 것이 좋습니다.
두 컨테이너가 임의의100000정수로 초기화 된 다음 코드 예제에서 삽입 시간 차이를 보여준 다음 각 개체에 단일 삽입 작업 시간을 지정합니다. std::search함수로 검색된 두 컨테이너에 대해 상대적으로 중간 위치 (39999)를 선택했습니다. 결과적으로list의vector에 새 요소를 삽입하려면 수백 개의 요소가 필요합니다.
요소 제거 작업은 삽입과 유사하므로vector에 비해list개체에서 더 효율적입니다. 단점은list요소에는 첫 번째 요소와 마지막 요소를 제외하고는 일정한 시간 액세스 작업이 없습니다.
#include <sys/time.h>
#include <algorithm>
#include <iostream>
#include <list>
#include <random>
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 Facebook