문제에 따라 전체를 한 번에 해결하기보다 같은 유형의 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적이기 때문이다.
→ 복잡한 알고리즘을 단순하고 알기 쉽게 표현할 수 있다.
→ 이를 분할 정복법(Divide & Conquer)이라고 한다.
void reserve(size_t newCapacity) 설명
vector v = { 1, 2, 3, 4, 5 };
// _size == 5
// _capacity == 5
int* iter = v.begirn();
*iter = 10;
++iter;
v.reserve(10);
// 할당이 일어난다.
// 1. 새로운 공간(sizeof(int) * 10)을 할당하고
// 2. 이전 메모리에 있던 데이터를 옮겨온다.
// 이전 메모리를 가리키고 있음.
*iter = 20; //논리 오류가 일어난다.
수업시작
템플릿 - 구글
함수부분 -기본인자
함수를 선언할 떄 기본인자를 전달한다
기봉니자는 는쓰고 값을 적어주면 된다
그러면 후 호출할
일반화프로ㅡ래밍 : 타입에 관계없이 알고리즘을 기훌하는 프로그램
타입도 인자처럼 가질 수 있다 -> c++ 프로그래밍 24page
컴프리 ㅏ파라미터 쓰는 이유 : 제약을 걸어두려고
C++ 프로그래머 : 빌드를 줄이기 위해서 노력함
Vector.cpp
#include <utility>
#include <vector>
#include <iostream>
#include "MyVector.h"
using namespace std;
class MyVector
{
public:
// 기본 생성자
MyVector() = default;
// count만큼 공간이 할당된 생성자
explicit MyVector(size_t count)
: _container(new int[count]), _size(count), _capacity(count)
{
for (size_t i = 0; i < count; ++i)
{
_container[i] = 0;
}
}
// 복사 생성자. 깊은 복사(deep copy)가 이뤄져야 한다.
MyVector(const MyVector& other)
: _container(new int[other._capacity]), _size(other._size), _capacity(other._capacity)
{
for (size_t i = 0; i < _size; ++i)
{
_container[i] = other._container[i];
}
}
// 할당 연산자. 깊은 복사(deep copy)가 이뤄져야 한다.
MyVector& operator=(MyVector& rhs)
{
std::swap(_container, rhs._container);
std::swap(_size, rhs._size );
std::swap(_capacity, rhs._capacity);
return *this;
}
// 소멸자
~MyVector()
{
clear();
}
// 첫 번째 요소를 가리키는 반복자를 반환한다.
int* begin()
{
// 벡터가 비어있다면 end()를 반환
if (empty())
{
return end();
}
// 벡터가 비어있지 않다면 첫 번째 원소를 가리키는 반복자를 반환한다.
return _container;
}
const int* begin() const
{
// 벡터가 비어있다면 end()를 반환
if (empty())
{
return end();
}
// 벡터가 비어있지 않다면 첫 번째 원소를 가리키는 반복자를 반환한다.
return _container;
}
// 마지막 요소의 다음 번째를 가리키는 반복자를 반환한다.
int* end() { return _container + _size; }
// _container : 컨테이너의 주소
// _size : 현재 가지고 있는 원소으 ㅣ개수
// _capacity : 최대 원소의 개수
const int* end() const { return _container + _size; }
// 컨테이너가 비었는지 검사한다.
bool empty() const
{
if (_size == 0)
{
return true;
}
else
{
return false;
}
// return _size == 0; 이거랑 같다. 위 코드
}
// 원소의 개수를 반환한다.
size_t size() const { return _size; }
// 현재 할당된 공간의 크기를 반환한다.
size_t capacity() const { return _capacity; }
// pos에 위치한 원소의 참조를 반환한다.
// vector<int> v;
// v[2];
int& operator[](size_t pos) { return _container[pos]; }
const int& operator[](size_t pos) const { return _container[pos]; }
// 컨테이너의 첫 번째 원소의 참조를 반환한다.
int& front() { return *begin(); }
const int& front() const { return *begin(); }
// 컨테이너의 마지막 원소의 참조를 반환한다.
int& back() { return *(end() - 1); }
const int& back() const { return *(end() - 1); }
// 컨테이너를 비운다.
void clear()
{
delete[] _container;
_container = nullptr;
_size = 0;
_capacity = 0;
}
// pos 이전 위치에 value를 삽입한다.
// value가 삽입된 곳을 가리키는 포인터를 반환한다.
int* insert(int* pos, int value)
{
// 1. 얼만큼 떨어져있는지 확인한다.
int dist = pos - begin();
// 2. 용량을 확인한다.
if (_capacity == 0)
{
reserve(1);
pos = begin() + dist;
}
else if (_size == _capacity)
{
reserve(_capacity * 2);
pos = begin() + dist;
}
// 3. 삽입
for (int* iter = end(); iter != pos; --iter)
{
*iter = *(iter - 1);
}
*pos = value;
// 4. 필드 데이터 최신화
++_size;
return pos;
}
// pos에 위치한 원소를 지운다.
// 삭제된 요소의 다음 포인터를 반환한다.
int* erase(int* pos)
{
// 1. 비어있다면 end() 반환
if (_size == 0)
{
return end();
}
// 2. 데이터 이동(삭제)
int* last = end() - 1;
for (int* iter = pos; iter != last; ++iter)
{
*iter = *(iter + 1);
}
// 3. 필드 업데이트
--_size;
return pos;
}
// 컨테이너의 맨 끝에 원소를 추가한다.
void push_back(int value) { insert(end(), value); }
// 컨테이너의 마지막 원소를 삭제한다.
void pop_back() { erase(end() - 1); }
// value가 존재하는지 검사한다.
bool contains(int value)
{
for (size_t i = 0; i < _size; ++i)
{
if (_container[i] == value)
{
return true;
}
}
return false;
}
// 컨테이너의 용량을 newCapacity보다 같거나 크게 늘린다.
// newCapacity > _capacity라면 새로운 메모리를 할당하고,
// 그렇지 않다면 아무 동작도 수행하지 않는다.
void reserve(size_t newCapacity)
{
// 1. newCapacity가 _capacity 보다 큰지 비교
if (newCapacity <= _capacity) return;
// 2. 새로운 메모리를 할당
int* NewContainer = new int[newCapacity];
// 3. 이전 메모리의 데이터를 복사
for (size_t i = 0; i < _size; ++i) // 데이터복사
{
NewContainer[i] = _container[i];
}
// 4. 이전 메모리 해제
delete[] _container;
// 5. 필드 데이터 수정 _capacity = newCapacity;
_container = NewContainer;
_capacity = newCapacity;
}
private:
int* _container = nullptr;
size_t _size = 0;
size_t _capacity = 0;
};
int main()
{
vector<int> vec;
vector<int> vec2(5);
vector<int> vec3 = { 1, 2, 3, 4, 5 };
vec.push_back(1);
vec.push_back(2);
vec.pop_back();
for (size_t i = 0; i < vec.size(); ++i)
{
cout << vec[i];
}
cout << endl;
vec.pop_back();
cout << boolalpha << vec.empty() << endl;
cout << "Cap : " << vec.capacity() << endl;
vec.reserve(10);
cout << "New Cap : " << vec.capacity() << endl;
vec2.insert(vec2.begin() + 2, 3);
for (size_t elem : vec2)
{
cout << elem << ' ';
}
cout << endl;
vec3.erase(vec3.begin());
for (size_t i = 0; i < vec3.size(); ++i)
{
cout << vec3[i] << ' ';
}
cout << endl;
MyVector mvec;
MyVector mvec2(5);
mvec.push_back(1);
mvec.push_back(2);
mvec.pop_back();
for (size_t i = 0; i < mvec.size(); ++i)
{
cout << mvec[i];
}
cout << endl;
mvec.pop_back();
cout << boolalpha << mvec.empty() << endl;
cout << "Cap : " << mvec.capacity() << endl;
mvec.reserve(10);
cout << "New Cap : " << mvec.capacity() << endl;
mvec2.insert(mvec2.begin() + 2, 3);
for (int elem : mvec2)
{
cout << elem << ' ';
}
cout << endl;
cout << boolalpha << mvec2.contains(2) << endl;
mvec2.erase(mvec2.begin());
for (size_t i = 0; i < mvec2.size(); ++i)
{
cout << vec2[i] << ' ';
}
cout << endl;
}
Vector.h
#pragma once
class MyVector
{
public:
// 기본 생성자
MyVector();
// count만큼 공간이 할당된 생성자
explicit MyVector(size_t count);
// 복사 생성자. 깊은 복사(deep copy)가 이뤄져야 한다.
MyVector(const MyVector& other);
// 할당 연산자. 깊은 복사(deep copy)가 이뤄져야 한다.
MyVector& operator=(const MyVector& rhs);
// 소멸자
~MyVector();
// 첫 번째 요소를 가리키는 반복자를 반환한다.
int* begin()
{
// 벡터가 비어있다면 end()를 반환
if (empty())
{
return end();
}
// 벡터가 비어있지 않다면 첫 번째 원소를 가리키는 반복자를 반환한다.
return _container;
}
const int* begin() const
{
// 벡터가 비어있다면 end()를 반환
if (empty())
{
return end();
}
// 벡터가 비어있지 않다면 첫 번째 원소를 가리키는 반복자를 반환한다.
return _container;
}
// 마지막 요소의 다음 번째를 가리키는 반복자를 반환한다.
int* end() { return _container + _size; }
// _container : 컨테이너의 주소
// _size : 현재 가지고 있는 원소으 ㅣ개수
// _capacity : 최대 원소의 개수
const int* end() const { return _container + _size; }
// 컨테이너가 비었는지 검사한다.
bool empty() const
{
if (_size == 0)
{
return true;
}
else
{
return false;
}
// return _size == 0; 이거랑 같다. 위 코드
}
// 원소의 개수를 반환한다.
size_t size() const { return _size; }
// 현재 할당된 공간의 크기를 반환한다.
size_t capacity() const { return _capacity; }
// pos에 위치한 원소의 참조를 반환한다.
// vector<int> v;
// v[2];
int& operator[](size_t pos) { return _container[pos]; }
const int& operator[](size_t pos) const { return _container[pos]; }
// 컨테이너의 첫 번째 원소의 참조를 반환한다.
int& front() { return *begin(); }
const int& front() const { return *begin(); }
// 컨테이너의 마지막 원소의 참조를 반환한다.
int& back() { return *(end() - 1); }
const int& back() const { return *(end() - 1); }
// 컨테이너를 비운다.
void clear()
{
delete[] _container;
_container = nullptr;
_size = 0;
_capacity = 0;
}
// pos 이전 위치에 value를 삽입한다.
// value가 삽입된 곳을 가리키는 포인터를 반환한다.
int* insert(int* pos, int value);
// pos에 위치한 원소를 지운다.
// 삭제된 요소의 다음 포인터를 반환한다.
int* erase(int* pos);
// 컨테이너의 맨 끝에 원소를 추가한다.
void push_back(int value);
// 컨테이너의 마지막 원소를 삭제한다.
void pop_back();
// value가 존재하는지 검사한다.
bool contains(int value)
{
for (size_t i = 0; i < _size; ++i)
{
if (_container[i] == value)
{
return true;
}
}
return false;
}
// 컨테이너의 용량을 newCapacity보다 같거나 크게 늘린다.
// newCapacity > _capacity라면 새로운 메모리를 할당하고,
// 그렇지 않다면 아무 동작도 수행하지 않는다.
void reserve(size_t newCapacity);
private:
int* _container;
size_t _size;
size_t _capacity;
};