'map'에 해당되는 글 1건

  1. 2011.05.31 STL 기본
2011.05.31 10:14

STL이란?

Standard Template Library 라고 불리우며, C++에서 사용할 수 있는 컨테이너 클래스와 알고리즘을 일반화

시켜서 사용 할 수 있는 자료구조 등을 포함하는 라이브러리의 모음이다.

흔히 generic library(일반화된 라이브러리)라고 부른다.템플릿을 사용하여 구현되어있다.

 

그럼 STL을 왜 사용하는가?

전용의 함수 혹은 전용의 자료구조가 아닌 일반적으로 사용 가능한 함수 혹은 자료구조를 만들기 위해서이며,

일반적인 자료구조에 일반적인 알고리즘을 적용시키기 위해서이다.

쉽게 말해 코드길이를 줄이고 유지보수 쉽고 확장이 쉬운코드를 만들기 위해서인데,

그냥 자신이 직접 만들어 쓰는것보다 STL이 좋고 일일이 하나씩 만들어 쓰는것보다 STL을 가져다 쓰는게 쉬워서이다.

게다가 STL은 표준이기 때문에 리눅스,윈도우,솔라리스등에서도 정상적으로 작동한다.

 

장점?

1. 소스길이를 줄일 수 있다.

2. 유연하다.(컨테이너와 알고리즘이 대게 분리되어있어 자신의 알고리즘을 적용할 수 있다.)

3. STL은 충분히 테스트 되고 최적화되어 있어 안정적이다.

단점?

1. STL에 익숙하지 않다면 디버깅이 어렵다.

2. 반복자와 컨테이너가 분리되어 존재 하기 때문에, 스레드 프로그래밍시 문제가 발생 할 수 있다.

3. STL이 유연성을 구현하기 위한 템플릿의 경우 프로그램의 크기를 매우 크게 만들 수 있다.

 

>컨테이너의 원소가 삽입,삭제 되면 모든 레퍼런스,포인터,반복자들은 무효화된다.

 

Vector

-동적 배열을 사용해 구현.

-reserve() 용량 확보, 재할당을 피할때 사용, 용랑을 줄이지는 못한다.

-assign() 기존의 값을 없애고 새값을 재할당한다.

-at(index)은 out-of-range 범위 에러 예외를 발생한다. 이것을 제외한 [],front,back 등은 에러를 발생하지 않는다.

-랜덤 엑세스 반복자(벡터,데큐,스트링,배열) +,-,<,>오프셋 연산지원

-양방향 반복자(리스트,셋,멀티셋,맵,멀티맵) ++,--

-입력,출력 반복자(istream/ostream)

-벡터와 스트링의 경우 포인터처럼 반복자를 구현. 데큐,리스트,맵,셋 등은 클래스 형태로 구현.

(반복자구현 환경에 따라 다를수 있다)

-일반 vector과 vector<bool>에 대해 다시공부

 

 

Deque

-벡터와 유사하다. 하지만 벡터가 연속적인 메모리 구조를 갖는 반면

deque는 '분리된 메모리 블록의 집합'이란 방식으로 구현된다.

 

List

 

Set & Multiset

-자신들의 원소를 자동정렬한다.

-set과 multiset은 균형 이진트리로 구현됨.

자동정렬의 가장 큰 장점은 특정값으로 검색할 경우 이진트리가 좋은 성능을 보장한다는 것이다.

로그 복잡도를 지닌다. O(log n)

 

-set과 multiset의 차이는 중복값의 허용 유무이다. 중복값은 multiset만 허용된다. set은 중복값을 삽입했을경우 무시한다.

-할당자

allocate(num) num개의 원소에 대해 메모리 할당.

construct(p,val) 할당된 p 공간을 val로 초기화.

destroy(p) p가 참조하는 원소 소멸.

deallocate(p,num) p가 참조하는 num개의 원소 메모리 해제.

-벡터와 데큐와 달리 직접적인 원소 엑세스가 안된다.

반복자를 통한 간접 엑세스 또한 제한 받는다.(반복자 측면에서 모든 원소의 값은 상수값이다)

- '=='비교 동작은 두 컨테이너의 정렬 타입이 같아야한다. 타입이 다를때는 비교 알고리즘을 사용.

equal(beg1,end1,beg2), equal(beg1,end1,beg2,비교조건(op))

 

-set과 multiset의 insert()함수의 반환값이 다르다. 이유는 중복값의 허용.

-시퀀스 컨테이너(벡터,데큐,리스트) : 모든 원소들이 자신만의 위치를 가지고 있는 순서가 존재하는 컬렉션.

                                                    원소의 값과는 무관하고 삽입된 순서대로 순서를 유지.

-연관 컨테이너(셋,멀티셋,맵,멀티맵) : 모든 원소들이 정렬 기준에 의존하여 자동 정렬이 되는 컬렉션.

                                                      원소의 순서는 값에만 의존. 삽입순서와는 무관.

 

 

Map & Mulitmap

-이것 역시 중복값 허용의 차이, multimap이 중복값 허용.

-key값으로 정렬, key로 검색하면 좋다. value값으로 정렬되지 않는다. value로 검색하면 성능 안좋음.

-find_if(beg,end,value_equals<T,T>(valud))알고리즘.

-map에서 특이한 점은 vector처럼 []연산자를 제공한다.

-replace_key(map m, old key, new key)를 사용해 키값을 변경한다. multimap의 경우 다른 방법은 없다.

하지만 map의 경우에는 []연산자를 이용.

m[new key] = m[old key];

m.erase(old key);

 

-암시적인 형변환을 막기위해 value_type,pair(const붙여서씀) 사용.

가장 좋은 방법은 make_pair를 사용하는 것이다.

 

해쉬 테이블

hash_set

 

hash_map

 

hash_multiset

 

hash_multimap

신고
Posted by 우엉 여왕님!! ghostkyow

티스토리 툴바