std::forward_list

std::list는 doubly linked list
std::forward_list는 singly linked list이다.

#include <algorithm>
#include <iostream>
#include <forward_list>

int main(int argc, char const *argv[]) {
	std::list<int> nums{1,2,3,4,5};
    nums.emplace_front(0);
    
    for (auto num : nums) {
    	std::cout << num << " ";
    }
    
    std::cout << std::endl;
}

의 메모리를 보면

힙의 원소의 포인터가 다음 원소의 주소만을 가리키는 것을 볼 수 있다.

---

vector와 list의 차이점

vector는 random access가 O(1), list는 삽입,삭제가 O(1)인 차이만 있지만
대부분의 경우 vector를 사용하는 것이 더 빠르다.
find가 둘다 O(n)이지만 실제로는 vector의 find가 더 빠르다

힙 메모리에 저장될 때 vector의 경우 연속되게 저장을 시키기 때문에 다음 값을 한 cache안에 저장이 되지만
list의 경우 포인터로 다른 주소에 나뉘어 있기 때문에 한 cache에 다음 값이 들어가지 못하고, 다음 원소를 보기 위해서 pointer referencing이 계속 필요하므로 느리다.

병렬 프로그래밍시 core의 개수만큼 cache line의 배수로 잘라주면 편하게 프로그래밍이 가능한데
연속되게 저장되어 자르기편한 vector에 비해 list는 자르기가 쉽지않다.