[C++] Data Structure & Algorithm/STL11 [STL] algorithm 기존 문제점 예제를 하나씩 풀어봤는데, 가독성이 좋지 않다는 걸 알 수 있다. 코드는 굉장히 단순하지만, 그래도 분석하는데 최소 10초는 걸릴 수 있다고 생각할 수 있다. 또한 정형화된 패턴이 아니다보니 프로그래머 마다 스타일이 다를 수도 있다. 그래서 바로 보자마자 이해하기 어렵다. 더욱 큰 단점은 코드는 vector를 사용했기 때문에, 코드 내에선 특정 인덱스에 접근(v[i])하는 임의 접근 코드가 들어가있지만, 만약 삽입/삭제의 효율 때문에 list로 바꿔야 한다면 문법의 문제가 생길것이다. #include #include #include using namespace std; int main() { srand(static_cast(time(nullptr))); vector v; for (int i .. 2023. 5. 22. [STL] set, multimap, multiset set #include #include #include #include using namespace std; 주제 : set, multimap, multiset int main() { // (key = value) set s; // 넣고 s.insert(10); s.insert(20); s.insert(30); s.insert(40); // 뺴고 s.erase(40); // 찾고 set::iterator findit = s.find(50); if (findit == s.end()) cout 2023. 5. 20. [STL] map vector, list 문제점 #include using namespace std; class Player { public: Player() : _playerId(0) { } Player(int playerId) : _playerId(playerId) { } public: int _playerId; } int main() { vector v; // 10만명 입장 for (int i = 0; i < 100000; ++i) { Player* p = new Player(i); v.push_back(p); } // 5만명이 퇴장 for (int i = 0; i < 50000; ++i) { int randIndex = rand() % v.size(); Player* p = v[randIndex]; delete p.. 2023. 5. 19. [STL] deque #include #include // 주제 : deque // vector : 동적 배열 [ ] // list : 이중 연결 리스트 // [ ] [ ] [ ] [ ] // deque : doble-ended queue 데크 // [ ] // [ ] // [ ] int main() { // 시퀀스 컨테이너 (Sequence Container) // 데이터가 삽입 순서대로 나열되는 형태 deque dq; // vector와 사용형태가 굉장히 비슷하다. // capacity가 없다. dq.push_back(1); dq.push_front(2); dq[0]; // 임의접근도 가능. // vector와 마찬가지로 배열 기반으로 동작. // 다만 메모리 할당 정책이 다르다. // vector는 뒤로만. deque는.. 2023. 5. 19. [STL] list #2 list 직접 만들어보기. #include using namespace std; #include #include // 오늘의 주제 : list 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*_prev; T_data; }; template class Iterator { public: Iterator() : _node(nullptr) { } Iterator(Node* node) : _node(node) { } // ++it Iter.. 2023. 5. 19. [STL] list #1 list (연결 리스트) list의 동작 원리 중간 삽입/삭제 처음/끝, 삽입/삭제 임의 접근 (Random Access) list li; for (int i = 0; i < 100; ++i) li.push_back(i); li.push_front(0); // vector는 처음 삽입이 비효율적이라 없음 int size = li.size(); //li.capacity(); // 없음 int first = li.front(); int last = li.back(); // li[3] = 10 // 임의접근 허용안됨 list::iterator itBegin = li.begin(); list::iterator itEnd = li.end(); li.insert(itBegin, 100); li.erase(li.be.. 2023. 5. 15. [STL] vector #4 vector 직접 만들기 template class Vector { public: Vector() : _cata(nullptr), _size(0), _capacity(0) { } ~Vector() { if (_data) delete[] _data; } T& operator[](const int pos) { return _data[pos]; } public: void push_back(const T& val) { if (_size == _capacity) { // 증설 작업 int newCapacity = static_cast(_capacity * 1.5); // capacity가 0 or 1 이면 0과 1.5 짤려서 1을 반환하기 때문에 체크 if (newCapacity == _capacity) newC.. 2023. 5. 15. [STL] vector #3 vector = 동적 배열 = 동적으로 커지는 배열 = 배열 원소가 하나의 메모리 블록에 연속하게 저장된다. 중간 삽입/삭제 (BAD) vector의 중간 삽입은 새로운 데이터를 중간에 하나만 딱 밀어넣는게 아니라, 기존에 있던 데이터를 모두 이동시키는 것이기 때문에 비효율적이다. 데이터 크기가 클수록 더욱 비효율적이다. 또한 vector는 연속된 메모리 블록이기 때문에, 원소를 중간 삭제했을 때 데이터를 날리고 끝나는 게 아니라 나머지 데이터도 이동해야 돼서 비효율적이다. [0] [1] [2] [3] [4] [0] [1] [5] [2] [3] [4] 결론은 vector의 중간 삽입/삭제는 비효율적이다. 처음/끝, 삽입/삭제 (처음 - BAD / 끝 - GOOD) 처음 삽입/삭제는 뒤에 있는 데이터가 이.. 2023. 5. 15. [STL] vector #2 반복자(iterator) : pointer와 유사한 개념. 컨테이너의 원소(데이터)를 가리키고, 다음/이전 원소로 이동 가능 vector v(10); for (vector::size_type i = 0; i < v.size(); i++) v[i] = i; vector::iterator it; iterator도 class다. 위 설명 코드 ex) class MyIterator { }; class MyVector { public: typedef MyIterator iterator; typedef unsigned int size_type; } pointer와 비교해서 설명한 ex) iterator는 pointer처럼 활용할 수 있다. vector v(10); for (vector::size_type i = 0.. 2023. 5. 15. [STL] vector #1 STL (Standard Template Library) 프로그래밍 할 때, 필요한 자료구조/알고리즘들을 템플릿으로 제공하는 라이브러리 컨테이너(Container) : 데이터를 저장하는 객체 (자료구조 Data Structure) vector (동적 배열) vector의 동작 원리 (size/capacity) 중간 삽입/삭제 처음/끝, 삽입/삭제 임의 접근 배열 const int MAX_SIZE = 10 int arr[MAX_SIZE] = { }; for (int i = 0; i < MAX_SIZE; ++i) arr[i] = i; 근데 여기서 추가로 데이터를 가지고 싶다면? 몬스터를 추가시키고 싶다면? 그러면 애초에 배열의 크기 10으로 잡아서 사용못하는 문제가 있을 것이다. 추가적으로 배열을 늘리는 것.. 2023. 5. 15. 이전 1 2 다음
