✍️Today I Learned

1. Vector vs Deque
2. 맨 앞에 원소를 추가/삭제 하는 경우
3. 임의 접근을 하는 경우
4. 정렬이 필요없는데 정렬을 하는 경우
5. 특정 원소를 찾는 경우
6. 문자열을 결합하는 경우
7. auto& vs auto

---

Vector vs Deque

덱(deque)

1. 벡터의 단점을 보완하기 위해 만들어진 컨테이너이다.
2. 벡터는 원소 삽입 시 용량이 부족하면 메모리를 재할당하여 이전 원소를 복사하는 방식
3. 덱은 메모리가 부족할 때 일정한 크기의 새로운 메모리 블록을 할당한다.(이전 원소 복사X)

덱의 구조
맨 앞의 원소와 맨 뒤의 원소를 가리키는 포인터가 있고, 내부적으로 데이터는 여러 개의 청크로 쪼개져있다. 임의 접근을 효율적으로 할 수 있다.

벡터와 덱의 메모리 전략 차이
벡터: 메모리가 연속적이다.
덱: 각 청크들 끼리는 메모리가 연속적이지 않다.

---

맨 앞에 원소를 추가/삭제 하는 경우

🔸벡터의 경우

• 뒤에 있는 원소들을 전부 이동시킴 -> O(N)

🔸덱의 경우

• 청크를 나눠서 관리 -> O(1)

👉 맨 앞의 원소를 추가하거나 삭제하는 경우 덱을 사용해야 한다.

임의 접근을 하는 경우

벡터와 덱 모두 점근적 상한 기준으로는 O(1)

🔸덱의 경우

• 불연속적인 청크를 내부적으로 map이 관리하지만 데이터가 커지면 맵을 통해 청크 위치를 찾고 접근하는데 필요한 연산 횟수가 증가하여 성능차이가 커진다.

👉 임의 접근을 빈번하게 하는 경우 벡터를 사용해야 한다.

정렬이 필요 없는데 정렬하는 경우

key순으로 정렬할 필요가 없는데 map을 사용하는 경우

🔸map의 경우

• 내부가 레드-블랙 트리 구조. key값으로 자동 정렬한다. 삽입/삭제/탐색 -> O(log N)

🔸unordered_map의 경우

• 내부가 해시 구조. key값으로 정렬하지 않는다. 삽입/삭제/탐색 -> O(1)

👉 정렬할 필요가 없는 경우 unordered 컨테이너를 사용한다.

특정 원소를 찾는 경우

🔸벡터의 경우

• 특정 데이터에 접근하려면 해당 데이터의 인덱스를 통해 임의 접근해야 한다. 인덱스에는 데이터에 대한 정보가 없기 때문에 순차탐색을 해야한다. -> O(N)

🔸set과 map의 경우

• 레드-블랙 트리로 데이터를 관리한다. 탐색 -> O(log N)

🔸unordered_set과 unordered_map의 경우

• unordered가 붙는 컨테이너는 해시 기반으로 데이터를 관리한다. 탐색 -> O(1)

문자열을 결합하는 경우

🔸+ 연산자의 경우

• +연산자로 문자열을 결합하는 경우 매번 새로운 문자열을 다시 만든다. -> O(N)

🔸+= 연산자와 append() 메서드의 경우

• 매번 새로운 문자열을 만들지 않고 기존 문자열에 덧붙이는 방식이다. -> O(1)

👉 문자열 결합이 빈번하게 일어난다면 + 연산자는 절대 사용하면 안된다.

auto& vs auto

🔸auto 의 경우

• 매번 복사가 일어난다. -> O(N)

🔸auto& 의 경우

• 복사하지 않고 레퍼런스로 받는다. -> O(1)

👉 데이터가 큰 경우 auto&로 레퍼런스로 받아와야 한다.