std::list만 sort가 따로 있는 이유

std::list란

---

std::list는 C++ 표준 라이브러리의 연결 리스트 컨테이너이다.

각 노드들이 메모리에 연속적으로 붙어있지 않고, 이전/다음 노드를 가리키는 포인터로 연결되어 있다.

핵심 특징

---

• 임의 접근 불가: list[i] 같은 인덱스 접근이 안 됨
  -> 원하는 위치를 찾으려면 앞에서부터 탐색해야 함 O(N)
• 삽입/삭제가 빠름: 특정 위치의 iterator를 알고 있다면, 포인터만 바꾸면 됨
  -> 삽입/삭제 자체는 O(1)
• iterator/reference 안정성: 삽입/삭제를 해도 다른 원소를 가리키는 iterator나 reference가 보통 유지됨
• 메모리/캐시 효율이 낮음: 노드마다 포인터(2개)같은 오버헤드가 있고, 메모리가 힙 영역에 흩어져 있어 캐시 히트율이 낮음

그렇다면 언제 쓰나?

---

• 어디에 삽입/삭제할지 위치(iterator)를 이미 알고 있고, 중간 삽입/삭제가 빈번할 때
• 원소를 자주 옮기지 않고, splice 같은 기능이 유용할 때

언제 피하나?

---

• 인덱스로 자주 접근해야 할 때 (std::vector, std::deque를 사용)
• 단순히 앞/뒤 삽입/삭제만 필요할 때 (std::deque가 더 유리)
• 원소 순회가 빈번하고 성능이 중요할 때 (Cache Hit가 낮음)

사용 예시

---

#include <list>
#include <iostream>

int main() {
    std::list<int> lst = {1, 2, 3};

    auto it = lst.begin();
    std::advance(it, 1);      // 2를 가리킴(여기까지 O(N))
    lst.insert(it, 10);       // 2 앞에 10 삽입(O(1))

    for (int x : lst) std::cout << x << ' '; // 1 10 2 3
}

std::sort

---

std::sort는 <algorithm>에 있는 범위 정렬 알고리즘이다.

std::sort(first, last) 또는 std::sort(first, last, comp) 형태로 사용한다.

sort를 사용하기 위해서는 정렬할 범위의 iterator가 Random Access가 가능해야 한다.
-> O(1) 만에 K번 원소에 접근이 가능해야 한다는 뜻

일반적으로 O(NlogN)의 시간 복잡도가 소요된다.

사용 예시

---

std::vector<int> v = {3,1,2};
std::sort(v.begin(), v.end()); // 1,2,3

std::list에 sort 함수가 따로 있는 이유

---

위의 std::list와 std::sort 설명을 보고나면 왜 std::list가 <algorithm>의 sort를 사용하지 않고 자체 sort 함수가 있는지 알 수 있다.

std::list는 연결 리스트이기 때문에 iterator가 앞/뒤 이동만 가능하고, iterator + n 같은 Random Access가 불가능하기 때문이다.

그렇기 때문에 std::list는 멤버 함수로 list.sort()를 제공하고 있다.

list.sort()는 보통 merge sort를 기반으로 구현되며, 값을 복사/이동해서 재배치하는 것이 아닌, 노드 포인터 연결만 바꾸는 방식이다.

정리

---

• std::sort: Random Access가 가능한 컨테이너용 정렬 함수
• list.sort: Random Access가 불가능한 list에 맞게, 노드 연결을 이용한 정렬 함수