Crat

9-10. STL - 알고리즘

이전 예제 실습에서 구현한 코드를 알고리즘을 이용하여 간단하게 구현할 수 있다. 1. 특정 값 찾기 - find / find_if (1) find vector::iterator findIt = find(v.begin(), v.end(), number); // find(시작 위치, 끝 위치, 찾을 숫자) find는 결과로 반복자를 리턴한다. 따라서 vector가 아닌 list에서도 사용할 수 있다. (2) find_if struct Divby11 { bool operator()(int n) { return (n % 11) == 0; } }; vector::iterator findIt = find_if(v.begin(), v.end(), Divby11()); find_if의 세번째 항인 조건항은 함수의 형식..

9-9. STL 실습

0. 사전 준비 0~99의 숫자를 랜덤하게 뽑아 어떤 변수에 저장하고 그 변수의 값을 동적 배열에 하나씩 밀어넣는다. #include #include #include #include #include #include using namespace std; int main() { srand(static_cast(time(nullptr))); vector v; int count = 0; bool found = false; for (int i = 0; i < 100; i++) { int num = rand() % 100; //0~99까지 100개의 숫자 중 하나 랜덤 저장 v.push_back(num); } Q.1) 어떤 숫자(number)가 벡터에 있는지 찾기(bool과 iterator 위치 반환) { int ..

9-8. STL - Set, Multimap, Multiset

1. Set 키와 값이 동일. 임의 접근이 불가능. 오름차순으로 정렬됨. map과 동일하게 요소를 넣고 삭제하고 찾는 것 또한 가능하다. 2. Multimap 중복되는 키를 가질 수 있음. 임의 접근이 불가능. 삭제 시에 해당하는 키와 일치하는 키-값 페어를 모두 삭제함. -> 특정 키-값 페어만 삭제하고 싶다면 반복자를 사용함. 3. Multiset Set과 동일하나 중복되는 키를 가질 수 있음.

9-7. STL - Map

0. 객체가 많아졌을 때 vector의 문제 각자의 플레이어 아이디를 가지는 객체 player를 생성한다. #include #include #include #include using namespace std; class Player { public: Player() : _playerId(0) {} Player(int playerid) : _playerId(playerid) {} public: int _playerId; }; 이후 10만명을 입장시키고 랜덤으로 5만명을 퇴장시키게 한다. int main() { vector v; // 10만명 입장 for (int i = 0; i < 100000; i++) { Player* p = new Player(i); v.push_back(p); } // 5만명 퇴장 ..

9-6. STL - Deque

0. 시퀀스 컨테이너 (Sequence Container) 데이터가 삽입한 순서대로 나열되는 형태 ex) vector, list, deque 1. Deque(Double-ended Queue ; 데크) 큐와 스택의 특징을 모두 가지는 형태. 동적 배열의 형태이지만 vector와는 조금 다르게 작동함. 이중 연결 리스트의 형태이지만 list와는 다르게 임의 접근이 가능함. 각 블록이 메모리 영역에 연속적으로 있지 않기 때문에 포인터 연산이 불가능함. 2. vector와의 차이점 - vector : size가 capacity보다 커지면 메모리 영역을 제거하고 더 큰 메모리 영역을 재할당하고 데이터를 복사 / 이동시킴. - deque : size가 capacity보다 커지면 다음 데이터 부터는 다른 메모리 영..

9-5. STL - List 구현하기(실습)

1. 노드 구현하기 template class Node { public: Node() : _next(nullptr), _prev(nullptr), _data(T()) { } Node(const T& value) : _next(nullptr), _prev(nullptr), _data(value) { } public: Node* _next; // 다음 노드의 주소를 담은 포인터, 노드 다음에는 노드가 있음(Node 형) Node* _prev; // 이전 노드의 주소를 담은 포인터 T _data; // 각 노드의 값 }; 2. 리스트 구현하기 template class List { public: List() : _size(0) { _header = new Node(); _header->_next = _head..

9-5. STL - List (2)

이중 연결 리스트를 중점에 둔다. list는 데이터가 연속적으로 존재할 필요가 없기 때문에 vector에 비해 삽입과 삭제가 효율적으로 작동한다. 1. 중간 삽입 / 삭제 vector에서는 중간 삽입을 위해 삽입 위치의 오른쪽 값들을 한 칸씩 복사 붙여넣기하는 비효율적 과정이 필요했으나 list에서는 보다 효율적으로 작동하게 된다. 중간에 노드를 추가하고 이전 노드와 다음 노드의 포인터를 가지게 한다. 2. 처음과 끝 삽입 / 삭제 list에서는 처음과 끝에 노드를 삽입하거나 삭제할 때 포인터에만 유의하면 된다. 3. 임의 접근 ; i번째 데이터에 접근하기(불가능) vector와 다르게 불연속적이고 capacity의 개념이 없기 때문에 임의 접근이 어려움. (노드에서 다른 노드로, 다른 노드에서 또 다른..

9-4. STL - List (1)

벡터와 비슷하지만 차이점이 있으며 차이점에 대해서 명확히 알고 있어야 한다. vector : 동적 배열. 연속된 공간을 할당받아 사용. 사이즈가 캐퍼시티를 초과하면 메모리를 확장 후 기존 데이터를 복사 붙여넣기 함. 임의 접근 가능. 1. list의 동작 원리 (1) 단일 연결 리스트 각 노드(데이터를 저장하는 칸)가 서로 다른 메모리 영역에 저장되어 있고 서로 어디에 있는지만 알 수 있도록 연결되어 있음. 이미 알고 있는 클래스에 비유하여 만들면 이렇게 나타낼 수 있다. class Node { public: Node* _next; // 다음 노드의 주소를 담은 포인터, 노드 다음에는 노드가 있음(Node 형) int _data; // 각 노드의 값 }; 노드(8 또는 12바이트) 안에서는 다음 노드의 ..