vector5 [Linear Data] Chapter 01. 동적 배열 구현 GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commit/2e1fffb765ff77ea1e260e027e2d0a23d81f7f73 동적배열(Vector) 구현 · developeSHG/Data_Structure-Algorithm@2e1fffb developeSHG committed Aug 7, 2023 github.com 선형 구조는 자료를 순차적으로 나열한 형태 - 배열 - 연결 리스트 - 스택 / 큐 비선형 구조는 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태 - 트리 - 그래프 배열 VS 동적 배열 VS 연결 리스트 { 배열 : - 사용할 데이터를 고정해서 할당하고 (절대 변경 불가) - 연속된 메모리를 배정받아 사용 장점 .. 2023. 8. 7. [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 다음
