[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
- 배열(Array)
- 벡터(Vector)
- range-based for loop
- Q&A
- 마치며
1. 배열(Array)
- 배열(Array)
: 메모리 상에 원소를 연속하게 배치한 자료구조
ex) int arr[10]
1) 배열의 성질
(1) 원소의 접근 및 수정은 []연산자를 통해 O(1)에 수행
(2) 다른 자료구조와 다르게, 추가적으로 소모되는 메모리의 양(Overhead)가 거의 없음
(3) Cache hit rate가 높음
Cache hit rate는, 캐시된 데이터를 요청할 때 해당 키 값이 메모리에 존재하여 얼마만큼의 비율로 잘 찾았는지에 대한 비율.
(4) 메모리 상에서 연속된 구간을 잡아야 하므로, 할당에 제약
2) 배열의 기능과 구현
(1) 임의의 위치에 있는 원소의 확인 / 변경 : O(1)
(2) 원소를 배열의 끝에 추가 : O(1)
(3) 마지막 원소를 제거 : O(1)
(4) 임의의 위치에 원소를 추가 : O(N)
만약 n번째 위치에 원소를 추가하게 되면, n+1부터 뒤의 칸들은 한 칸씩 밀림.
따라서, 추가하는 위치가 끝에 가까울수록 시간을 줄어들고, 앞에 가까울수록 늘어남
그러면 평균적으로 N/2개를 밀어야하므로 O(N)으로 표현가능함.
void insert(int idx, int num, int arr[], int& len){
for(int i = len; i > idx; i--){
arr[i] = arr[i-1];
}
arr[idx] = num;
len++;
}위의 코드는 insert를 구현한 코드.
배열의 맨 끝부터 하나씩 오른쪽으로 당김.
이 때, i > idx에서 >=이 되면 안됨.
만약, idx가 0일 경우, 밑의 코드에서 arr[0] = arr[-1]이 되기 때문.
(5) 임의의 위치에 있는 원소를 제거 : O(N)
4번과 마찬가지로 n번쨰 원소를 삭제 후 n+1부터 뒤 칸들을 한 칸씩 앞당겨야 함.
그러므로 O(N)
만약 제거 후 당기지 않으면 어떡하나?
-> 메모리 상에서 원소가 연속적으로 존재하지 않으므로 배열이라고 볼 수 없으며, k번쨰 원소를 O(1)에 찾을 수 없게 됨.
void erase(int idx, int arr[], int& len){
for(int i = idx; i < len; i++){
arr[i] = arr[i+1];
}
len--;
}위의 코드는 erase를 구현한 코드.
4번과 마찬가지로 배열의 맨 끝부터 하나씩 오른쪽으로 당김.
3) 사용 팁
(1) 원소 전체를 특정값으로 초기화
(1.1) memset함수 -> 비추천!!!
int a[21];
int b[21][21];
memset(a, 0, sizeof a);
memset(b, 0, sizeof b);cstring 헤더의 memset함수를 이용.
하지만 실수할 여지가 많음.
0이나 -1외의 값을 넣으면 오작동.
2차원 이상의 배열을 인자로 넘겨 그곳에서 memset을 사용하면 실수할 여지가 있음.
(1.2) for문 이용 -> 무난함
int a[21];
int b[21][21];
for(int i = 0; i < 21; i++){
a[i] = 0;
}
for(int i = 0; i < 21; i++){
for(int j = 0; j<21; j++){
b[i][j] = 0;
}
}for문을 이용해 원소 하나하나를 수정하는 방식.
투박하지만 실수할 여지가 없으므로 무난함.
(1.3) fill함수 -> 추천!!!
int a[21];
int b[21][21];
fill(a, a+21, 0);
for(int i = 0; i < 21; i++){
fill(b[i], b[i]+21, 0);
}algorithm헤더의 fill함수를 이용
fill함수는 실수할 여지도 별로 없고, 코드도 짧으므로 추천!
2. 벡터(Vector)
- 벡터(Vector)
: 가변 길이의 배열vector<Type> name; // 1차원 vector<vector<Type>> name; //2차원
1) 생성자
1. vector<int> v;
2. vector<int> v(n); 또는 vector<int> v(n, val);
3. vector<int> v(w); 또는 vector<int> v = w; //단, w는 vector<int>
4. vector<int> v(w.begin(), w.end());
5. vector<int> v{1,2,3}; 또는 vector<int> v = {1,2,3};- 비어있는 벡터를 생성합니다.
- n개의 원소를 갖는 벡터를 생성합니다.
후자는 n개의 원소를 val값으로 초기화합니다. - copy constructor로, 다른 vector와 동일한 벡터를 복사 생성할 때 사용됩니다.
- 다른 컨테이너의 iterator를 받은 후, 순회하며 vector에 해당 범위의 원소를 채워주는 생성자
- initializer_list를 인자로 받는 생성자
2) 멤버 함수
#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
using namespace std;
int main(void) {
fastio;
// v = { 0, 0, 0 }
// t = { 5, 5 }
// w = { { -1, -1, -1 }, { -1, -1, -1 }}
vector<int> v(3), t(2, 5);
vector<vector<int>> w(2, vector<int>(3, -1));
v.push_back(1); // v = { 0, 0, 0, 1 }
v.pop_back(); // v = { 0, 0, 0 }
// insert 2 at v[0], v = { 2, 0, 0, 0 }
v.insert(v.begin(), 2);
// insert { 4, 4, 4 } at v[2], v = { 2, 0, 4, 4, 4, 0, 0, 0 }
v.insert(v.begin() + 2, 3, 4);
// insert [t.begin(), t.end()] at v.begin(), v = { 5, 5, 2, 0, 4, 4, 4, 0, 0 }
v.insert(v.begin(), t.begin(), t.end());
// erase v[4], v = { 5, 5, 0, 4, 4, 4, 0, 0 }
v.erase(v.begin() + 2);
// erase [v[0], v[6]), v= { 0, 0 }
v.erase(v.begin(), v.begin()+6);
cout << "v.size() : " << v.size() << '\n'; // 2
cout << "v.empty() : " << v.empty() << '\n' << '\n'; // 0
v.clear(); // v = { }
v.resize(1); // v = { 0 }
v.resize(3, 2); // v = { 0, 2, 2 }
v[1] = 1; // v = { 0, 1, 2 }
}(1) push_back / pop_back
마지막 위치에 원소를 삽입 / 제거. O(1)
(2) insert / erase
임의의 위치에 원소를 삽입 / 제거. O(n)
O(n)이므로, n이 클 떄 해당 함수들을 여러 번 적용하기는 적합하지 않음.
(3) size / resize
vector의 크기를 size_t 자료형으로 반한
(return값은 unsigend int이므로, v.size() - 1의 연산 시 언더플로우 위험 주의)
vector의 크기를 변경
변경될 크기가 원래의 크기보다 작은 경우, 뒤의 원소부터 차례로 지워지고,
원래의 크기보다 큰 경우, 두 번째 인자가 없는 경우 초기값, 있는 경우는 해당 값으로 남은 칸이 채워짐.
(4) capacity / reserve
vector의 capacity를 size_t 자료형으로 반한
(return값은 unsigend int이므로, v.capacity() - 1의 연산 시 언더플로우 위험 주의)
vector의 capacity를 변경
reserve를 잘 이용하면 메모리를 절약할 수 있음.
: 만약 size와 capacity가 각각 6일 때, 하나의 원소를 추가해보자.
size는 7이 되지만, size는 capacity보다 클 수 없기 때문에 capacity가 늘어난다.
이 때 capacity는 자동적으로 1.5 ~ 2배 정도 늘어난다. 그러면 12가 될 것이다.
그러나 남은 공간 5(12 - 7)은 사실 필요가 없는 공간이다.
따라서 reserve(7)로 해주면 size도 만족하고, 용량도 절약할 수 있다.
(capacity는 vector의 원소들을 담을 수 있는 메모리가 할당되어 있는 공간의 용량, size는 실제 유효 원소들의 개수)
(5) empty
vector가 비어져 있는지 bool자료형으로 반환
(6) clear
vector의 모든 원소를 삭제
(7) begin / end
vector의 첫번째 원소를 가리키는 iterator 반환
vector의 마지막 원소의 다음 칸을 가리키는 iterator 반환
iterator(반복자)는 포인터처럼, 자료구조의 원소를 가리키는 자료형.
(8) rbegin / rend
begin의 reserve_iterator 버전
end의 reserve_iterator 버전
(9) front / back
v[0]을 reference로 반환
v[n-1]을 reference로 반환
빈 vector에서 둘을 호출하는 것은 'UB(Undefined Behavior)'
3. range-based for loop
vector<int> v = {1,2,3,4,5,6};
// 1. ranged-based for loop (since C++11)
for(int e : v) { cout << e << ' '; }
for(int& e: v) { cout << e << ' '; }
// 2. not bad
for(int i = 0; i < v.size(); i++) { cout << v[i] << ' '; }
// 3. **Wrong**
for(int i = 0; i <= v.size() - 1; i++) { cout << v[i] << ' '; }
}1번의 방법은 C++11부터 적용가능한 range-based for loop
위의 방법은 v의 각 원소의 복사값이 e에 들어감. 따라서 for문 내에서 e를 바꿔도 원본 v에는 아무런 영향이 없음
그러나 아래의 방법은 v의 각 원소의 참조를 통해 e에 들어감. 따라서 for문 내에서 e를 바꾸면 원본 v의 값이 바뀜.
이 방법은 나중에 배울 list, map, set에도 지원.
만약 위 방법이 익숙치 않으면, 2번 3번을 사용해도 됨.
그러나 3번처럼 사용하면 안됨.
vector의 size는 unsigned int나 unsigned long long을 반환함
만약 v가 빈 벡터일 경우, unsigned int 0에서 1을 뺴는 것이므로, -1이 아닌 4294967295이 됨. unsigned int overflow가 발생함.(런타임에러)
4. Q&A
-
5. 마치며
-
[Reference] : 위 글은 다음 내용을 제가 공부한 후, 인용∙참고∙정리하여 만들어진 게시글입니다.
