c++ list와 vector 비교

실무에서는 99% Vector를 쓴다고 보면 된다.

 

Time Complexity	Find	Random Access	Insertion/Deletion	I/D back
Vector	O(N)	O(1)	O(n)	O(1)
List	O(N)	O(1)	O(1)	O(1)

 

각 연산에 대한 Time complexity를 보면 List가 좋아 보인다.

하지만 메모리는 연속 격자 구조 이기에 Vector가 훨씬 빠르다.

List는 메모리가 여기 저기 흩어져 있다.

그리고 연속 구조가 아니기 때문에 병렬 프로그래밍이 어렵다.

 

List는 emplace back, emplace front 명령이 있고

emplace(iterator, value)로 해당 위치에 value를 입력할 수 있다.

 

그리고 merge와 splice를 활용해서 데이터를 병합하거나 transfer가 가능하다.

 

코드 >>

#include <iostream>
#include <list>
#include <algorithm>
#include <forward_list>
 
std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
    for (auto& i : list) {
        ostr << " " << i;
    }
    return ostr;
}
 
int main()
{
    // nums는 first pointer, last point와 size를 가지고 있음
    // dobule linked list임
 
    //emplace_back, emplace_front time complexity
    //위치가 확실하다면 o(1)에 insertion, delete 가능함
    // splice는 iterator 부터 다른 list에 move 시킴
    // merge는 두 리스트를 합침.
    std::list<int> nums{ 1,2,3,4,5 };
    nums.emplace_back(6);
    nums.emplace_front(0);
    auto it = std::find(nums.begin(), nums.end(), 3);
    if (it != nums.end())
    {
        nums.emplace(it, 100); // 이 경우는 O(n)임
    }
    for (auto num : nums) {
        std::cout << num << " ";
    };
    std::cout << std::endl;
    
    // merge
    std::list<int> list1 = { 5,9,8,1,3 };
    std::list<int> list2 = { 8,7,2,6,4 };
    list1.sort();
    list2.sort();
    list1.merge(list2);
    std::cout << "merged : " << list1 << "\n";
    std::cout << "before merged : " << list2 << "\n";
 
    // splice
    std::list<int> list3 = { 22,3,7,8,5,4 };
    std::list<int> list4 = { 99,6,15,2,3,7 };
    it = list3.begin();
    std::advance(it, 2);
    list3.splice(it, list4);
    std::cout << "list3 : " << list3 << std::endl;
    std::cout << "list4 : " << list4 << std::endl;
 
    list4.splice(list4.begin(), list3, it, list3.end());
    std::cout << "list3 : " << list3 << std::endl;
    std::cout << "list4 : " << list4 << std::endl;
    
    
    //forward_list(single linked list)
    std::forward_list<int> nums_forward{ 1,2,3,4,5 };
    nums_forward.emplace_front(0);
 
    for (auto num : nums_forward)
    {
        std::cout << num << " ";
 
    }
    std::cout << std::endl;
    
    // vector vs list(99%는 vector를 사용해야 빠르다)
    // 메모리 구조가 격자,연속 구조이기에 vector가 훨씬 빠르다.
    // 병렬 연산(8core, 16core)에 vector가 유리함
    // 그러나 list는 core의 개수만큼 데이터 나누기가 어렵다.
    // list는 메모리가 여기저기 흩어져 있다. -> 매우 느리다
    //vector random access o(1), insertion/deletion o(n) I/D back o(1), find o(n)
    // list random access o(n), insertion/deletion o(1) I/D back o(1), find o(n)
    // list가 더 좋아 보이긴 한다
 
    return 0;
}