this.code(1).DS_ Array & Vector (STL) (★★★★★★)

※ Array (배열)

※ 1차원 배열

배열은 주로 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다.

예를 들어 a0, a1, a2, a3, a4, a5라는 6개의 정수형 변수를 A[6]으로 간단하게 선언할 수 있다.

 

배열의 가장 기본적인 특징은 <인덱스, 요소> 쌍의 집합으로 인덱스를 이용한 직접접근이 가능하다는 것이다.

이때, 배열과 대응되는 개념으로 연결리스트를 공부한다.

- 배열: index를 이용해서 원하는 요소에 직접접근이 가능

- 연결리스트: 맨 처음요소부터 하나씩 순차적으로 찾아가야 원하는 요소에 접근할 수 있다. (순차접근, sequential access)

 

배열의 특징은 index를 건너뛸 때 마다 배열의 자료형의 크기만큼 건너뛴다.

Ex) int arr[6]; 은 int형 배열인데, arr[0] => arr[1]로 건너뛴다면 sizeof(int) = 4byte 만큼 건너뛰게 되는 것이다.

 

단! 이때, 문자열에 대한 배열은 조심해야 한다.

문자열 선언방식은 char str[12]와 같이 하는데 이때, str은 문자열 배열의 변수이름이며

문자열의 마지막 index에는 '\0'이 들어간다! ('\0'은 ASCII값의 0을 뜻하며 즉, NULL을 의미한다.)

따라서 char str[12] = "game is over"는 ['g'] ['a'] ['m'] ['e'] [' '] ['i'] ['s'] [' '] ['o'] ['v'] ['\0'] 처럼

str[11]에 '\0' 값이 들어가 최종적으로 game is ov까지만 배열에 들어가게 된다.

 

 

 

※ 2차원 배열

1차원 배열이 여러개 모여서 이루어진 것이다.

int arr[3][4]의 경우를 해석하자면 [4]개의 1차원 배열이 [3]개 있다고 생각하면 된다.

[ ] [ ] [ ] [ ]     <=  4개짜리 배열

[ ] [ ] [ ] [ ] 

[ ] [ ] [ ] [ ]

 

 

 

 

 

※ 포인터와 참조자로 배열 나타내기

※ 1차원 배열

arr[4] = *(arr + 4)

int arr[4];       int (&ref)[4] = arr;

 

※ 2차원 배열

arr[3][4] = *(arr+3)[4]  =  *(arr[3] + 4)  =  *(*(arr+3)+4)

 

 

 

※ 매개변수로 배열의 길이 전달하기

int findMacVal(int arr[], int len){
    int max = arr[0];
    for (int i = 1; i < len; i++) {
        if (max < arr[i])
            max = arr[i];
    }
    return max;
}


int main() {
    int arr_len = 0;
    cin >> arr_len;
    int arr[arr_len];
    for (int i = 0; i < arr_len; i++) {
        cin >> arr[i];
    }

    int MaxVal = findMacVal(arr, arr_len);
    cout << MaxVal << endl;
}

- 배열의 이름이 포인터 역할을 하기에 함수 호출 시 배열의 이름을 매개변수로 전달하면 호출되는 함수에서는 이 주소를 이용해 배열의 모든 요소들을 접근할 수 있다.

- 이때, 배열의 길이도 매개변수로 함께 전달해야 한다.

 

이는 2차원 배열도 마찬가지로 2차원 배열은 가로크기가 5일 때만 적용가능한 함수가 되어버린다.

int findMacVal(int arr[][5], int h, int w){
    int max = 0;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (max < arr[i][j])
                max = arr[i][j];
        }
    }
    return max;
}

 

Q. 만약 배열의 길이를 모르거나 매개변수로 전달하기 싫다면 어떻게 해야하나요?

 

A. Vector 클래스를 배열대신 사용한다면 가능하다.

 

 

 

※ array container (std::array) _ 고정크기배열

- memory를 자동으로 할당하고 해제하며 원소의 타입과 배열크기를 매개변수로 사용하는 템플릿클래스이며

다음과 같이 사용할 수 있다.

#include <iostream>
#include <array>
using namespace std;

int main(){
    array<int, 3> arr1;
    arr1[0] = 1;
    cout << arr1[0] << endl;

    array<int, 5> arr2;
    for(int i=0; i < arr2.size(); i++){
        cin >> arr2[i];
    }
    for (int i = 0; i < arr2.size(); i++) {
        cout << arr2[i] << ' ';
    }
}

 

위의 std::array에서는 배열원소에 접근할 때 [ ]를 사용했는데, arr.at() 함수를 사용해서 접근할 수도 있다.

출처) https://computer-science-student.tistory.com/80?category=1163589

arr.at() 함수를 이용한 접근은 아래와 같이 할 수 있다.

 

 

 

 

※ std::array를 매개변수로 하는 배열출력함수

[최대값 찾기]

#include <iostream>
#include<array>
using namespace std;

template<size_t N>

void MaxVal(array<int, N> arr){
    int max = 0;
    for (auto element : arr) {
        if (element > max)
            max = element;
    }
    cout << max;
}


int main() {
    array<int, 5> arr = { 1, 5, 3, 8, 2 };
    MaxVal(arr);
}

 

 

※ std::array 멤버함수 정리

https://computer-science-student.tistory.com/80?category=1163589

 

 

 

 

 

 

 

 

 

 

※ STL Container

STL에서 컨테이너(container)는 같은 타입의 여러 객체를 저장하는 일종의 집합이라 할 수 있습니다.

- 컨테이너 변수 선언 시, 컨테이너에 포함할 요소의 타입 명시가 가능.

- 컨테이너에는 복사 생성과 대입을 할 수 있는 타입의 객체만을 저장가능.

- 컨테이너는 요소의 추가 및 제거 등 다양한 작업을 도와주는 여러 멤버 함수를 포함한다.

 

먼저 STL에서 컨테이너는 자료를 저장하는 방식과 관리하는 방식에 따라  3가지 형태가 있다.

1. sequence container (시퀀스 컨테이너)

2. associative container (연관 컨테이너)

3. adapter container (컨테이너 어댑터)

출처) http://www.tcpschool.com/cpp/cpp_container_intro

이 중에서 우리는 시퀀스 컨테이너의 vetor에 대해서 알아볼 것이다.

 

 

 

 

 

 

 

 

 

 

※ vector container (std::vector) _가변배열

C++의 STL에 내장되어 있는 템플릿 클래스로 배열과 유사하며 Java의 ArrayList와 비슷한 기능을 한다.

배열에 여러가지 기능을 추가한 것으로 기존의 배열에서 불편했던 점을 개선하여 일반화 시킨 것이다.

 

- 벡터 컨테이너는 동적배열의 클래스 템플릿이다.

- 벡터 객체는 요소가 추가,삭제될 때 마다 자동으로 메모리를 재할당해 크기를 동적으로 변경한다.

- 임의의 위치에 있는 원소 접근과, 뒤에서 원소를 추가하는 연산은 O(1)  (분할상환분석)을 보장한다.

 

- vector<x> 타입 vec이 소요하는 메모리는 대략 sizeof(vector<X>) + vec.size()*sizeof(X)이다. (약 12byte)

 

 

 

 

 

※ vector 선언방법

#include <vector>
using namespace std;

vector<자료형> 변수명(숫자)    //숫자만큼 벡터 생성 후 0으로 초기화
vector<자료형> 변수명(숫자, 변수1);   //숫자만큼 벡터 생성 후 변수1으로 모든 원소 초기화
vector<자료형> 변수명{숫자, 변수1, 변수2, 변수3, ...};    // 벡터 생성 후 오른쪽 변수 값으로 초기화
vector<자료형> 변수명[]={ {변수1, 변수2}, {변수3, 변수4}, ...}   //2차원 벡터생성 (열은 고정, 행 가변)
vector<vector <자료형>> 변수명   //2차원 벡터생성 (열, 행 가변)

ex);
vector<int> vec1; // 크기가 0인 벡터 선언
vector<int> vec2(10); // 크기가 10인 벡터 선언
vector<int> vec3(10, 3); // 크기가 10이고 모든 원소가 3으로 초기화된 벡터
vector<int> vec4 = { 1,2,3,4,5 }; // 크기가 지정한 초기값으로 이루어진 벡터
vector<int> vec5[] = { {1,2},{3,4} }; // 벡터 배열 생성(행은 가변인지만, 열은 고정)
vector<vector<int>> vec6; // 2차원 벡터 생성(행과 열 모두 가변)

 

 

 

 

 

※ vector 요소 삽입, 제거, 변경

-  insert(), push_back() 같은 삽입연산자는 많은경우 list보다 vector에 좀 더 효율적이다.

#include <vector>
using namespace std;

int main() {
    vector<int> vec; // 크기가 0인 벡터 선언

    vec.push_back(10);
    vec.push_back(20); // vec = {10, 20}

    vec.insert(vec.begin() + 1, 100);  // vec = {10, 100, 20}

    vec.pop_back();       // vec = {10,100}

    vec.emplace_back(1);   // vec = {10, 100, 1}
    vec.emplace_back(2);   // vec = {10, 100, 1, 2}
    vec.emplace(vec.begin() + 2, -50); // vec = {10, 100, -50, 1, 2}

    vec.erase(vec.begin() + 1);    // vec = {1, -50, 1, 2}
    vec.resize(6); // vec = {1, -50, 1, 2, 0, 0}
    vec.clear();   // vec = empty()
}

 

※ vector의 복사생성자와 move

- Default: push_back()은 값을 넣을 때, 복사생성자를 호출한다. 이는 insert()도 새 메모리에 복사 후 넣는다.

- 이로인해 복사생성자로 인한 오버헤드가 커지고, 성능저하가능성이 있다.

=> 그래서 push_back()과 insert() 대신 emplace_back()과 emplac() 함수를 사용한다. (생성자만 호출)

 

 

 

 

 

 

 

※ vector의 iterators

vec.begin()	벡터 시작점의 주소값 반환
vec.end()	벡터 (끝부분+1) 주소값 반환
vec.rbegin()	벡터의 끝지점을 시작점으로 반환
vec.rend()	벡터의 (시작+1)을 끝부분으로 반환

 

 

※ vector의 index 접근

vec.at(i)	벡터의 i번째 요소 접근 (범위 검사O)
vec[i] (operator [])	벡터의 i번째 요소 접근 (범위 검사X)
vec.front	벡터의 첫 번째 요소 접근
vec.rend	벡터의 마지막 요소 접근

 

 

 

 

 

 

※ vec.at(i)와 vec.[i]의 차이점

- at은 범위를 검사하여 범위 밖의 요소에 접근 시 예외처리를 발생시킨다. (std::out_of_range)

- [ ]은 범위검사를 하지 않으며 예외처리를 발생시키지 않는다. (범위 밖 요소에 접근하면 디버깅 발생)

 

vector는 효율에 중점을 두기에 보통 [ ]를 권장한다.

 

 

 

 

 

 

※ vector의 크기 size, capacity

- size: vector의 크기, 즉 벡터에 실제로 저장된 원소의 개수를 뜻한다.

- capacity: vector의 용량, 즉 벡터의 최대 할당 크기를 뜻한다.

 

만약 벡터의 크기가 용량을 초과한다면 재할당이 발생한다. (기존 값 새 메모리에 복사 후 파괴)

if (size > capacity) {
    reallocate <- 모든 값 새 메모리에 복사 후 기존 벡터 파괴
}

 

Problem 1. 새 메모리의 복사과정에서 복사생성자가 발생해 성능이 저하될 수 있다.

Solution 1. reserve()라는 함수를 사용해서 벡터의 용량을 충분히 크게 생성할 수 있다.

 

Problem 2. reserve()를 너무 크게 잡으면 벡터가 불필요하게 늘어나 메모리를 많이 차지할 수 있다.

Solution 2. clear()로 벡터의 값을 지울 때, 벡터의 요소를 삭제할 수 있다.

 

Problem 3. clear()로 벡터의 요소는 없어지지만 capacity는 그대로 남아있다.

Solution 3. 이를 해결하기 위해 swap()을 사용하는데 이는 아래와 같다.

 

#include <vector>
using namespace std;

int main() {
    vector<int> vec = { 1,2,3,4,5 };
    vec.clear();
    cout << vec.capacity() << endl;  // 5 출력
    vector<int>().swap(vec);
    cout << vec.capacity() << endl;  // 0 출력
}

 

 

 

※ vector와 string  [  vector<char>    vs   string  ]

- vector<char>: char타입의 원소로 이루어진 시퀀스

- string: 문자시퀀스를 저장하는 것이 목적, 따라서 string은 문자열을 정렬하는 경우가 거의 없다. (string의 의미성이 소멸)

 

 

 

 

※ vector는 언제 사용하는게 좋을까?

- 크기 변경이 가능할 때

- 순차 접근이 가능할 때

- 랜덥 접근이 가능할 때

 

단점) 중간 삽입과 삭제가 용이하지 않기에 삽입과 삭제가 빈번할 경우, vector보다는 list나 deque를 사용하는 것이 낫다.

크기 변경 가능	O
중간 삽입, 삭제	X
순차 접근 가능	O
랜덤 접근 가능	O

 

 

 

 

 

 

※ Array vs Vector vs Linked List

 

 

 

 

 

출처 및 참고사이트) https://computer-science-student.tistory.com/83