알고리즘&자료구조/c++ stl 정리 (10) 썸네일형 리스트형 c++ stl Container 사용법 정리 문제를 해결할 때 적절한 자료구조를 선택하면 문제를 쉽게 해결할 수 있다. c++에서 지원하는 아주 유용한 container들이 있다. 간단하게 각각 접근법,삽입,삭제에 대해서 알아보자. -vector 정리해 놓은 개시물 링크 https://zero-stone.tistory.com/22 >접근법: 1) v[index] / 시간복잡도=O(1) 2) v.at(index) / 시간복잡도=O(1) 3) v.back() / 시간복잡도=O(1) 4) v.front() / 시간복잡도=O(1) 5) v.begin과 v.end를 이용해 iterator로 접근 / 시간복잡도=O(N) 6) v.data를 이용해 포인터로 접근 / 시간복잡도=O(N) iterator가 [] 지원 ex) it[1] >삽입: 1) v.insert.. C++ STL Sequence Container -Sequence Container란? *container= 기본자료형과 사용자가 정의한 자료형을 담는 자료구조 *Sequence= 배열과 같이 입력한 순서대로 저장하여 정렬이 돼있지 안은 자료구조이다 c++ stl중 지원하는 Sequence Container의 종류는 > vector https://zero-stone.tistory.com/22 > deque https://zero-stone.tistory.com/25 > list https://zero-stone.tistory.com/23 > forward_list https://zero-stone.tistory.com/24 로 이루어져있다. (궁금하면 링크 참조) -특징 1) vector vector는 배열로 구현된 자료구조이다. 크기가 자유자재로 늘.. c++ deque #inclue -deque란? vector와 같은 기능을 하는 자료구조이다. vector와의 차이는 vector의 경우 insert시 용량이 다 하면 새로 동적할당 받고 기존은 데이터를 새로 할당 받은 메모 리 공간에 복사한다. deque는 이러한 단점을 보완하기 위해 insert시 용량이 다 해도 공간을 늘리되 복사 작업을 하지 않는다. vector와 아주 유사함으로 지원하는 함수도 거의 유사하다. vector를 잘 모른다면 참고 https://zero-stone.tistory.com/22 -vector와의 차이 1)capacity , data , reserve 지원x vector는 메모리의 연속적인 공간에 사상된다. 이와 반대로 deque는 연속적인 공간에 사상되지 안는다. deque은 블록단위로 메.. c++ forward_list -forward_list란? list와 다르게 단방향(전방) 포인터로 연결된 구조이다. 그래서 iterator이용시 --사용 불가 list를 잘 모른다면 https://zero-stone.tistory.com/23 참고 (list와 같은 부분은 생략하겠다.) -헤더파일 #include -함수 1)befor_begin(): 시간복잡도:O(1) 시작 위치전을 가리키는 정방향 iterator 반환 begin()함수도 존재 2)erase_after, insert_after , splice_after: 시간복잡도:O(N) 모두 list의 erase,insert,splice 기능과 동일하다. 차이점은 예를들어 리스트의 5번째 자리에 insert하고 싶다면 (양방향)list는 5번째 iterator를 매개변수로 전달.. c++ list (stl) -list란? 노드들이 포인터를 통해 서로 양방향 포인터로 연결된 형태의 자료구조이다. 검색 시간은 오래걸리지만 삽입,삭제는 빠르다는 장점을 갖고 있다. -헤더파일 #include -생성 1)default 생성자: list li; 비어있는 list를 생성 2) 크기 지정 생성자: list li(4); 노드수가 4인 vector 생성 원소들은 0으로 초기화 된다. 3)크기와 초기화 쌍 생성자: list li (4,100); 노드수가 4이며 모두 100으로 초기화 4) 다른 list의 원하는 범위 지정 생성자: list li(first_iterator , last_iterator); 다른 list의 복사 하기를 원하는 시작 위치와 끝 위치의 다음 iterator를 매개변수로 전달하여 li에 복사 5) 다른 .. c++ vector -vector란? 동적으로 크기(용량)가 변하는 배열이라고 생각하면된다. 배열의 경우 int a[10];과 같이 선언하면 a배열은 10개의 value만 갖고있을 수 있지만 vector는 이와 같은 제약이 없다. -헤더파일 #include -생성 1)default 생성자: vector v; 비어있는 vector를 생성 2) 크기 지정 생성자: vector v(4); 크기(원소 수)가 4인 vector 생성 원소들은 0으로 초기화 된다. 3)크기와 초기화 쌍 생성자: vector v (4,100); 크기가 4이며 모두 100으로 초기화 4) 다른 vector의 원하는 범위 지정 생성자: vector v(first_iterator , last_iterator); 다른 vector의 복사 하기를 원하는 시작 위.. c++ pair -pair란? template struct pair로 2개의 data_type을 묶은 1개의 구조체 개체이다. 2개의 data_type을 다룰 때 유용하게 사용하는 자료구조이다. -멤버 변수 위에서 설명했듯이 pair는 2개의 data_type을 묶은 구조체이다. 그럼으로 first,second라는 이름의 멤버 변수를 갖는다. -생성자 1) default 생성자 pair 변수명 first와second는 모두 0으로 초기화 된다. 2) 값 직접 넣어주는 생성자 pair 변수명 (data1,data2) data자리에는 data_type에 맞는 value를 넣어주면 된다. 3) 다른pair개체 복사하는 생성자 pair 변수명 ( 복사pair명) ex. pair b(1,1); pair a(b) ; - make_.. c++ set & multiset - set이란? set은 insert시 원소들이 자동적으로 정렬된다는 특징을 갖는다. value값은 중복을 허용하지 안는다.. set은 value를 노드로 갖는 red black tree(binary search tree의 일종)로 구현 돼있다. binary search tree의 경우 트리 최악의 높이는 n이다 반면 red black tree는 o(logn)을 갖는다. *multiset은 value값의 중복을 허용하는거 이외에는 set과 동일하다.( value를 갖고 erase시 해당되는 value원소들 모두 삭제) -해더 파일 #include -생성 set (multiset은 set대시 multiset으로 바꾸면 된다.) 1) value_.. 이전 1 2 다음
