1. Array, vector, list
std::Array std::vector std::list > 선형
트리, 그래프 > 비선형
c#의 list가 c++의 vector와 대응한다.
list는 임의 접근 안됨. radom access안 됨.
2. vector 구현
가장 많이 쓰고 가장 많이 써야한다.
cache friendly하기 때문에 삽입/삭제시도 잘 구현/활용 하면 O(1)로 동작을 한다.
resize(), reserve() 차이점 ❗
reserve는 capacity를 조절하는 것이고,
resize는 size를 조절하는 것이기 때문에 => 데이터 갯수를 막바로 조절하게 된다.
reserve(100) -> resize(10)
이렇게 해버릴 경우는??
capacity는 변하지않고 size만 변함
data 100 넣고 -> resize(1) ? ❗
데이터가 10개만 남고 capacity는 그대로이다.
데이터가 10개만 유효하고 나머지 다 날라감.
3. linked List
using iterator = Iterator<T>https://jungmonster.tistory.com/323
이거 참고하면은 될듯?
중간 삽입 삭제가 빠르다 ??
ㄴㄴ.
실제로 삭제하거나 삽입은 O(1)맞기는 한데
Random Access접근이 안되기 때문에 원하는 데이터를 찾으러가는데
O(n)이다. ㅋㅋ.
거의 99%는 vector 써라.
std::list는 또한 cache friendly하지 않다.
4. Stack
LIFO
끝이다.
top()은 peek()같은 개념이고 pop을 해야 꺼내오고 사라짐.
(C#은 pop하면 반환하는 값으로 추출을 함)
구현
template <typename T>
class Stack
{
public:
void push(const T& v)
{
_c.push_back(v);
}
void pop()
{
_c.pop_back(); // 실제로 꺼내서 없앰
}
T& top()
{
return _c.back(); // reference 반환함.
}
bool empty() { return _c.empty(); }
int size() { return _c.size(); }
private:
vector<T> _c;
};이게다임.
이런식으로 Stack에 쓰일 container adaptor를 이런식으로 설정을 해줄 수 도 있을 것이다.
표준은 deque를 통해서 구현되어있다.
C++에서는 성능관련 이슈 때문에 top()을하고 pop()을 한다.
5. Queue
FIFO
front()를 통해 데이터를 꺼내고 pop을 통해 없앰. stack이랑 똑같다.
int main()
{
std::queue<int> q;
for (int i = 0; i < 100; ++i)
{
q.push(i);
}
while (q.empty() == false)
{
int value = q.front();
q.pop();
std::cout << value << " " << q.size() << std::endl;
}
int size = q.size();
std::cout << size << " " << std::endl;
}
실행하면 결과가 이렇게 나옴.
문제점 ❗
Queue를
내부 멤버 변수를 Container를 vector로 사용하면
pop의 경우 어떻게 구현을 할껀가? Time Complex O(n)의 시간이 걸린다.
Order Of (n)
그래서 그냥 내부 멤버 변수 컨테이너를 list로 하고 pop에서는 _container.pop_front를 해버리면 일단은 상관은 없음.
std::deque ❗
여기 참고바람.
https://blockdmask.tistory.com/73
앞뒤로 삽입 삭제가 가능하기 때문에 stack, queue의 기반 자료구조는 deque이다.
array로 queue만들기 ❗
테크닉을 키우는데 좋기 때문에 array로 queue를 만들어보도록 하겠다.
일단 이상태로 시작을 할 것이다.
front 랑 back을 사용해서 유효범위를 사용하면 vector의 단점을 좀 보완할 수가 있다.
이런식으로 사용을 할 것인데
처음에 잡아 놓은 사이즈를 벗어나면 어떻게 해야하나??
꽉차면은 back이 제일 앞으로 와가지고 계속 이어서 진행을 하면은 된다.
template <typename T>
class ArrayQueue
{
public:
void push(const T& v)
{
// 다 찼는지 체크
if (_size == _container.size())
{
// 증설
int newSize = max(1, _size * 2);
vector<T> newData;
newData.resize(newSize);
for (int i = 0; i < _size; ++i)
{
int index = (_front + i) % _container.size();
newData[i] = _container[index];
}
_container.swap(newData);
_front = 0;
_back = _size;
}
_container[_back] = v;
_back = (_back + 1) % _container.size();
++_size;
}
void pop()
{
_front = (_front + 1) % _container.size();
--_size;
}
T& front()
{
return _container[_front];
}
bool empty() { return _size == 0; }
int size() { return _size; }
public:
vector<T> _container;
int _front = 0;
int _back = 0;
int _size = 0;
};이렇게 vector를 통해서 순환 구조로도 만들 수 있다라는 점이 중요하다.
6. 오른손 법칙 개선
오늘은 오른손법칙 좀 똑똑하게 개선을 할 것인데 그전에 잠깐
선형 자료구조 복습을 좀 하자면은..
동적배열 / 연결 리스트 시간 복잡도 중요함.
여기서 이동을 할 때마다 걸어왔던 길을 스택으로 추적을 해줄 것이다.
가야할 좌표가 스택의 최상위의 원소와 같은지를 비교를 하여 다르다면 그대로 push를 해주고
위로 갔다가 되돌아와야할 경우 다음 좌표가 스택의 최상위 원소와 같을 경우 돌아가는 길이라고 인지를 한다음에 스택에 있던 정보를 pop을 해서 하나씩 빼줄 것이다.
우수법 개선 코드 (중요) ❗❗❗
_pos = board->GetEnterPos();
p_board = board;
POS pos = _pos;
DIR dir = _dir;
_path.clear();
_path.push_back(pos);
POS front[4] =
{
POS {0, -1},
POS {-1, 0},
POS {0, 1},
POS {1, 0}
};
POS dest = p_board->GetExitPos();
while (pos != dest)
{
DIR newDir = DIR((int32(dir) + int32(DIR::COUNT) - 1) % int32(DIR::COUNT));
// 1. 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는지 확인.
if (Cango(pos + front[int32(newDir)]))
{
// 오른쪽 방향으로 90도 회전
dir = newDir;
// 앞으로 한 보 전진
pos += front[int32(newDir)];
_path.push_back(pos);
}
// 2. 현재 바라보는 방향을 기준으로 전진할 수 있는지 확인.
else if (Cango(pos + front[int32(dir)]))
{
// 앞으로 한보 전진
pos += front[int32(dir)];
_path.push_back(pos);
}
else
{
// 왼쪽 방향으로 90도 회전
dir = DIR((int32(dir) + 1) % int32(DIR::COUNT));
}
}이전에 이렇게 하면은 거의 몇백개씩 _path안에 들어가게 되는데
돌아나오는 부분을 체크를 하기 위해서 stack을 사용하여
stack<POS> s;
for (int i = 0; i < _path.size() - 1; ++i)
{
if (s.empty() == false && s.top() == _path[i + 1])
{
// 되돌아 가야하는 길
s.pop();
}
else
{
s.push(_path[i]);
}
}
// 목적지 도착
if (_path.empty() == false)
s.push(_path.back());
vector<POS> path;
while (!s.empty())
{
path.push_back(s.top());
s.pop();
}
std::reverse(path.begin(), path.end());
_path = path;
이렇게해주면 돌아 나와야하는 부분을 체크가 가능하다.
그리고 스택의 특성상 목적지부터의 좌표가 나오게 되기 때문에
reverser를 이용하여 반대로 뒤집어 준다.
