음악, 삶, 개발
vector 안에서 일어나는 일들 본문
vector 에는 요소를 추가, 삭제하는 다양한 함수들이 존재한다.
우리는 그저 무심코 "요소를 추가하면 되고, 삭제하면 되고"라고 생각할것이다.
내가 지금까지 그랬다.
하지만 vector 가 내가 원하는 컨테이너인지 정확히 이해하기위해서,
또한 성능의 향상을 위해서는..
각 함수가 호출되었을때 내부적으로 무슨일이 생기는지를 알고있어야한다.
이 무슨일이 생기는지를 이해하면 다른 컨테이너와 장,단점을 서로 비교할수있게될것이다.
각 함수에 따라 무슨일이 발생하는지를 파해쳐보려한다.
< vector 의 내부 상황을 확인하기위한 함수와 구조체 >
void print(const char* str) {
std::cout << str << std::endl;
}
void print(int n) {
std::cout << n << " 번 호출!" << std::endl;
}
void printResult(const char* str, int a, int b) {
std::cout << str << " 은 " << a << "번의 루프에서 총 " << b << "번의 함수를 호출했습니다" << std::endl;
}
int counter = 0;
bool letsPrint = false;
struct T {
T()
{ if (letsPrint) print("Constructor"); counter++; }
T(const T& other)
{ if (letsPrint) print("Copy Constructor"); counter++; }
T(T&& other) noexcept
{ if (letsPrint) print("Move Constructor"); counter++; }
~T()
{ if (letsPrint) print("~Destructor"); counter++; }
T& operator=(const T& other)
{ if (letsPrint) print("Copy Assignment"); counter++; return *this; }
T& operator=(T&& other) noexcept
{ if (letsPrint) print("Move Assignment"); counter++; return *this; }
};나는 위의 구조체를 스파이로 vector 에게 보낼것이다.
그리고 vector 의 함수들을 실행하며 구조체의 어떤 함수들이 실행되는지 확인할것이다.
클래스의 객체가 생성되거나 파괴될때 사용되는 6가지
Constructor, Copy Constructor, Move Constructor, Destructor, Copy Assignment, Move Assignment
를 정의하였다.
또한 counter 를 사용하여 위의 6가지의 함수가 총 몇번 호출되는지 샐것이다.
void push_back( const T& value );
vector 에 요소를 추가해주는 함수이다.
객체를 인자로 넘겨야하므로 {} 를 사용할것이다.
또한 10개의 요소를 push_back 할것이다.
코드
int main() {
std::vector<T> vec;
int loopLength = 10;
for (int i = 0; i < loopLength; ++i) vec.push_back({});
printResult("push_back", loopLength, counter);
return 0;
}
위의 코드에서 loopLength 를 1 부터 백만까지 변경해보면서 실행해보았다.
push_back 은 1번의 루프에서 총 3번의 함수를 호출했습니다
push_back 은 10번의 루프에서 총 80번의 함수를 호출했습니다
push_back 은 100번의 루프에서 총 868번의 함수를 호출했습니다
push_back 은 1000번의 루프에서 총 7274번의 함수를 호출했습니다
push_back 은 10000번의 루프에서 총 78568번의 함수를 호출했습니다
push_back 은 100000번의 루프에서 총 853042번의 함수를 호출했습니다void emplace_back( Args&&... args );
push_back 처럼 요소를 추가해주는 함수지만,
객체 대신 생성자의 인자를 넘겨야한다.
객체를 vector 내부에서 생성하기때문이다.
이로인해 push_back 보다 성능이 좋은것으로 알려져있다.
나의 클래스 생성자는 따로 인자를 받지않으므로, 그냥 emplace_back() 으로 호출하면된다.
과연 push_back 보다 호출수가 적을까??
코드
int main() {
std::vector<T> vec;
int loopLength = 100;
for (int i = 0; i < loopLength; ++i) vec.emplace_back();
printResult("emplace_back", loopLength, counter);
return 0;
}역시 loopLength 를 1 부터 백만까지 변경해보면서 실행해보았다.
emplace_back 은 1번의 루프에서 총 1번의 함수를 호출했습니다
emplace_back 은 10번의 루프에서 총 60번의 함수를 호출했습니다
emplace_back 은 100번의 루프에서 총 668번의 함수를 호출했습니다
emplace_back 은 1000번의 루프에서 총 5274번의 함수를 호출했습니다
emplace_back 은 10000번의 루프에서 총 58568번의 함수를 호출했습니다
emplace_back 은 100000번의 루프에서 총 653042번의 함수를 호출했습니다
emplace_back 은 1000000번의 루프에서 총 5199506번의 함수를 호출했습니다void reserve( size_type new_cap );
vector 의 공간을 미리 정하는 함수이다.
push_back 이나 emplace_back 을 위해 매우 매우 중요한 함수이다.
vector 는 capacity 가 꽉찬 상태에서 push_back 이나 emplace_back 이
호출되었을때 새로운 메모리를 할당후 모든 요소를 그쪽으로 이동한다.
이때 이런 저런 생성자, 소멸자등이 호출되게된다..
이로인해 우리가 위에 본것처럼
push_back 의 10번 호출이 80번의 호출을.
emplace_back 의 10번 호출이 60번의 호출을 하는것이다.
reserve 를 통해 애초에 capacity 를 크게 설정해놓으면,
vector 에 요소가 추가될때 발생할수있는 재할당 가능성을 줄여줄수있다.
reserve 가 호출되었을때와 호출되지않았을때의 결과를 비교해보자.
push_back 은 1000번의 루프에서 총 7274번의 함수를 호출했습니다
emplace_back 은 1000번의 루프에서 총 5274번의 함수를 호출했습니다위의 결과는 reserve 를 하지않았을때이다.
emplace_back 도 push_back 보다 상황은 낫지만 여전히 굉장히 거대한 호출이다.
1000개의 요소를 넣을 예정이니, 아래오 같이 코드를 작성했다.
int main() {
std::vector<T> vec;
vec.reserve(1000);
int loopLength = 1000;
for (int i = 0; i < loopLength; ++i) vec.push_back({});
printResult("push_back", loopLength, counter);
return 0;
}push_back 은 1000번의 루프에서 총 3000번의 함수를 호출했습니다 // reserve(1000);emplace_back 은?
emplace_back 은 1000번의 루프에서 총 1000번의 함수를 호출했습니다 // reserve(1000);와우 !!!!!!
reserve 와 emplace_back 의 조합은 정말 대단하다.
16GB 램이 대부분인 세상에서, reserve 가 사용자의 컴퓨터에 많은 메모리를 사용하지는않을까?
라는 고민은 하지않는것이 좋을듯하다..
emplace_back 은 충분한 reserve 가 되어있을때 진짜 default constructor 만을 호출한다.
결론
reserve 를 충분히 크게, 그후 emplace_back 으로 요소를 추가하자.
reserve 를 하는 경우와 하지않은 경우의 차이
reserve 를 하지않은 경우 emplace_back 은 무엇을 호출하는가? : Constructor, Move Constructor, Destructor
reserve 를 하는 경우 emplace_back 은 무엇을 호출하는가? : Constructor
reserve 를 하지않은 경우 push_back 은 무엇을 호출하는가? : Constructor, Move Constructor, Destructor
reserve 를 하는 경우 push_back 은 무엇을 호출하는가? : Constructor, Move Constructor, Destructor
push_back 은 reserve 가 되있던 말건 언제나 C, M, D 를 호출한다.
반면 emplace_back 은 reserve 가 되어있을때는 C 만, 아닐때 C, M, D 를 호출한다.
void clear();
vector 의 모든 요소를 제거해주는 함수이다.
먼저, 요소들을 집어넣고 clear() 를 호출한 시점부터 count 를 해보겠다.
코드
int main() {
std::vector<T> vec;
int loopLength = 1000000;
for (int i = 0; i < loopLength; ++i) vec.push_back({});
counter = 0;
vec.clear();
printResult("clear", loopLength, counter);
return 0;
}
clear 은 1000000번의 루프에서 총 1000000번의 함수를 호출했습니다destructor 만이 호출된다. 예상했던 대로이다.
하지만 객체 T 가 여러개의 멤버 변수들을 가지고있다면 이들도 파괴되어야하기때문에
destructor 의 호출은 이에 비례하여 늘어날것이다.
기억해야할것은 vec.size() 만이 줄어들고 늘어난 vec.capacity() 는 줄지않는다는것이다.
capacity 를 줄이기위해서는, vec.shrink_to_fit() 을 호출해야하는데,
이로인해 발생하는 오버헤드에 대해서는 검색을 해보고 이 포스트를 업데이트하겠다.
iterator erase( iterator pos );
iterator erase( const_iterator pos );
erase 는 vector 의 요소를 지워주는 함수이다.
일반적으로 상항하는 vector 의 index 대신, 위치를 가리키는 iterator 를 인자로 넘겨주어야한다.
한개의 iterator 를 인자로 넘기면 해당 요소가 삭제되고
2개의 iterator first, last 를 넘기면 first 요소부터 last 요소의 -1 요소까지 삭제된다. (last 요소까지 아님!!)
어찌보면 이 포스팅을 만든것이 erase 를 통해 잘 설명될것이다.
vector 에서 erase 는 생각보다 매우매우 무거운 작업이기때문이다.
erase 함수의 결과를 print 하기위해 따로 함수를 정의했다.
void printErase(int a, const char* str, int b, int c) {
std::cout
<< a
<< "번의 "
<< str
<< " 호출은 "
<< b
<< "개의 요소를 가진 vector 에서 총 "
<< c
<< "번의 함수를 호출했습니다"
<< std::endl;
}
그리고 실행 코드
int main() {
std::vector<T> vec;
int loopLength = 10;
for (int i = 0; i < loopLength; ++i) vec.push_back({});
counter = 0;
vec.erase(vec.begin() + 1);
printErase(1, "erase", loopLength, counter);
return 0;
}
10개의 요소를 가진 vector 에서 vec.begin() + 1, 즉 2번째 요소를 삭제해보았다.
참고로 vector 는 연결된 메모리를 사용하기때문에 vec.begin() + 1 같이 2번째 요소를 제거하라는
iterator 산술이 가능하다. (모든 컨테이너가 이런 연산이 가능한것이 아니다)
1번의 erase 호출은 10개의 요소를 가진 vector 에서 총 9번의 함수를 호출했습니다뭐지? 난 요소를 1개 지웠을뿐인데, 왜 9번의 함수가 호출됨?
1번의 destructor 만 호출되야하는것이 아닌가?
이것이 우리가 vector 안에서 일어나는 일을 파해쳐봐야하는 이유다.
9번의 함수가 도대체 무엇인지 출력해보았다.
erase 호출할거임!!
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
~Destructor
1번의 erase 호출은 10개의 요소를 가진 vector 에서 총 9번의 함수를 호출했습니다Move Assignment 연산자가 호출되었다.
vector 는 연속적인 메모리를 사용하는 컨테이너다.
따라서 중간 요소가 삭제되면 나머지 요소들이 이 삭제된 요소의 자리를 채우기위해
한칸씩 이동, 즉 Move assignment 를 호출한다.
나는 2번째 요소를 삭제했기때문에, 나머지 8개의 요소가 왼쪽으로 한칸씩 이동하였고
이 이동이 끝난뒤 2번째 요소의 Destructor 가 마침내 호출되어 총 9번의 호출이 일어난것이다.
erase 는 매우 비싼 함수이다.
만약 요소들의 갯수가 매우 크다면?
1번의 erase 호출은 100개의 요소를 가진 vector 에서 총 99번의 함수를 호출했습니다
1번의 erase 호출은 1000개의 요소를 가진 vector 에서 총 999번의 함수를 호출했습니다
1번의 erase 호출은 10000개의 요소를 가진 vector 에서 총 9999번의 함수를 호출했습니다
1번의 erase 호출은 100000개의 요소를 가진 vector 에서 총 99999번의 함수를 호출했습니다
1번의 erase 호출은 1000000개의 요소를 가진 vector 에서 총 999999번의 함수를 호출했습니다이를 보라..
백만개의 요소를 가진 vector 에서 나는 2번째 요소, 즉 한번의 erase 를 호출했을뿐인데
99만번 - 1 의 Move Assignment 호출이 일어난다. (마지막이 Destructor 의 호출)
이러한 고난이 일어나지않으려면 최대한 뒷쪽의 요소를 지워야한다.
vec.erase(vec.end() - 1); // 마지막 요소를 지워다오!1번의 erase 호출은 1000000개의 요소를 가진 vector 에서 총 1번의 함수를 호출했습니다그렇다. 마지막 요소를 지우면 어떠한 다른 요소들은 움직일 필요가 없다.
iterator erase( iterator first, iterator last );
iterator erase( const_iterator first, const_iterator last );
이번에는 first, 와 last 를 통해 10개의 요소중 2개의 요소를 제거해보겠다.
int main() {
std::vector<T> vec;
int loopLength = 10;
for (int i = 0; i < loopLength; ++i) vec.push_back({});
counter = 0;
print("erase 할거임!");
vec.erase(vec.begin() + 1, vec.begin() + 3);
printErase(1, "erase", loopLength, counter);
return 0;
}2번째 요소와 3번째 요소를 제거하는 코드이다.
범위를 정해 요소를 제거하고자할때
범위는 끝은 지울 마지막 요소의 위치 + 1 을 해주어야한다.
따라서 end 가 vec.begin() + 2 가 아니라 vec.begin() + 3 이어야한다.
(이 부분을 항상 명심할것. 마지막 요소 + 1 !!!!)
erase 할거임!
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
Move Assignment
~Destructor
~Destructor
1번의 erase 호출은 10개의 요소를 가진 vector 에서 총 9번의 함수를 호출했습니다다르길 기대했지만 2개의 iterator 를 넘기든 한개의 iterator 를 넘기든
동일한 양의 함수 호출이 발생하였다.
아래의 코드를 보자.
vec.erase(vec.begin(), vec.end() - 2); // 총 10개의 요소에서 8개의 요소를 지웁시다!위의 코드처럼, 요소의 대부분을 지우는 경우라면 차라리 덜 억울할것이다.
Destructor() 가 대부분 호출될것이기때문이다.
erase 할거임!
Move Assignment
Move Assignment
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
~Destructor
1번의 erase 호출은 10개의 요소를 가진 vector 에서 총 10번의 함수를 호출했습니다8개의 요소를 지우려했기때문에, 2개의 요소만이 이동하였고, 나머지 8개의 Destructor 가 호출되었다.
정리를 하면,
erase 는 내가 1000개의 요소중 하나를 지우려한다면,
(1000 - 이 요소의 위치) 만큼의 함수 호출이 발생한다 (Move Assignment)
void pop_back();
vector 의 가장 마지막에 있는 요소를 삭제해주는 함수이다.
가장 뒤의 요소를 지우기때문에, 어떠한 다른 요소들은 전혀 움직일 필요가 없다.
코드
int main() {
std::vector<T> vec;
int loopLength = 1000000;
for (int i = 0; i < loopLength; ++i) {
vec.emplace_back();
}
counter = 0;
vec.pop_back();
printErase(1, "pop_back()", loopLength, counter);
return 0;
}
위의 코드는 백만개의 요소중 가장 마지막 요소를 삭제하는 코드이다.
실행해보면...
1번의 pop_back() 호출은 1000000개의 요소를 가진 vector 에서 총 1번의 함수를 호출했습니다어떠한 객체도 마지막 요소를 삭제할때 움직일 필요가 없으므로,
백만개의 요소를 가진 vector 라 하더라도, 단 1번의 Destructor 호출만이 발생한다.
std::iter_swap(index1, index2);
<algorithm> 안에 포함되어있는 함수이다.
앞서 우리는 erase() 의 비효율성 "하나의 객체를 지우면 나머지 객체가 자리를 채우며 왼쪽으로 이동해야한다" 를 배웠다.
이를 피하기위한 전략은, 내가 지우고자 하는 요소와 마지막 요소를 바꿔치기한후 pop_back() 을 하는것이다.
이 바꿔치기를 해주는것이 iter_swap 함수이다.
일단 간단한 사용예제를 보도록 하자.
#include <vector>
#include <algorithm>
int main() {
std::vector<int> vec {1, 2, 3, 4};
std::iter_swap(vec.begin() + 1, vec.end() - 1);
for (const auto& it : vec) {
std::cout << it << std::endl; // 1 4 3 2
}
return 0;
}위의 코드를 실행해보면,
1, 2, 3, 4 였던 vector 가 1, 4, 3, 2 로 바뀌었다.
iter_swap 은 2개의 iterator 를 인자로 받는데, 바꾸고자하는 2개의 요소를 가리키는 iterator 이다.
이번에는 iter_swap 후, pop_back 을 호출하여,
2번째 요소를 제거하는 코드를 작성해보고 출력해보자.
int main() {
std::vector<int> vec {1, 2, 3, 4};
std::iter_swap(vec.begin() + 1, vec.end() - 1);
vec.pop_back();
for (const auto& it : vec) {
std::cout << it << std::endl; // 1 4 3
}
return 0;
}두번째 요소인 2가 지워지고,
1, 2, 3, 4 에서 1, 4, 3 이 되었다.
여기서 알수있는것은 이 iter_swap 후 pop_back() 은 vector 요소들의 순서를 바꾼다는것이다. (swap 되었기때문에)
따라서 내가 vector 를 정렬할 필요가 없는 상황에서만 사용가능한 방식이다.
우리의 T 클래스를 활용하여, 백만개의 요소에서 이 swap & pop 방식으로 했을때
몇개의 함수가 호출되는지 찍어보았다.
int main(int argc, const char * argv[]) {
std::vector<T> vec;
int loopLength = 1000000;
for (int i = 0; i < loopLength; ++i) {
vec.emplace_back();
}
counter = 0;
std::iter_swap(vec.begin() + 1, vec.end() - 1);
vec.pop_back();
printErase(1, "iter_swap(index1, index2) + pop_back()", loopLength, counter);
return 0;
}1번의 iter_swap(index1, index2) + pop_back() 호출은 1000000개의 요소를 가진 vector 에서 총 5번의 함수를 호출했습니다erase 로 2번째 요소를 지우려했을때 어떻게 되었는지 기억해보자.
1번의 erase 호출은 1000000개의 요소를 가진 vector 에서 총 999999번의 함수를 호출했습니다어마 어마한 차이이다.
하지만 아까 이야기했듯이, 이 방식을 사용하려면
vector 를 순차적으로 정렬할 필요가 없어야하거나, 지금 당장 정렬할 필요가 없을때 가능하다.
