배열 & STL vector

배열

• 임의의 원소를 확인하고 변경, O(1)
• 원소를 끝에 추가, O(1)
• 마지막 원소 제거, O(1)
• 임의의 위치에 있는 원소를 추가, O(n)
• 임의의 위치에 있는 원소를 제거, O(n)

구현

#include <iostream>
using namespace std;

class Array
{
private:
  int *arr; // 배열
  int arrSize; // 배열의 크기
  
public:
  Array(int sz) // 생성자
  {
    this->arrSize = sz; // 배열읰 크기 초기화
    this->arr = new int[arrSize]; // 크기가 sz인 배열 동적 할당
    
    for(int i=0; i < sz; i++) // 배열 요소를 모두 0으로 초기화
    {
      arr[i] = 0;
    }
  }
  
  int at(int idx) // 해당 index에 저장된 요소 출력
  {
    return arr[idx]; 
  }
  
  void add(int idx, int value) // 임의의 위치에 원소를 추가
  {
    for(int i = arrSize-2; i >= idx; i--)
    {
      arr[i+1] = arr[i];
    }
    arr[idx] = value;
  }
  
  void set(int idx, int value) // 배열에 값 할당
  {
    arr[idx] = value;
  }
  
  void print() // 요소 출력
  {
    for(int i=0; i < arrSize; i++)
    {
      cout << arr[i] << " ";
    }
    cout << endl;
  }
  
  void remove(int idx) // 임의의 위치에 있는 원소 제거
  {
    for(int i = idx+1; i < arrSize; i++)
    {
      arr[i-1] = arr[i];
    }
    arr[arrSize-1] = 0;
  }
}

배열 사용 팁

• 인덱스 전체를 모두 어떤 특정값으로 초기화시킬 때 어떻게 초기화할 수 있는 알아보자.

1. for문을 돌면 값을 하나하나 다 바꾸기

for(int i=0; i < 21; i++)
{
 a[i] = 0;
}

2. algorithm 헤더의 fill 함수

fill(a, a+21, 0);
for(int i = 0; i < 21; i++)
  fill( b[i], b[i]+21, 0);

---

STL vector

• 배열과 거의 동일한 기능을 수행하는 자료구조

• 배열과 마찬가지로 원소가 메모리에 연속적으로 저장되있기 때문에 O(1)에 인덱스를 가지고 각 원소를 접근 가능.

• 배열과 달리, 크기를 자유자재로 늘리거나 줄일 수 있다.

• 수용 공간이 꽉차면 공간(capacity)를 이전보다 2배로 크게 새로운 공간을 할당시키고, 그곳에다 기존 요소들을 복사함

• < vector > 헤더파일 선언해야함

• 선언형태 : vector<데이터 타입> 변수이름

---

메소드

insert, erase : 배열에서 구현한 것 처럼 O(n)
push_back, pop__back : 제일 끝에 원소를 추가하는 것이므로 O(1)
push_front, pop_front : 제일 앞에 원소를 추가하거나 빼므로 O(n)

• push_back(a) : 맨 뒤에 원소 a 추가

• v1.begin() : 맨 앞 원소를 가리킴 (iterator 과 사용)

• v1.rbegin() : reverse begin을 가리킨다(거꾸로 해서 첫번째 원소를 가리킴) / iterator와 사용

• v1.end() : 마지막의 "다음"을 가리킴 (iterator 과 사용)

• v1.pop_back() : 마지막 원소를 제거

• v1.assign(a,b) : b의 값으로 a개의 원소 할당

• v1.at() : idx번째 원소를 참조 (v[idx]보다 속도는 느리지만, 범위를 점검하므로 안전하다)

• v1[idx] : idx번째 원소를 참조 (범위를 점검하지 않으므로 v.at(idx)보다 빠르다)

• v1.front() : 첫번째 원소를 참조

• v1.back() : 마지막 원소를 참조

• v1.clear() : 모든 원소를 제거 / 원소만 제거하고 메모리는 남아있다. / size만 줄어들고 capacity 는 그대로 남아있다.

• v1.size() : 원소의 갯수를 리턴

• v1.capacity() : 할당된 공간의 크기를 리턴

• v1.insert(a,b,c) : a번째 위치에 b개의 c값을 삽입한다.

• v1.insert(a,b) : a번째 위치에 b 값을 삽입

• v1.erase(iter) : iter가 가리키는 원소를 제거한다.

• v1.empty() : 비어있으면 true 리턴 / 비어있다의 기준은 size가 0이라는 것이지, capacity와는 상관이없다.

• v1.resize(n) : 크기를 n으로 변경 / 더 커졌을 경우 default 값인 0으로 초기화한다

• v1.resize(n,3) : 크기를 n으로 변경 / 더 커졌을 경우 인자의 값을 3으로 초기화한다.

• v2.swap(v1); : v1과 v2의 원소와 capacity를 바꿔줌 (모든 것을 스왑해줌)

---

vector의 size 와 capcity의 관계

v.size() : 원소를 개수를 리턴
v.capacity() : 할당된 공간의 크기를 리턴 / 공간 할당의 기준은 점점 커지면서 capcity 를 할당하게 된다.

*capacity : 할당된 메모리의 개수(크기) / size : 할당된 메모리 안에 요소가 들어있는 개수

• capacity를 2배로 늘리는 이유 : push_back 이 일어날 때마다 동적할당을 하면 비효율적이므로, 미리 정해둔 만큼 동적할당을 한번에 하는 것이다.

• 예를들어 string 클래스로 vector를 만들었을 때 아래처럼 capcity(공간)이 늘어난다.
  원소 개수1 : capacity 1
  원소 개수2 : capacity 2
  원소 개수3 : capacity 4
  원소 개수4 : capacity 4
  원소 개수5 : capacity 8
  원소 개수6 : capacity 8
  원소 개수7 : capacity 8
  원소 개수8 : capacity 8
  원소 개수9 : capacity 16

#include <bits/stdc++.h>
using namespace std;

int main(void){
  vector<int> v1(3,5); // {5,5,5}
  cout << v1.size() << '\n'; // 3
  
  v1.push_back(7); // {5,5,5,7};
  
  vector<int> v2(2); // {0,0};
  v2.insert(v2.begin()+1, 3); // {0,3,0}
  
  vector<int> v3 = {1,2,3,4};
  v3.erase(v3.begin()+2);
  
  vector<int> v4;  // {}
  v4 = v3; // deepCopy 복사 수행. 추후에 v4를 바꿔도 v3에 영향을 주지 않는다.
  cout << v4[0] << v4[1] << v4[2] << '\n'; 
  v4.pop_back(); // 맨뒤 원소제거
  v4.clear(); // 싹 비워버림
  

vector 의 for문 활용

• 3번처럼 vector.size() 메소드가 unsigned int를 리턴해서 for문에서 활용하면 안된다는 점만 유의하자.

vector<int> v1 = {1,2,3,4,5,6};

// 1. range-based for loop
for(int e: v1)  // e에 v1원소들이 하나씩 들어가는 for문
  cout << e << ' '; // int e 면 복사본이 들어가고, int& e면 원본이 들어감. 
  // 2번은 for문 내에서 e를 바꾸면 원본인 v1에서 실제 해당 원소 값이 바뀜
  
// 2. 평소 하던 방법
for(int i=0; i < v1.size(); i++)
  cout << v1[i] << ' ';
  
// 3. 잘못된 표현
// 기본적으로 vector의 size메소드는 unsigned int를 반환한다.
//  그렇기 때문에 따라서 3번같이 쓰면 v1이 
// 빈 vector 일때 v1.size() - 1 이 unsigned int 0에서 int 1을 빼는 식이 되고,
// unsigned int로 자동 형변환이 되서 (unsigned int)0 - (int)1 은
// -1 이 아니라 4294967295가 된다. (unsigned int overflow 발생) => 무한루프 발생 
for(int i=0; i <= v1.size()-1; i++)
  cout << v1[i] << ' ';

---

정렬 메소드 sort( )

• < algorithm > 헤더의 sort( ) : 배열또는 vector 를 오름차순으로 정렬해줌

오름차순 형식 : sort(arr, arr+10); / sort(v1.begin( ), v1.end( ) )

내림차순 형식 : sort(v.begin(), v.end(), greater< int >( ) );
=> 표준라이브러리 내에 있는 greater() 라는 비교 함수를 마지막 파라미터로 전달

벡터 정렬

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(void){
  vector<int> v = {4, 7, 2 ,5, 10, 8, 1, 6 3};
  cout << "정렬 전:";
  for(int i=0; i < v.size(); i++){
   cout << v[i] << " ";
  }
  cout <<< endl;
  
  sort(v.begin(), v.end()) // sort() 정렬
  
  cout << "정렬 후: ";
  for(int i=0; i < v.size(); i++){
    cout << v[i] << " ";
  }
  cout << endl;
  return 0;
}

배열 정렬

#include <iostream> 
#include <algorithm> 
using namespace std; 
int main() { 
	int arr[10] = { 9, 4, 7, 2, 5, 10, 8, 1, 6, 3 }; 
    cout << "정렬 전: "; 
    for (int i = 0; i < 10; i++) { 
    	cout << arr[i] << " "; 
    } 
    cout << endl; 
    sort(arr, arr + 10); 
    cout << "정렬 후: "; 
    for (int i = 0; i < 10; i++) { 
    	cout << arr[i] << " "; 
    } 
    cout << endl; 
    return 0; 
}