1강 배열: C 스타일 배열과 std::array
1. 배열
가. 배열이란?
- 같은 종류의 데이터가 연속적으로 저장되어 있는 자료 구조
- 다섯 학생의 점수를 저장하는 방법
나. 배열의 특징
- 인덱스(index)를 사용하여 원하는 원소(element)에 곧바로 접근 가능: O(1) (상수 시간)
- 캐시 지역성 (cache locality)
- 배열의 각 원소는 서로 인접해 있기 때문에 하나의 원소에 접근할 때 그 근방에 있는 원소도 함께 캐시(cache)로 가져옴 -> 인접해있는 원소에 연속적으로 접근할 경우, 빠르게 접근할 수 있음
- 반복문에서 배열을 사용하면 효율적인 프로그래밍이 가능
- 상수 또는 상수표현식으로 크기를 지정(크기 불변)
- VLA(Variable-length array): 변수로 배열의 길이를 지정할 수도 있음. 하지만 일반적으로는 변수로 배열의 크기를 지정하는 것은 바람직하지 않다고 봄. 그래서 C++에서는 VLA이 표준 X, 상수 형태로만 지정해야한다.
- 스택 메모리 영역에 할당 → 보통 1MB 할당
- 너무 큰 크기의 배열을 사용할 경우 스택 오버플로우라는 에러가 발생하면서 프로그램 종료될 수도 있음
2. C 스타일 배열
가. C 스타일 배열 예제 코드
#include <iostream>
using namespace std;
int main()
{
int scores[5] = {50, 60, 70, 80, 90}; // 1. 배열 생성
int sz = sizeof(scores) / sizeof(scores[0]); // 3. sizeof 함수를 사용해 배열의 엘리먼트의 크기를 알아낼 수 있다
// int sz = size(scores); 4. c++ 17에서 제공하는 size라는 함수를 이용해서 배열의 엘리먼트 개수를 알아낼 수 있다
int s = 0;
for (int i = 0; i < sz; i++){
s += scores[i]; // 배열의 값에 접근하기 위해 대괄호 연산자 사용
}
float m = (float)s / sz;
cout << "Mean scores: " << m << endl;
}
나. C 스타일 2차원 배열
3. std::array
가) std::array 란?
- C++에서 C 스타일 배열을 대체하는 고정 크기 컨테이너 (C++11부터 지원)
- 원소의 타입과 배열 크기를 매개변수로 사용하는 클래스 템플릿 (원소의 타입과 배열의 크기를 지정해줘야 한다)
- <array> 헤더 파일에 정의되어 있다.
template <class T, std::size_t N>
class array
{
public:
T data[N]; // 데이터 타입 T에 대한 N개짜리 데이터가 저장
T& operator[] (int index) // 대괄호 연산자에 대한 연산자 오버로딩이 되어있다.
{
return data[index]; // C 언어의 배열과 비슷한 방식으로 array 객체르 사용할 수 있음
}
};
나. std::array 특징
- C 스타일 배열처럼 사용할 수 있는 [] 연산자 오버로딩을 제공
- 대입 연산자 지원 (깊은 복사)
- 대입 연산자를 이용해서 서로 다른 array 객체를 = 연산자를 이용해서 깊은 복사를 할 수 있다.
- 배열 크기를 정확하게 알 수 있음. array::size()
- 반복자 지원
다. std::array 예제 코드
#include <array>
#include <iostream>
using namespace std;
int main()
{
array<int, 5> scores = {50, 60, 70, 80 , 90}; // array 사용 위해서는 #include <array> 필수
int s = 0;
for (int i = 0; i < scores.size(); i++) { // size 멤버함수 사용 가능
s += scores[i];
}
float m = (float) s / scores.size();
cout << "Mean scores: " << m << endl;
}
라. std::array 단점
- 배열의 크기를 명시적으로 지정해야 함
- 항상 스택 메모리를 사용 (대용량 데이터 저장 X)
- 사람들은 고정 크기 배열이 아닌 가변 크기 배열을 더 선호함
2강 동적 배열과 std::vector
1. 동적 배열
가. 동적 메모리 할당 (dynamic memory allocation)
- 프로그램 실행 중 필요한 크기의 메모리 공간을 할당하여 사용하는 기법
- 필요한 크기: 프로그램을 실행할 때마다 가변적으로 사용할 수 있는 크기
- 예: 이미지 편집 프로그램 사용시 작은 이미지를 편집할 때도, 큰 이미지를 편집할 때도 있음. 각각의 이미지 크기에 맞는 메모리 공간을 할당해야지만 좀 더 효율적으로 메모리 사용 가능
- 동적으로 할당된 메모리는 사용이 끝나면 명시적으로(사용자가 직접) (할당된) 메모리를 해제해야 함
- C 언어: malloc() 또는 calloc() 함수로 메모리 할당하고, free() 함수로 메모리 해제
- C++ 언어: new 연산자로 메모리 할당하고, delete 연산자로 메모리 해제
- C++ 에서도 malloc, calloc, free 사용은 가능함. 단 추천은 X
나. 동적 메모리 할당을 이용한 동적 배열 생성 및 해제
- new[] 연산자를 이용하여 동적 배열을 위한 메모리를 할당하고, delete[] 연산자를 이용하여 동적 배열 메모리를 해제
int* ptr = new int[3];
// ptr을 배열처럼 사용. (e.g.) ptr[0], ptr[1], ptr[2]
delete [] ptr;- 후에는 반드시 delete + []로 ptr이 가리키고 있는 메모리 공간을 할당해줘야 한다.
- 대괄호를 안써도 에러는 안나지만 할당할 때 대괄호를 사용했으면 해제할 때도 반드시 대괄호 연산자를 사용해야 함
- 동적메모리 할당은 힙(heap) 메모리 영역을 사용하므로 대용량 배열도 할당 가능
다. 동적 배열 예제 코드
#include <iostream>
int main()
{
int n;
std::cin >> n;
// 동적 배열 할당 및 초기화
int* ptr = new int[n] {};
ptr[0] = 10;
ptr[1] = 20;
// ptr을 배열처럼 사용
for (int i = 0; i < n; i++) {
std::cout << ptr[i] << std::endl;
}
//동적 배열 해제
delete [] ptr;
}
라. 메모리를 자동으로 해제하는 동적 배열 클래스
#include <iostream>
using namespace std;
class dynamicArray_test
{
private:
unsigned int sz;
int* arr;
public:
explicit dynamicArray_test(int n) : sz(n){ // explicit: 묵시적 형변환을 방지 하기 위해. 생략 가능
arr = new int[sz] {}; // 생성자: 메모리 생성
}
~dynamicArray_test() { delete [] arr; } // 소멸자: 메모리 해제
unsigned int size() { return sz; }
int& operator[] (const int i) { return arr[i]; }
const int& operator[] (const int i) const { return arr[i]; }
};
int main()
{
dynamicArray_test da(5); // int {} 벗어나면 사라짐. -> delete 자동 실행
da[0] = 10;
da[1] = 20;
da[2] = 30;
for (int i = 0; i < da.size(); i++)
cout << da[i] << ", ";
cout << endl;
}
마. 템플릿으로 구현한 동적 배열 클래스
#include <iostream>
using namespace std;
template <typename T> // 다양한 자료형에 대한 동적 할당 가능
class DynamicArray
{
private:
unsigned int sz;
T* arr;
public:
DynamicArray(int n) : sz(n) {
arr = new T[sz] {};
}
~DynamicArray() { delete [] arr; }
unsigned int size() { return sz; }
T& operator[] (const int i) { return arr[i]; }
const T& operator[] (const int i) const { return arr[i]; }
};
int main()
{
DynamicArray<int> da(5); // 템플릿 인자값 줘야한다.
da[0] = 10;
da[1] = 20;
da[2] = 30;
for (int i = 0; i < da.size(); i++)
cout << da[i] << ", ";
cout << endl;
}
2. std::vector
가. std::vector 란?
- C++에서 C 스타일 배열을 대체하는 가변 크기 컨테이너
- 가변 크기: 중의적 의미, 배열 크기를 상수 아닌 정수로 지정할 수 있음 + 배열 크기가 고정이 아닌 확장 가능ㅇ
- 원소의 타입을 매개변수로 사용하는 클래스 템플릿
- <vector>에 정의되어 있음
3강 std::vector 사용법과 동작 방식
1. std::vector 사용법과 동작 방식
가. std::vector 객체 생성과 원소 참조
#include <iostream>
#include <vector>
using namespace std;
int main()
{
// 벡터 생성
vector<int> v1; // int 값을 저장할 비어 있는 벡터 생성
vector<int> v2(20); // int 값 10개를 저장할 벡터 생성하고 0으로 초기화
vector<int> v3(10, 1); // int 값 10개를 저장할 벡터 생성하고 1로 초기화
vector<int> v4{10, 20, 30, 40, 50}; // 유니폼 초기화 (uniform initialization)
vector<int> v5(v4); // v4를 복사하여 v5 생성
vector<int> v6(v4.begin(), v4.begin() + 3); // v4의 청므 3개 원소를 이용하여 v6 생성
// 벡터 원소 참조
for (int i = 0; i < v6.size(); i++)
cout << v6[i] << endl;
}
나. std::vector를 이용한 2차원 벡터 생성과 원소 참조
// 정수형 2차원 배열. 2행 3열. 0으로 초기화
vector<vector<int>> mat1(2, vector<int>(3, 0));
// 유니폼 초기화
vector<vector<int>> mat2{{1, 2, 3,}, {4, 5, 6}};
//2차원 벡터 출력
for (int r = 0; r < mat2.size(); r++) {
for (int c = 0; c < mat2[r].size(); c++) {
cout << mat2[r][c] << " ";
}
cout << endl;
}
}
다. std::vector 주요 멤버 함수와 기능
라. std::vector::push_back() 동작 방식
마. std::vector::insert()와 std::vector::erase() 동작 방식
바. std::vector 사용 예제
int main()
{
vector<int> vec1 {1, 2, 3, 4};
cout << vec1.capacity() << ":" << vec1.size() << endl;
vec1.push_back(5);
cout << vec1.capacity() << ":" << vec1.size() << endl;
vec1.push_back(6);
cout << vec1.capacity() << ":" << vec1.size() << endl;
vec1.insert(vec1.begin(), 0);
cout << vec1.capacity() << ":" << vec1.size() << endl;
vec1.erase(vec1.begin() + 1, vec1.begin() + 3);
cout << vec1.capacity() << ":" << vec1.size() << endl;
for (int i = 0; i < vec1.size(); i++
cout << vec1[i] << ", ";
}
사. std::vector 주요 멤버 함수와 기능
4장 주요 모던 C++ 문법은 자료구조와 알고리즘에 상관 없는 내용이므로 정리를 생략함
'3학년 > 자료구조와 알고리즘 스터디' 카테고리의 다른 글
| [자료구조와 알고리즘] 6장 재귀 (1) | 2023.05.21 |
|---|---|
| [자료구조와 알고리즘] 5장 큐 (0) | 2023.05.15 |
| [자료구조와 알고리즘] 4장 스택 (1) | 2023.05.09 |
| [자료구조와 알고리즘] 3장 연결 리스트 (0) | 2023.04.11 |
| [자료구조와 알고리즘] 1주차 개요, 시간 복잡도 (1) | 2023.03.26 |
