C++ 15일차

큐란?

선입 선출 자료구조(먼저 온것 먼저 처리 방식)

pop은 맨 앞의 데이터를 빼고 /push는 맨 뒤에 데이터를 넣음

front 가장 먼저 삽입된 요소를 참조로 반환 /back 가장 마지막에 삽인된 요소 참조로 반환

size queue의 요소 수 반환 /empty queue가 비어있으면 true 아니면 false

 

큐 만드는 법

ex) std::queue<type> Name;

 

스택?

후입 선출 자료구조(통에 물건을 넣고 빼는 방식)

top은 가장 마지막 저장된 요소 참조 반환 push는 맨 위에 데이터를 넣고 pop은 맨 위의 데이터를 뺀다.

size, empty 존재

 

만드는법

std::vector<type> Name;

 

리스트? (자주 사용하지않음 벡터를 더 많이사용) //실무는 벡터 또는 맵에서 끝남

operator[]가 없음

양쪽 끝에서 삽입/제거 가능

(단방향, 양방향존재)

insert(iterator position, const value_type& value)

position이 카리키는 위치에 새 요소 삽입

push_front 제일 처음에 새 요소 삽입 //제거는 pop_front

push_back 제일 마지막에 새 요소 삽입 //제거는 pop_back

iterator erase(iterator position) position이 가리키는 위치의 요소 제거

remove value와 값이 같은 요소 전부 제거

장점

삽입 제거 시간이 O(1)

어느 위치든 삽입/제거 가능

단점

탑색이 느림

임의 접근 불가

메모리 불연속적

 

만드는법

std::list<type> Name;

 

STL 컨테이너는 종류가많다

멀티셋 (중복 키 허용, 요소 수정X)

멀티맵 (중복 키 허용)

덱 (double_ended queue, 양쪽 끝에서 삽입, 삭제가능) 

우선순위 큐 (자동 정렬 큐)

 

STL 컨테이너에서는 벡터, 맵을 가장 많이사용한다!!(보통 벡터와 맵에서 해결)

 

STL 컨테이너의 목적

모든 컨테이너에 적용되는 표준 인터페이스 

std 알고리즘은 많은 컨테이너 작동

템플릿 프로그래밍 기반

메모리 자동 관리

 

STL은 무조건은 좋지않다!

많은 회사들이 자신만의 컨테이너로 STL을 대체..

EA,Epic Games 등..많은 회사가 최적화 시킨 컨테이너 사용

그대로 STL 사용하는 경우도 있지만, 고 성능을 위해서는 자신만의 컨테이너를 만드는 회사가 많다.