티스토리 뷰


std::vector를 사용하다보면 많이 사용하는 구문 중 하나는 현재 std::vector가 비어있는지 확인하는 것이다. 이러한 구문을 표현하는 방법이 아래와 두 가지가 있을 것이다.


* std::vector.size() == 0

std::vector<int> myVector;
if (myVector.size == 0)
    printf("Warning: Empty vector");
if (myVector.size > 0)
    printf("Vector is not empty");


* std::vector.empty()

std::vector<int> myVector;
if (myVector.empty())
    printf("Warning: Empty vector");
if (!myVector.empty())
    printf("Vector is not empty");


위의 두 가지는 서로 같은 역할을 수행하는데 이 둘의 차이에 대해서 알아보자. 먼저 일반적으로 개발자들 사이에서 선호되는 방법을 이야기하자면, std::vector.empty()를 사용하는 것이다. 여러 가지 이유를 꼽고 있지만 아래가 가장 대표적인 이유이다.


  1. 가독성이 empty() 함수가 뛰어나다.
  2. size() 함수는 추가 컨디션을 생각해서 작성해야 한다.
  3. empty() 함수는 모든 STL로 구현된 container들 모두에 대하여 O(1)이다.
  4. size() 함수는 특정 container(std::list)는 STL 구현에 따라 O(n)이 될 수 있다.


일단 첫번째 이유는 가독성이 좋기 때문이다. empty()라는 함수 자체는 그 역할을 수행하기 위한 이름의 함수로 정의 되어있기 때문에 소스의 가독성에 size() == 0 과 같이 추가적으로 비교 연산자를 읽어야 하는 수고를 더는 것이 좋기 때문이다. 실제로 소스를 따라가면서 읽다보면 속으로 이렇게 다르게 머리 속으로 분석을 하는 것을 느낄 수 있다.


"벡터의 크기가 0이라면..", "벡터의 크기가 0보다 크다면.."

"벡터가 비어있다면..", "벡터가 비어있지 않다면.."


가독성 자체는 empty()가 조금 더 좋은 것 같기는 하다. 하지만 어떠한 사람들은 아주 크게 개의치 않을거라 생각한다. 개발자들이 empty()를 선호하는 이유 중 두번째로 이야기하는 이유는 가독성과 유사하게 개발자가 작성할 때 어찌되었든 추가로 컨디션을 생각해야 하기 때문이라고 이야기한다. empty()는 함수 호출로 끝나지만 어찌되었든 size() 함수는 호출하고나서 비교 연산자를 추가로 입력해야 하는 부분이다. 물론 이러한 이유들은 다른 것보다도 습관이 어떻게 되었느냐에 따라서 한쪽이 익숙해지고 편해질 수 있다고 생각한다.



가독성 외에 개발자들이 뽑는 이유는 바로 empty() 함수와 size() 함수에 대한 연산 대한 처리 복잡도가 다르기 때문이다. std::vector만을 보면 두 함수 모두 복잡도가 O(1)로 동일하다고 볼 수 있다. 하지만 std::list의 경우에는 empty() 함수는 O(1)이지만, size() 함수는 복잡도가 O(n)이기 때문에 같은 용도이더라도 기본적으로 empty()를 쓰는 것을 습관화 하는 것이 좋다고 한다.


하지만 사실 모던C++에서는 모든 STL container의 size() 함수가 O(1)을 가지는 것으로 표준이 정의 되었다고 한다. 그러면 정말로 그러한지 한번 최신 버전의 gcc 구현 소스를 살펴보고 판단해보자. 먼저 std::vector의 size() 함수와 empty() 함수를 비교해보면 아래와 같다.


[std::vector 구현 소스] - gcc 6.3 기준

https://gcc.gnu.org/onlinedocs/gcc-6.3.0/libstdc++/api/a01641_source.html

  652       // [23.2.4.2] capacity
  653       /**  Returns the number of elements in the %vector.  */
  654       size_type
  655       size() const _GLIBCXX_NOEXCEPT
  656       { return size_type(this->_M_impl._M_finish - this->_M_impl._M_start); }

먼저 std::vector.size() 함수를 살펴보면 메모리에 할당된 마지막 포인터에서 시작 포인터를 빼서 크기를 구하고 있는 것을 확인할 수 있다.


  739       /**
  740        *  Returns true if the %vector is empty.  (Thus begin() would
  741        *  equal end().)
  742        */
  743       bool
  744       empty() const _GLIBCXX_NOEXCEPT
  745       { return begin() == end(); }

반면 std::vector.empty() 는 begin()과 end()를 통해서 iterator를 생성한 다음 비교 연산을 하고 있다. 단순히 std::vector의 size() 와 empty() 함수 자체의 성능을 생각한다면 iterator를 두개 생성해야 하는 empty()의 성능 자체가 조금은 느릴 수 있다고 생각할 수 있을 것 같다. 하지만 일단 두 가지 경우 다 O(1)의 복잡도를 가지고 있다.


그러면 다음에는 std::list의 구현을 살펴보자.


[std::list 구현 소스] - gcc 6.3 기준

https://gcc.gnu.org/onlinedocs/gcc-6.3.0/libstdc++/api/a01627_source.html

  944       // [23.2.2.2] capacity
  945       /**
  946        *  Returns true if the %list is empty.  (Thus begin() would equal
  947        *  end().)
  948        */
  949       bool
  950       empty() const _GLIBCXX_NOEXCEPT
  951       { return this->_M_impl._M_node._M_next == &this->_M_impl._M_node; }
 

먼저 std::list.empty() 함수부터 살펴보면 단순한 노드의 비교를 하고 있으므로 복잡도가 O(1)인 것을 명확히 알 수 있다. 그 다음은 std::list.size() 함수를 살펴보면 아래와 같다.

  953       /**  Returns the number of elements in the %list.  */
  954       size_type
  955       size() const _GLIBCXX_NOEXCEPT
  956       { return this->_M_node_count(); }

여기서 this->_M_node_count() 함수를 따라가보면 아래와 같다.

  349 #if _GLIBCXX_USE_CXX11_ABI
...
  363       // return the stored size
  364       size_t _M_node_count() const { return *_M_impl._M_node._M_valptr(); }
  365 #else
...
  373       // count the number of nodes
  374       size_t _M_node_count() const
  375       {
  376         return _S_distance(_M_impl._M_node._M_next,
  377                            std::__addressof(_M_impl._M_node));
  378       }
  379 #endif

여기서 C++11을 사용한다면 저장 되어있는 값을 리턴하는 것을 확인할 수 있고, C++11을 사용하지 않으면 따로 _S_distance 함수를 호출하는 것을 확인할 수 있다. 마지막으로 _S_distance 함수를 찾아보면 아래와 같다.

  310       static size_t
  311       _S_distance(const __detail::_List_node_base* __first,
  312                   const __detail::_List_node_base* __last)
  313       {
  314         size_t __n = 0;
  315         while (__first != __last)
  316           {
  317             __first = __first->_M_next;
  318             ++__n;
  319           }
  320         return __n;
  321       }

여기서는 루프를 도는 것을 확인할 수 있다. 따라서 C++11 로 컴파일 하지 않으면 std::list.size() 함수는 O(n)의 복잡도로 동작하고 C++11 로 컴파일한다면 O(1)의 복잡도로 동작하는 것을 확인할 수 있다.


따라서 구버전 컴파일러, 예를 들면 gcc 4.6 버전 등의 컴파일러를 이용하거나 C++98 등과의 라이브러리 연동을 위하여 C++11 로 컴파일하지 않는다면 분명히 empty() 함수를 size() 함수보다 더 선호하는 것은 습관적으로 좋다고 볼 수 있을 것이고, C++11 이후에는 가독성이 가장 큰 이유로 empty() 함수를 더 선호하는 것이 좋다고 볼 수 있을 것이다. 물론 세부적으로 어셈블리 한 줄까지도 꼼꼼하게 따지고 들어가기 시작하면 왠지 위의 STL에서 구현한 내용을 보면 size()가 더 효율적이라고 생각할 수 있을 것이다. 그러면 실제로 그런지 어셈블리 소스도 한번 비교해보자.


아래의 두 가지 소스를 만들어서 clang / intel CPU 기준의 어셈블리를 비교해볼 것이다.


[std::vector.size() 소스]

#include <vector>

int main() {
    std::vector<int> myVector;
    if (myVector.size() == 0)
        return -1;
    return 0;
}


[std::vector.empty() 소스]

#include <vector> int main() { std::vector<int> myVector; if (myVector.empty()) return -1; return 0; }


각각에 대하여 컴파일한 어셈블리 결과를 비교해보면 아래의 내용이 다르다.



먼저 좌측이 std::vector.size()이고 우측이 std::vector.empty() 의 결과이다. 소스만 봤을 때에는 empty()함수 안에서는 begin()과 end() 함수를 통해서 내부적으로 iterator()를 생성하는 부분에 대하여 부하가 있을 것 같았지만 실제로 보면 iterator()를 생성하는 과정 없이 바로 그냥 포인터 비교를 하고 있는 것을 확인할 수 있다. 반면 size() 함수는 내부적으로 소스에 있는 그대로 빼기 연산을 하고 그 결과를 다시 0과 비교하는 추가적인 연산을 하고 있는 것을 볼 수 있다. 따라서 최종적으로 보면 함수의 자체 성능만 봐도 std::vector.empty()를 사용해야 하는 이유를 꼽을 수 있다고 볼 수 있다.


따라서 앞으로는 std::vector가 비어있는지 확인하고자 한다면 사소하지만 성능적인 부분과 가독성의 부분에서 더 좋은 std::vector.empty()를 우선적으로 사용하는 것을 습관화 들이면 좋다고 생각한다.



더 읽을 거리

http://stackoverflow.com/questions/3863282/checking-whether-a-vector-is-empty



공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
글 보관함