[Effective STL] 4. 빈 컨테이너인지 확인하기

항목 4. size()의 결과를 0과 비교할 생각이라면 차라리 empty를 호출하자

 

 

 

size와 empty의 용법

// size를 사용
if(c.size() == 0)

// empty를 사용
if(c.empty())

 

 

 

empty를 선호해야 하는 이유

• empty는 모든 표준 컨테이너에 대해 상수 시간에 수행되지만..
• list 컨테이너의 경우 간혹 컴파일러에 따라 size가 선형 시간에 수행되기도 하기 때문이다.
  • 이 경우가 꽤 빈번하다.

 

 

 

list가 상수 시간 size를 제공하지 않는 경우, 왜 그럴까.

• 리스트의 splice 함수와 밀접한 관계가 있다.

list<int> list1;
list<int> list2;

...

// list2의 노드 중
// 제일 먼저 5가 나타나는 부분부터
// 제일 먼저 10이 나타나는 부분까지를
// list1의 끝으로 이동시킨다.
// base() 함수는 역방향 iterator를 정방향으로 변경한다.(항목 28 참조)
list1.splice(
    list1.end(), list2,
    find(list2.begin(), list2.end(), 5),
    find(list2.rbegin(), list2.rend(), 10).base()
);

• splice를 호출한 후의 list1에는 요소의 갯수는 얼마나 될까?
  • splice를 호출하기 전 요소 + splice로 옮겨진 요소 만큼일 것이다.
• splice로 인해 list2에서 잘려나간 요소의 갯수는 얼마나 될까?
  • list1에 splice로 옮겨진 요소 만큼일 것이다.
  • 즉, find(list2.begin(), list2.end(), 5) 부터 find(list2.rbegin(), list2.rend(), 10).base() 까지의 갯수
  • 근데 이게 몇 개인지 알고 싶다면?
    • 처음부터 하나씩 횡단해 가면서 세어가지 않는 한 알 방법이 없다.
• 이게 왜 문제인지  list를 구현한다고 가정해보며 알아보자.
  • list는 표준 컨테이너이므로 범용성을 생각해 만들어야 한다.
  • 그러므로 빈번히 사용되는 size를 상수 시간 동작으로 만들고 싶을 것이다.
  • 그러려면 list 내에서 매번 요소 수를 정확히 유지하도록 하면 될 것이다.
  • 하지만, list는 다른 표준 컨테이너와 달리 splice란 함수를 제공한다.
    • 이는 자신의 요소 중 일정 범위를 옮겨버리는 기능이다.
    • 범용성 있는 기능이므로 이 역시 상수 시간 멤버 함수로 만들고 싶을 것이다.
  • 여기서 딜레마가 발생한다.
    • size를 상수 시간으로 만들려면?
      • 리스트의 요소 수에 영향을 주는 다른 멤버 함수 쪽에서 동작할 때마다 리스트 요소 수를 업데이트 해줘야 한다.
      • splice가 선형 시간 동작이 된다.
        
        • 요소 갯수 업데이트를 위해서, 이 때 옮겨지는 노드의 갯수를 알려면 일일이 세어볼 수밖에 없기 때문이다.
    • splice를 상수 시간으로 만들려면?
      
      • size 호출 시 상수 시간으로 전달해줄 저장된 요소 갯수 값을 업데이트 해줄 수 없다.
      • size가 선형 시간 동작이 된다.

 

 

 

정리

• lsit는 컴파일러마다 구현이 다르다.
  • 즉, 컴파일러 개발자가 size와 splice 중 어디에 비중을 두고 있는지에 좌우된다.
• 하지만 empty는 항상 상수 시간 함수이다.
• 그러므로 size() == 0 을 사용하기보다는 empty 를 사용하면 늘 상수 시간을 보장받을 수 있다.