본문 바로가기

[ C/ C++ 프로그래밍 ]/[ STL ]

[ 혼연 정리 ] 연관 컨테이너 - 8 [ 컨테이너 어댑터 ] ㅇ 컨테이너 어댑터 - 컨테이너 어댑터는 기본 컨테이너의 기능 중 일부만을 공개하여 기능이 제한 되거나 변형된 컨테이너를 만든다. - 기존 컨테이너의 구현 중 일부는 그대로 사용하되 외부에서 사용하는 인터페이스만 변경하는 것이다. - STL은 스텍, 큐, 우선쉬위 큐 세가지의 컨테이너를 어댑터로 제공 ㅇ 스텍 - 선형적인 기억 공간에 자료를 저장하되, LIFO를 할 수 있다. - 임의 위치를 엑세스한거나 중간에서 삽입, 삭제하는 동작은 필요치 않다. - 스텍의 정의 template class stack { ... } - 스텍에 들어갈 데이터 타입 T와 스텍이 자료 저장을 위해 사용할 컨테이너 Cont(스텍의 요소 타입과 같은 타입을 저장하는 컨테이너) 이다. - Cont는 디폴트로 제공, 벡터나 리스트로.. 더보기
[ 혼연 정리 ] 연관 컨테이너 - 7 [ 맵 ] ㅇ 맵의 활용 - 맵의 가장 큰 장점은 빠른 검색속도이다. ==> 키를 삽입할 때마다 정렬 - 이분 검색법을 사용 ==> 10억중에 하나를 찾는다 해도 최악의 경우 30번 정도만 비교하면 된다. 1 #include 2 #include 3 #include 4 #include 5 using namespace std; 6 7 struct {const char * first; unsigned second; } sites[] = { 8 {"www.winapi.co.kr",0x10203040}, 9 {"www.lpacampus.com",0x20304050}, 10 {"www.microsoft.com",0x99999999}, 11 {"www.borland.com",0xbbbbbbbb}, 12 {"kangcom.com.. 더보기
[ 혼연 정리 ] 연관 컨테이너 - 6 [ 맵 ] ⊙ 맵 - 맵은 키와 값의 쌍을 관리한다. - 연관이 있는 두개의 값을 쌍으로 관리 한다는 점에 연관 컨테이너라고 함 - 정렬된 상태로 요소를 저장하므로 빠르게 검색할 수 있다. - 두 컨터네이너 모두 키를 정렬 및 검색의 기준으로 사용한다. - 단순 맵은 키의 중복을 허락하지 않음, 한 키에 하나만 저장할 수 있다. - 멀티맵은 키의 중복을 허용하므로 여러 개의 키를 저장할 수 있다. - 데이터의 관계를 표현하는데 주로 사용 ㅇ 맵 클래스 - 단순 맵 정의 template class map { ... } - 멀티 맵도 이름만 다를 뿐 정의는 같다. - 데이터에 해당하는 값의 타입을 두 번째 인수로 요구 - 나머지 비교 함수 객체나 할당기는 셋과 동일하며 디폴트가 무난하게 지정되어 있어 생략가능 - 키와.. 더보기
[ 혼연 정리 ] 연관 컨테이너 - 2 [ 셋 ] ㅇ 셋 (set) - 셋(set)은 영어 단어 뜻 그대로 집합을 의미한다. - 동일한 타입의 데이터를 모아 놓은 것 - 저장하는 데이터 자체가 키로 사용되고 값은 저장되지 않는다. - 셋은 키의 중복을 허용하지 않는다. 멀티셋은 키의 중복 허용 template class set { ... } - class Key : 저장되는 키 타입 - class BinPred : 키를 정렬하기 위한 비교함수, 디폴트 오름차순 - class A = 할당기 - 시퀀스 컨테이너와 마찬가지로 내부에서 사용하는 타입을 정의 하는데 value_type, iterator, const_iterator, reference 등의 같은 이름을 사용한다. - 이외 다음 세게의 타입을 추가로 정의 - value_compare : 셋에 꼭 필.. 더보기
[ 혼연 정리 ] 연관 컨테이너 - 1 [ 셋 ] ㅇ 연관 컨테이너 - 키와 값 처럼 관련 있는 데이터를 하나의 쌍으로 저장하는 컨테이너 - 맵은 키와 값의 쌍을 저장하며, 셋은 키만 저장하고 값은 저장하지 않는다. - 데이터를 저장할 때 아무곳에나 저장하지 않고 검색을 고려하여 최대한 빠른 속도로 키를 찾을 수 있는 위치에 저장하므로 검색속도가 굉장히 빠르다. - 구현하는 방법에는 이진트리, 해쉬테이블에 저장하는 방법이 있다. - 해쉬 : 해쉬 함수에 의해 한번에 자료를 찾을 수 있으므로 검색속도가 거의 순식간이라는 장점, 성능을 높이기 위해서 해쉬 테이블이 충분히 커야 하므로 메모리 낭비가 좀 심한편 데이터의 분포 정도에 따라 검색 속도가 운에 좌우되는 경향, 최악의 상황에는 속도가 떨어진다. - 이진트리 : 메모리 낭비가 심하지 않음, 데이터의 종.. 더보기
[ 혼연 정리 ] 시퀀스 컨테이너 - 9 [ 리스트 ] ◎ 정렬 - 임의 접근 반복자를 제공하지 않으므로 정렬 속도가 대단히 느림 - 정렬속도가 느리므로 알고리즘 sort함수를 사용하지 않고 멤버 함수 sort를 사용 알고리즘 sort : 퀵소트 구현, 멤버함수 sort : 리스트에 특화된 알고리즘 ㅇ sort - void sort(); /// ' 더보기
[ 혼연 정리 ] 시퀀스 컨테이너 - 8 [ 리스트 ] ◎ 링크 재배치 - 리스트에는 링크 재치의 장점을 살리수 있는 여러가지 함수가 준비되어 있다. ㅇ void swap(list& Right); - 실제 요소를 교환할 필요 없이 리스트끼리 head, tail 정보만 바꾼다. ==> 속도 상승 ㅇ void reverse() - 요소들을 꺼구로 재배치하여 일일 옮길 필요없이 next, prev 링크를 반대로 바꾼다. ㅇ void merge(list& Right) - 리스트끼리 병합하는 merge는 링크를 조작하여 한쪽 리스트를 다른쪽의 끝과 연결한다 ※ swap, reverse, merge 이 함수는 일반함수로도 제공되지만, 멤버함수로 제공되는 이유는 리스트의 특성을 이용하여 하기때문에 일반함수보다 훨씬 빠르다. ㅇ splice 함수 - splice 의미 : .. 더보기
[ 혼연 정리 ] 시퀀스 컨테이너- 7 [ 리스트 ] ◎ 삽입, 삭제 - 삽입,삭제 함수 벡터와 동일 iterator insert(iterator it, const T& x = T()); void insert(iterator it, size_type n, const T& x); void insert(iterator it, const_iterator first, const_iterator last); iterator erase(iterator it); iterator erase(iterator first, iterator last); - list 예) 1 #include 2 #include 3 4 using namespace std; 5 6 template 7 void dump(const char *desc, C c) 8 { 9 cout.width(12); .. 더보기
[ 혼연 정리 ] 시퀀스 컨테이너- 6 [ 리스트 ] ◎ 리스트 - 이중 연결 리스트를 탬플릿으로 추상화한 버전 - 동일한 자료의 집합을 관리 - 용도면에서 벡터와 같고 서로 대체 가능 ==> 주요 멤버함수의 원형 일치, 대입,비교등의 연산자도 동일 - 리스트의 반복자는 링크를 가리키는 포인터 ( 벡터의 반복자는 요소를 직접 가리키는 포인터) ㅇ 벡터와 리스트의 주요 차이점 ① 반족자의 레벨 (가장 큰차이점) => 리스트 양방향, 벡터는 임의 접근 - []연산자, at함수, sort, binary_search 사용 X ② 링크만 조작해서 삽입, 삭제 수행 - 제일 앞에 요소 삽입, 삭제하는 push_front, pop_front 제공 - capacity, reserve 불필요 -> 크기를 처음부터 정할 필요 없음 ③ 링크 구조로 인해 메모리 소모량은 벡터 .. 더보기
[ 혼연 정리 ] 시퀀스 컨테이너 - 5 [ 벡터 ] ◎ vector - bool은 크기가 1바이트 이지만 true or false 를 기억하는데 1비트만 있으면 된다. --> 7비트 낭비 - bool형에 특수화 되어 있어 하나의 값을 저장하는데 비트 하나만 사용 --> c구조체의 비트필드와 유사 - vector은 진위형의 요소들을 1비트에 하나씩 압축하여 저장하는 별도의 독립 클래스 - vector도 가능하나 BOOL은 정수와 크기가 같다. ==> vector보다 32배 크다. - vector 표준에 포함되어 있긴하나 몇가지 문제점과 컴파일러마다 지원 범위가 다르다. ==> 가급적 사용을 자제. - 사용예) 1 #include 2 #include 3 4 using namespace std; 5 6 void main() 7 { 8 vector vb(32);.. 더보기

티스토리툴바