std::array의 단점

• std::array의 크기는 컴파일 시간에 결정되는 상수, 프로그램 실행 중 변경 불가
• 크기가 고정되어 있어서 원소를 추가하거나 삭제할 수 없음
• 메모리 할당 방법 변경 불가, 항상 스택 메모리 사용

std::vector - 가변 크기 배열

• 벡터 초기화 예시

// 크기가 0인 벡터 선언
std::vector<int> vec;

// 지정한 초깃값으로 이루어진 크기가 5인 벡터 선언
std::vecotr<int> vec = {1, 2, 3, 4, 5};

// 크기가 10인 벡터 선언
std::vector<int> vec(10);

// 크기가 10이고, 모든 원소가 5로 초기화된 벡터 선언
std::vector<int> vec(10, 5);

• 벡터에 새로운 원소 추가: push_back() 또는 insert()
  • insert(): 삽입할 위치를 나타내는 반복자를 첫 번째 인자로 받아서 원하는 위치에 원소 추가
  • push_back(): 자주 사용되는 연산, 매우 빠르게 동작

    push_back(val):
      if size < capacity  // 새 원소를 추가할 공간이 있는 경우
        - 마지막 원소 다음에 val 저장
        - 벡터 크기를 1만큼 증가
        - return;
        
      if vector is already full  // 할당된 메모리 공간이 가득 차 있는 경우
        - 2*size 크기의 메모리를 새로 할당
        - 새로 할당한 메모리로 기존 원소 전부를 복사/이동
        - 데이터 포인터를 새로 할당한 메모리 주소로 지정
        - 마지막 원소 다음에 val을 저장하고, 벡터 크기를 1만큼 증가

  • 뒤쪽에 남아 있는 공간이 있다면 O(1)
  • 공간이 충분하지 않으면 모든 원소를 복사/이동해야 하므로 O(n): 이런 경우는 많지 않으므로 push_back() 연산의 평균 시간 복잡도는 O(1)에 가까움
  • insert() 함수는 지정한 반복자 위치 다음의 모든 원소를 이동시켜야 하고, 필요 시 메모리도 새로 할당해야 하므로 O(n)의 시간 소요
  • 벡터는 push_front() 함수를 지원하지 않으므로 맨 앞에 새로운 원소를 추가하려면 원소 삽입 위치를 인자로 받는 insert() 함수를 사용해야 함
    
    
• 벡터 원소 추가 예제 코드

std::vector<int> vec;  // 비어 있는 벡터 생성: {}

vec.push_back(1);  // 맨 뒤에 1 추가: {1}

vec.push_back(2);  // 맨 뒤에 2 추가: {1, 2}

vec.insert(vec.begin(), 0);  // 맨 앞에 0 추가: {0, 1, 2}

vec.insert(find(vec.begin(), vec.end(), 1), 4);  // 1 앞에 4 추가: {0, 4, 1, 2}

• push_back()과 insert()의 단점: 추가할 원소를 임시로 생성한 후 벡터 버퍼 내부 위치로 복사 또는 이동 수행

• emplace_back() / emplace(): 새로운 원소가 추가될 위치에서 원소를 생성 -> 성능 향상

• 벡터 원소 제거: pop_back() 또는 erase()

  • pop_back(): 벡터 맨 마지막 원소 제거 -> 벡터 크기 1만큼 감소 => 시간 복잡도는 O(1)
  • erase(): 반복자를 인자로 받아 해당 위치 원소 제거 -> 특정 위치 원소 삭제 후, 뒤쪽 원소를 모두 앞으로 이동해야 하므로 O(n)

• 벡터 원소 제거 예제 코드

#include <iostream>
#include <vector>

using namespace std;

void print(vector<int> vec)
{
    for (auto& i : vec)
    {
        cout << i;
    }

    cout << endl;
}

int main()
{
    vector<int> vec = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    print(vec);

    // 맨 마지막 원소 하나 제거: {0, 1, 2, 3, 4, 5, 6, 7, 8}
    vec.pop_back();
    print(vec);

    // 맨 처음 원소 제거: {1, 2, 3, 4, 5, 6, 7, 8}
    vec.erase(vec.begin());
    print(vec);

    // 2번째 원소부터 5번째 앞 원소까지(4번째 원소까지) 제거: {1, 5, 6, 7, 8}
    vec.erase(vec.begin() + 1, vec.begin() + 4);
    print(vec);
}

• 그 외 유용한 std::vector 멤버 함수
  • clear(): 모든 원소를 제거하여 완전히 비어 있는 벡터로 만듦
  • reserve(capacity): 벡터에서 사용할 용량을 지정, 매개변수로 지정한 값이 현재 용량보다 크면 메모리를 매개변수 크기만큼 재할당, 매개변수 값이 현재 용량보다 같거나 작으면 아무런 동작을 하지 않음
  • shrink_to_fit(): 여분의 메모리 공간을 해제하는 용도로 사용, 이 함수를 호출하면 벡터의 용량이 벡터 크기와 같게 설정, 벡터 크기가 더 이상 변경되지 않을 때 사용하면 유용

std::vector 할당자

• 템플릿 매개변수에서 데이터 타입 다음에 할당자 전달
• 할당자 함수
  • allocate(): 할당
  • deallocate(): 할당 해제
  • construct(): 초기화되지 않은 공간에 요소를 저장
  • destroy(): 객체 소멸
    • destroy() 호출 없이 deallocate() 호출 시 사라진 객체가 가리키던 객체가 메모리에 남아있어 메모리 릭(memory leak) 발생 가능

백준 4153번

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    vector<vector<int>> matrix;

    while(true)
    {
        int line_1, line_2, line_3;
        cin >> line_1 >> line_2 >> line_3;

        if (line_1 == 0) break;
        else
        {
            vector<int> vec = {line_1, line_2, line_3};
            matrix.push_back(vec);
        }
    }

    for (auto &vec : matrix)
    {
        sort(vec.begin(), vec.end());

        int longest_square = vec[2] * vec[2];
        int short1_square = vec[0] * vec[0];
        int short2_square = vec[1] * vec[1];
        
        if (longest_square == short1_square + short2_square)
        {
            cout << "right" << endl;
        }
        else
        {
            cout << "wrong" << endl;
        }
    }

    return 0;

}