vector time complexity, emplace_back 정리

vector의 index 접근은 Best할 때 o(1)에 이루어 짐

당연함 -> vector는 vector의 시작점을 가르키기 때문에

시작점 + index로 해당 index를 접근 가능함

 

vector의 끝에 삽입하는 것은 o(1)에 이루어짐 (emplace_back)

 

벡터의 가운데에 삽입하는 것은 o(n)에 이루어 짐.

왜냐하면 가운데에 삽입하는 순간, 뒤에 있는 elements이 n번 move 됨

 

emplace_back 에 클래스를 넣을 때는 cats.emplace_back("cats0", 0); 과 같은 방식으로 넣자.

왜냐하면 cats.emplace_back(Cat("cats0",0))과 같이 넣으면 내부에 이미 Cat이 저장되어 있는데

불필요한 Copy가 일어나기 때문이다.

 

cats.emplace_back(Lvalue) -> Copy

cats.emplace_back(Rvalue) -> Move

 

코드 >>

#include <iostream>
#include <vector>
/// 모든 Case에서 emplace_back을 쓰자!
 
/// Dynamic size
class Cat
{
public:
    explicit Cat(std::string name, int age) : mName{ std::move(name) }, mAge{ age }{};
    void speak() const
    {
        std::cout << "meow~" << mName << mAge << std::endl;
    }
 
private:
    std::string mName;
    int mAge;
};
 
int main()
{
    // 1을 10000개 지정
    // Random access의 접근은 O(1)
    // vector는 시작점을 가르키니까
    // index 기준을 보면 시작점 + 2005 = 3005 index를 찾으면 됨
    // constant 한 time에 접근 가능
    
    
    std::vector<int> nums(10000, 1);
 
    // vector는 첫번째를 가르키니까
    // 10000 + 1 위치에 2를 넣어주면 되므로 o(1)의 time complexity
    // pop_back 또한 10001번째를 제거해주면 된다.
    nums.emplace_back(2);
    nums.pop_back();
 
    // 3이라는 숫자를 맨 앞에 넣어주기 위해서 10000번의 move가 일어남
    // 결국 o(n)의 time complexity
    nums.emplace(nums.begin(), 3);
    // 맨 앞을 지워 줌.
    // 모든 element가 앞으로 move 해야 함
    // 총 10000번의 move가 일어남
    // 즉 o(n)의 time complexity
    nums.erase(nums.begin());
    
 
 
    std::vector<Cat> cats;
    // Not Optimal!
    //cats.emplace_back(Cat{ "cat0",0 });
    //cats.emplace_back(Cat{ "cat1",1 });
    
    cats.emplace_back("cat0",0);
    cats.emplace_back("cat1",1);
    // emplace_back은 reference를 return하게 만들어져 있음
    //Cat& cat = cats.emplace_back(Cat{ "kitty",2 });
    Cat& cat = cats.emplace_back("kitty", 2);
    for (const auto& cat : cats)
    {
    
        
        cat.speak();
    }
 
    Cat nabi{ "nabi", 3 };
    cats.emplace_back(std::move(nabi)); // R Value->move
    cats.emplace_back(nabi); // L Value->Copy
    return 0;
}