728x90

map과 multimap은 '연관 컨테이너'입니다. 모든 연관 컨테이너(set, multiset, map, multimap)는 '노드 기반 컨테이너'입니다. 또 모든 연관 컨테이너는 균형 2진 트리로 구현됩니다. 균형 2진 트리는 보통 레드-블랙 트리를 사용합니다. map은 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 여기서 key는 유니크합니다. multiset도 map과 같이 key와 value의 쌍으로 구성된 데이터 셋의 집합입니다. 단, multiset은 map과 달리 중복된 key가 존재할 수 있습니다.

 

map의 주요 개념을 그림으로 표현하면

 

 

set과 map은 데이터의 key가 유니크합니다.

 

multiset의 주요 개념을 그림으로 표현하면

 

 

multiset과 multimap은 같은 key값의 데이터를 컨테이너에 저장할 수 있습니다.

 

map, multimap의 주요 특징과 함수

 map도 set처럼 데이터를 추가하는 push_? 류의 함수를 가지고 있지 않습니다. 삽입(insert)한다는 의미에서 insert() 함수를 가지고 있습니다.

map의 특징은 key와 value의 쌍으로 데이터를 저장합니다. 그리고 key값을 이용하여 빠르게 value값을 찾을 수 있습니다. 연관 컨테이너에서 유일하게 [] 연산자 중복을 제공합니다.

 

기본적인 map 예제


#include <iostream>
#include <map>
using namespace std;
void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    cout << m[5] << endl;
    cout << m[3] << endl;
    cout << m[7] << endl;
    cout << m[2] << endl;
    cout << m[4] << endl;
}
  1. 100
    50
    80
    100
    100

map은 key와 value의 쌍으로 구성된 데이터들의 집합입니다. []연산자의 인덱스는 key이며 인덱스가 가리키는 메모리 값이 value입니다.

주의할 점은 m[5] = 100 연산에서 5라는 key가 없으면 노드 '추가'가되며 5라는 key가 있으면 '갱신'이 됩니다. 아래에서 공부합니다.

그림으로 설명하면..

 

 

map의 트리 그림입니다.

 

 

map의 key값 5로 value를 접근하는 그림입니다.

 

 

 

 map은 key와 value의 쌍을 pair 객체로 저장합니다. STL의 쌍을 이루는 모든 요소는 pair 객체를 사용합니다.

위 예제는 insert()함수를 사용하여 아래 예제로 바꿀 수 있습니다.


#include <iostream>
#include <map>
using namespace std;
void main( )
{
    map<int , int > m;

    m.insert( pair<int,int>( 5, 100) );
    m.insert( pair<int,int>( 3, 50) );
    m.insert( pair<int,int>( 7, 80) );
    m.insert( pair<int,int>( 2, 100) );
    pair<int,int> pr( 4, 100);
    m.insert( pr );

    cout << m[5] << endl;
    cout << m[3] << endl;
    cout << m[7] << endl;
    cout << m[2] << endl;
    cout << m[4] << endl;
}

  1. 100
    50
    80
    100
    100

 map은 key, value를 pair 객체로 각각 first와 second에 저장합니다.

그림으로 표현하면

 

 

 

 

반복자를 사용한 모든 key, value 출력 예제


#include <iostream>
#include <map>
using namespace std;

void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    map<int, int>::iterator iter;
    for( iter = m.begin(); iter != m.end() ; iter++)
        cout << "m["<<(*iter).first <<"]: " << (*iter).second << endl;

    cout << "==============" << endl;
    for( iter = m.begin(); iter != m.end() ; iter++)
        cout << "m["<<iter->first <<"]: " << iter->second << endl;
}
  1. m[2]: 100
    m[3]: 50
    m[4]: 100
    m[5]: 100
    m[7]: 80
    ==============
    m[2]: 100
    m[3]: 50
    m[4]: 100
    m[5]: 100
    m[7]: 80

 map도 양방향 반복자를 제공합니다.

그림으로 간단하게..

 

 

 

 

연관 컨테이너는 모두 동일한 함수군을 가지며 동작 방식도 같습니다.

map의 검색 함수들입니다.


#include <iostream>
#include <map>
using namespace std;

void main( )
{
    map<int , int > m;

    m[5] = 100;
    m[3] = 50;
    m[7] = 80;
    m[2] = 100;
    m[4] = 100;

    map<int, int >::iterator iter;

    iter = m.find( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    iter = m.lower_bound( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    iter = m.upper_bound( 5 );
    if( iter == m.end() )
        cout << "없음!" << endl;
    else
        cout << "m["<<iter->first <<"]: " << iter->second << endl;

    pair< map<int, int>::iterator, map<int, int>::iterator> iter_pair;
    iter_pair = m.equal_range(5);

    if( (iter_pair.first) == m.end() && (iter_pair.second == m.end()) )
        cout << "없음!" << endl;
    else
    {
        cout << "m["<< iter_pair.first->first <<"]: " << iter_pair.first->second <<" ~ ";
        cout << "m["<< iter_pair.second->first <<"]: " << iter_pair.second->second <<endl;
    }
}
  1. m[5]: 100
    m[5]: 100
    m[7]: 80
    m[5]: 100 ~ m[7]: 80

 동작은 set에서 설명했으므로 패스~!

그림으로 설명하면...

 

 

 

 

 

마지막으로 multimap 예제입니다.

map과 다른 점은 [] 연산자가 없으며 key 값이 중복될 수 있습니다.

#include <iostream>
#include <map>
using namespace std;

void main( )
{
    multimap<int , int > m;

    m.insert( pair<int,int>( 5, 100) );
    m.insert( pair<int,int>( 3, 50) );
    m.insert( pair<int,int>( 7, 80) );
    m.insert( pair<int,int>( 2, 100) );
    m.insert( pair<int,int>( 4, 100) );
    m.insert( pair<int,int>( 7, 200) );
    m.insert( pair<int,int>( 7, 300) );

    pair<multimap<int,int>::iterator, multimap<int, int>::iterator > iter_pair;
    iter_pair = m.equal_range( 7 );
    multimap<int,int>::iterator iter;
    for( iter = iter_pair.first ; iter != iter_pair.second ; iter++)
        cout << "m["<< iter->first <<"]: " << iter->second <<' ';
    cout << endl;

}
  1. m[7]: 80 m[7]: 200 m[7]: 300

 설명은 multiset과 같습니다.

아래는 위 예제의 그림입니다.

 



출처 : http://blog.daum.net/coolprogramming/76

728x90
저작자표시 비영리 변경금지

'Basic Programming > STL' 카테고리의 다른 글

STL - Set, MultiSet 컨테이너  (0) 2016.04.04
STL - Deque 컨테이너  (0) 2016.04.04
STL - String 컨테이너  (0) 2016.04.04
STL - List 컨테이너  (0) 2016.03.23
STL - Vector 컨테이너  (0) 2016.03.23
728x90

이번 장은 트리 자료구조를 이해하시면 조금 빠르게 공부할 수 있습니다.


set과 multiset은 '연관 컨테이너'입니다. 모든 연관 컨테이너는 '노드 기반 컨테이너'입니다. 또 모든 연관 컨테이너는 균형 2진 트리로 구현됩니다. 균형 2진 트리는 보통 레드-블랙 트리를 사용합니다. set의 특징은 유니크(unique)한 데이터(key) 셋의 균형 2진 트리로 저장합니다. multiset은 같은 데이터(key) 값을 가질 수 있는 set입니다. 그래서 set과 multiset은 데이터(key) 값을 빠르게 검색하고자 할 때 사용하면 좋은 컨테이너입니다.

 

set의 주요 개념을 그림으로 표현하면

 


set과 map은 컨테이너의 저장 데이터가 유니크합니다.

 

multiset의 주요 개념을 그림으로 표현하면

 

 

multiset과 multimap은 같은 값의 데이터를 컨테이너에 저장할 수 있습니다.

 

1, set과 multiset의 주요 특징과 함수

set은 데이터를 추가하는 push_? 류의 함수를 가지고 있지 않습니다. set뿐만 아니라 모든 연관 컨테이너는 데이터를 트리에 삽입(insert)한다는 의미에서 insert() 함수를 가지고 있습니다. 모든 연관 컨테이너에 데이터를 삽입하면 균형 2진 트리 형태로(비교 함수자를 사용하여) 크기 비교를 하여 2진 트리를 유지합니다.

또 모든 연관 컨테이너는 저장된 데이터를 빠르게 검색할 목적으로 사용되므로 검색류의 함수들을 가지고 있습니다.

 

데이터(key)의 저장과 출력( 랜덤으로 데이터를 저장합니다.)

#include <iostream>
#include <set>
using namespace std;
void main( )
{
    set<int> s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 70 );
    s.insert( 60 );

    set<int>::iterator iter;
    for( iter = s.begin(); iter != s.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;
}
  1. 10 30 50 60 70 80

 set은 같은 값의 데이터(key)를 저장할 수 없는 컨테이너입니다. 모든 연관 컨테이너는 '양방향 반복자'를 제공합니다. 출력 결과를 보면 inorder 방법으로 모든 컨테이너 요소를 탐색하는 것을 알 수 있습니다.

사실 연관 컨테이너에서 모든 요소를 출력하는 것은 별 의미가 없습니다. 연관 컨테이너라는 것이 데이터(key)를 저장하고 저장된 데이터(key)를 빠르게 검색할 목적으로 사용되기 때문입니다. 연관 컨테이너의 검색시간은 '로그 시간'입니다.

 

set은 기본 '비교 함수자'로 less<>를 사용합니다.

아래 예제는 위 예제와 같습니다.

 #include <iostream>
#include <set>
using namespace std;
void main( )
{
    set<int , less<int> > s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 70 );
    s.insert( 60 );

    set<int , less<int> >::iterator iter;
    for( iter = s.begin(); iter != s.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;
}
  1. 10 30 50 60 70 80

 set의 두번째 템플릿 인자가 '비교 함수자'입니다. less<>는 operator < 연산자를 중복한 멤버 함수를 갖는 클래스 템플릿입니다. 그래서 트리의 왼쪽 자식으로 작은 데이터(key)값이 오른쪽 자식으로 큰 데이터(key) 값이 위치합니다. 함수자 less<>은 '함수자와 함수 포인터5'에 자세히 설명되어 있습니다.

 

함수자를 greater<> 로 바꾸면 트리의 왼쪽 자식으로 큰 데이터(key)값이 오른쪽 자식으로 작은 데이터(key) 값이 위치합니다.

greater<> 사용 예제

#include <iostream>
#include <set>
using namespace std;

void main( )
{
    set<int , greater<int> > s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 70 );
    s.insert( 60 );

    set<int, greater<int> >::iterator iter;
    for( iter = s.begin(); iter != s.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;
}
  1. 80 70 60 50 30 10

 결과는 less<>와 반대로 출력됩니다.

 

이제 연관 컨테이너의 주요 함수인 검색함수를 공부합니다.

 

find() 함수 사용 예제

#include <iostream>
#include <set>
using namespace std;

void main( )
{
    set<int> s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 70 );
    s.insert( 60 );

    set<int>::iterator iter;
    iter = s.find( 80 );
    if( iter != s.end() )
        cout << *iter << endl;
    else
        cout << "없음!" << endl;

    iter = s.find( 100 );
    if( iter != s.end() )
        cout << *iter << endl;
    else
        cout << "없음!" << endl;
}
  1. 80
    없음!

 검색한 데이터(key)의 반복자를 반환합니다. 검색한 데이터가 없다면 끝을 표시하는 반복자를 반환합니다.

 

검색하는 내용에는 이 외에도 equal_range()와 lower_bound(), upper_bound()가 있습니다.

이 내용을 공부하기 위해서는 템플릿 클래스 pair<>를 알아야 합니다.

잠시 pair<> 클래스를 공부하고 가겠습니다. 아주 간단합니다.

 

pair<>는 하나의 쌍을 표현하기 위한 클래스입니다. STL의 쌍을 표현하는 모든 곳에서 pair<> 클래스를 사용합니다.

 

사용 예제입니다.

#include <iostream>
#include <string>
using namespace std;

void main( )
{
    pair<int , int> p1(10,20);
    cout << p1.first << ',' << p1.second << endl;

    pair<int , string> p2(10, "Hello!" );
    cout << p2.first << ',' << p2.second << endl;

    pair<string, string> p3( "Hello!", "Hi");
    cout << p3.first << ',' << p3.second << endl;
    cout << p3.first.c_str() << endl;
    cout << p3.first.size() << endl;
    cout << p3.second.c_str() << endl;

    cout << p3.second.size() << endl;
}

  1. 10,20
    10,Hello!
    Hello!,Hi
    Hello!
    6
    Hi
    2

 pair<>는 공용 멤버 first와 second를 가지고 있습니다. first는 첫 번째 값을 second는 두 번째 값을 저장하는 변수입니다.

그림으로 간단하게...

 

 

 

다시 set 컨테이너의 검색 함수를 돌아옵니다.

equal_range() 함수는 찾은 데이터(key)의 구간 반복자를 쌍으로 반환합니다.

사실 set은 저장한 데이터(key)가 유니크하므로(예외?를 제외하고) 반복자 쌍을 사용할 필요는 없지만 multiset이나 multimap에서는 유용하게 사용됩니다. 또 모든 연관 컨테이너는 같은 종류의 멤버 함수들을 제공합니다.

 

equal_range()의 예제입니다.

#include <iostream>
#include <set>
using namespace std;

void main( )
{
    set<int> s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 70 );
    s.insert( 60 );

    pair< set<int>::iterator, set<int>::iterator> iter_pair;
    iter_pair = s.equal_range(50);

    if( (iter_pair.first) == s.end() && (iter_pair.second == s.end()) )
        cout << "없음!" << endl;
    else
        cout << *iter_pair.first << ',' << *iter_pair.second << endl; //주의

    iter_pair = s.equal_range(100);
    if( (iter_pair.first) == s.end() && (iter_pair.second == s.end()) )
        cout << "없음!" << endl;
    else
        cout << *iter_pair.first << ',' << *iter_pair.second << endl; //주의
}
  1. 50,60
    없음!

 equal_range()는 찾음 데이터의 시작을 가리키는 반복자와 끝은 가리키는 반복자를 반환합니다.

여기서 주의할 점이 있습니다. set의 경우 찾은 데이터는 first 멤버가 되고 찾은 데이터 다음이 second가 됩니다. 이것은 lower_bound와 upper_bound에 해당합니다.

 

 그림으로 보면...

 

 

 

그래서 만약 마지막 데이터인 80을 검색하면 그림은 아래와 같습니다.

 

 

 

lower_bound와 upper_bound 예제입니다.

#include <iostream>
#include <set>
using namespace std;

void main( )
{
    set<int> s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 70 );
    s.insert( 60 );

    set<int>::iterator iter_lower;
    iter_lower = s.lower_bound(50);

    if( iter_lower == s.end() )
        cout << "없음!" << endl;
    else
        cout <<"lower: " << *iter_lower<< endl; 

    set<int>::iterator iter_upper;
    iter_upper = s.upper_bound(50);
    if( iter_upper == s.end() )
        cout << "없음!" << endl;
    else
        cout <<"upper: " << *iter_upper<< endl; //주의
}
  1. lower: 50
    upper: 60

 lower_bound()와 upper_bound() 함수 모두 찾은 데이터(key) 위치의 반복자를 반환합니다.

여기서 주의할 점은 lower_bound()은 찾은 데이터 위치의 반복자지만 upper_bound()은 찾은 데이터 위치의 다음 요소를 가리키는 반복자입니다.

 그림으로 보면...

 

 

 

 

지금까지 배운 내용은 모두 multiset에도 적용됩니다.

multiset이 set과 다른 점은 같은 값의 데이터(key)를 저장할 수 있다는 것입니다.

 

간단한 multiset의 출력입니다.

#include <iostream>
#include <set>
using namespace std;
void main( )
{
    multiset<int> s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 80 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 50 );
    s.insert( 70 );
    s.insert( 60 );

    multiset<int>::iterator iter;
    for( iter = s.begin(); iter != s.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;
}
  1. 10 30 50 50 60 70 80 80 80

 50과 80 데이터가 중복으로 저장됩니다.

 

여기서 주요 함수가 equal_range()입니다.

#include <iostream>
#include <set>
using namespace std;

void main( )
{
    multiset<int> s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 80 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 50 );
    s.insert( 70 );
    s.insert( 60 );

    multiset<int>::iterator iter;
    for( iter = s.begin(); iter != s.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;

    pair<multiset<int>::iterator, multiset<int>::iterator > iter_pair;
    iter_pair = s.equal_range( 80 );
    for( iter = iter_pair.first ; iter != iter_pair.second ; iter++)
        cout << *iter << ' ';
    cout << endl;
}
  1. 10 30 50 50 60 70 80 80 80
    80 80 80

 equal_range() 함수를 사용하면 찾은 데이터의 구간 반복자 쌍을 얻을 수 있습니다.

설명은 그림으로...

 

 

 

 

2, typedef 내장 자료형

모든 컨테이너 클래스에는 typedef되어 있는 자료형들을 제공합니다. 이 자료형중 연관 컨테이너처럼 '비교 함수자'를 가지는 컨테이너는 key_comp()라는 함수를 제공합니다.

key_comp()함수를 사용하면 우리가 2진 트리를 정렬하기 위해 지정했던 함수자(기본 함수자 less<>) 객체를 리턴합니다.

 

key_comp()함수 예제

#include <iostream>
#include <set>
using namespace std;

void main( )
{
    multiset<int> s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 70 );
    s.insert( 60 );

    less<int> key_less = s.key_comp();
    if( key_less( 10, 20 ) )
        cout << "true" << endl;
    else
        cout << "false" << endl;
    if( s.key_comp()( 10, 20) )
        cout << "true" << endl;
    else
        cout << "false" << endl;
}
  1. true
    true

 key_comp()함수가 less<> 객체를 리턴하므로 함수를 사용하여 지정했던 함수자 객체를 반환받거나 임의의 데이터를 비교할 수 있습니다.

 

greater<>를지정한 key_comp()함수 예제

#include <iostream>
#include <set>
using namespace std;

void main( )
{
    multiset<int, greater<int> > s;

    s.insert( 50 );
    s.insert( 10 );
    s.insert( 80 );
    s.insert( 30 );
    s.insert( 70 );
    s.insert( 60 );

    greater<int> key_greater = s.key_comp();
    if( key_greater( 10, 20 ) )
        cout << "true" << endl;
    else
        cout << "false" << endl;
    if( s.key_comp()( 10, 20) )
        cout << "true" << endl;
    else
        cout << "false" << endl;
}
  1. false
    false

 greater<>를 사용하므로 결과는 false 입니다.


출처 : http://blog.daum.net/coolprogramming/76

728x90
저작자표시 비영리 변경금지

'Basic Programming > STL' 카테고리의 다른 글

STL - Map, MultiMap 컨테이너  (0) 2016.04.04
STL - Deque 컨테이너  (0) 2016.04.04
STL - String 컨테이너  (0) 2016.04.04
STL - List 컨테이너  (0) 2016.03.23
STL - Vector 컨테이너  (0) 2016.03.23
728x90

deque 컨테이너는 '시퀀스 컨테이너'이며 '연속 메모리 기반 컨테이너'입니다.

연속 메모리 기반 컨테이너의 특징이 필요하고 요소의 추가, 삭제가 앞쪽과 뒤쪽에서 빈번하게 발생한다면 deque를 사용하는 것이 좋습니다.

 

deque의 주요 개념을 그림으로 표현하면

 

 

그림에서 보는 것처럼 deque는 앞과 뒤에 데이터 요소들이 추가될 수 있는 형태입니다. 또 데이터 요소를 저장하는 여러 개의 메모리 단위를 갖습니다.

그래서 요소의 추가, 삭제가 앞쪽과 뒤쪽에서 빈번하게 발생하더라도 vector나 string 처럼 메모리를 재할당하고 컨테이너의 모든 요소를 복사할 필요 없이 새로운 메모리 단위를 할당하여 새 요소만 추가하면 됩니다. 또 컨테이너의 중간 요소가 삽입(insert), 삭제(erase) 되더라도 요소들을 뒤쪽이나 앞쪽으로 모두 밀어낼 수 있으므로 vector나 string 보다 더 좋은 성능을 갖습니다. 위 그림을 이해한다면 그리 어렵지 않게 알 수 있을 것입니다.

 

1. deque의 특징과 주요 함수

 앞, 뒤로 추가, 삭제될 수 있으므로 push_front(), push_back(), pop_front(), pop_back()함수 등을 가지고 있으며 연속 메모리 기반 컨테이너이므로 []연산자 함수를 제공합니다.

 

데이터 추가와 출력

#include <iostream>
#include <deque>
using namespace std;
void main( )
{
    deque<int> dq;

    for(int i = 0 ; i < 10 ; i++)
        dq.push_back( (i+1)*10 );

    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;
}
  1. 10 20 30 40 50 60 70 80 90 100

 데이터를 추가하더라도 일정한 메모리 단위가 생성되며 요소들이 추가됩니다.

위 예제의 그림입니다. 새로운 메모리 단위만 생성할 뿐 vector처럼 메모리 재할당 및 모든 요소 복사가 발생하지 않습니다.

 

 

 

 

앞쪽에 데이터 요소를 추가하더라도 효율적으로 메모리를 생성합니다.

#include <iostream>
#include <deque>
using namespace std;

void main( )
{
    deque<int> dq;

    for(int i = 0 ; i < 10 ; i++)
        dq.push_back( (i+1)*10 );

    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;

    dq.push_front(100);
    dq.push_front(200);
    dq.push_front(300);
    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;
}
  1. 10 20 30 40 50 60 70 80 90 100
    300 200 100 10 20 30 40 50 60 70 80 90 100

 push_front()로 앞쪽에 데이터 요소를 추가하면 새로운 메모리 단위를 생성하고 데이터를 추가합니다.

위 예제의 그림입니다.

 

 

 

또 컨테이너 요소 중간에 삽입(insert), 삭제(erase) 하더라도 데이터 요소의 개수가 작은 쪽(앞쪽, 뒤쪽)을 밀어냅니다. vector 처럼 메모리가 부족하면 재할당하고 모든 요소를 복사할 필요없이 새로운 메모리 단위만 할당하면 됩니다.

간단한 insert() 예제입니다.

#include <iostream>
#include <deque>
using namespace std;

void main( )
{
    deque<int> dq;

    for(int i = 0 ; i < 10 ; i++)
        dq.push_back( (i+1)*10 );

    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;

    deque<int>::iterator iter = dq.begin()+1;

    iter = dq.insert( iter , 500);


    for( int i = 0 ; i < dq.size() ; i++)
        cout << dq[i] << ' ';
    cout << endl;
    cout << *iter << endl;
}


  1. 10 20 30 40 50 60 70 80 90 100
    10 500 20 30 40 50 60 70 80 90 100
    500

 중간에 데이터 요소를 삽입하면 삽입할 위치를 기준으로 앞쪽 요소의 개수가 작으므로 앞쪽으로 밀어냅니다. 삽입은 항상 반복자가 가리키는 위치 앞에 삽입됩니다. erase도 비슷하게 동작합니다.

위 예제의 그림입니다.

 

 

 

 

 

2, deque의 반복자

deque는 '연속 메모리 기반 컨테이너'이므로 임의 접근 반복자를 제공합니다.

 

반복자 예제

#include <iostream>
#include <deque>
using namespace std;

void main( )
{
    deque<int> dq;

    for(int i = 0 ; i < 10 ; i++)
        dq.push_back( (i+1)*10 );

    deque<int>::iterator iter;
    for( iter = dq.begin(); iter != dq.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;

    iter = dq.begin() + 3;
    cout << *iter << endl;
    iter -= 3;
    cout << *iter << endl;
}
  1. 10 20 30 40 50 60 70 80 90 100
    40
    10

deque도  vector, string처럼 '임의 접근 반복자'를 제공합니다.


출처 : http://blog.daum.net/coolprogramming/76

728x90
저작자표시 비영리 변경금지

'Basic Programming > STL' 카테고리의 다른 글

STL - Map, MultiMap 컨테이너  (0) 2016.04.04
STL - Set, MultiSet 컨테이너  (0) 2016.04.04
STL - String 컨테이너  (0) 2016.04.04
STL - List 컨테이너  (0) 2016.03.23
STL - Vector 컨테이너  (0) 2016.03.23
728x90

STL의 문자열을 다루는 전용 컨테이너가 string입니다. 사실 string은 basic_string<char>의 typedef일 뿐입니다.

 

문자열을 다루는 컨테이너는 string과 wstring 두 가지입니다.

  • string은 basic_string<char>의 typedef입니다.
  • wstring은 basic_string<wchar_t>의 typedef입니다.

 

간단하게 말해서 char는 ASCII 문자셋(8비트 문자셋)을 위한 타입이며 wchar_t는 Wide Byte Character Set(WBCS:16비트 문자셋)을 위한 타입입니다. 이것은 윈도우즈 기준이며 문자셋에 대한 내용은 다음에 공부할 기회가 있을 것입니다.(SBCS, DBCS, MBCS, WBCS)

 

그래서 string과 wstring은 저장 바이트 수만 다를 뿐 모든 멤버와 기능은 같습니다.(basic_string<>의 typedef일 뿐이므로)

우리는 char형태의 문자를 저장하는 string을 공부합니다.

 

string은 '시퀀스 컨테이너'이며 '연속 메모리 기반 컨테이너'입니다. vector와 비슷한 특징을 갖습니다.

string의 주요 개념을 그림으로 표현하면

 

 

 

 

1, string의 특징과 주요 함수

string은 문자열 전용 컨테이너로 문자열의 추상화 클래스입니다. 그래서 문자열을 쉽게 처리할 수 있는 여러 가지 기능을 제공합니다.

 

간단한 문자열 출력 예제.

#include <iostream>
#include <string>
using namespace std;
void main( )
{  
    string str = "Hello!";

    cout << str << endl;
}
  1. Hello!

 << 연산자가 중복돼 있으므로 Hello!을 출력합니다.

 

연속 메모리 기반 컨테이너의 특징은 [] 연산자 함수도 가지고 있습니다.

#include <iostream>
#include <string>
using namespace std;

void main( )
{  
    string str;

    str.push_back('H');
    str.push_back('e');
    str.push_back('l');
    str.push_back('l');
    str.push_back('o');
    str.push_back('!');

    cout << str << endl;

    for(int i = 0 ; i < str.size() ; i++)
        cout << str[i] ;
    cout << endl;
}
  1. Hello!
    Hello! 

 str[i]가 가능합니다.

 

'연속 메모리 기반 컨테이너'이므로 string은 vector처럼 임의 접근 반복자를 제공합니다.

#include <iostream>
#include <string>
using namespace std;
void main( )
{  
    string str;

    str.push_back('H');
    str.push_back('e');
    str.push_back('l');
    str.push_back('l');
    str.push_back('o');
    str.push_back('!');

    string::iterator iter;
    for( iter = str.begin() ; iter != str.end() ; iter++)
        cout << *iter;
    cout << endl;

    iter = str.begin() + 2;
    cout << *iter << endl;
    iter += 2;
    cout << *iter << endl;
    iter -= 4;
    cout << *iter << endl;
}
  1. Hello!
    l
    o
    H

임의 접근 반복자는 산술연산이 가능합니다.

또 vector와 비슷한 특징을 갖습니다.


#include <iostream>
#include <string>
using namespace std;

void main( )
{  
    string str;

    cout << "size : capacity " << endl;
    for(int i = 0 ; i < 26  ; i++)
    {
        str.push_back('A'+i);
        cout << str.size() <<":" << str.capacity() << endl;
    }
}
  1. size : capacity
    1:15
    2:15
    3:15
    4:15
    5:15
    6:15
    7:15
    8:15
    9:15
    10:15
    11:15
    12:15
    13:15
    14:15
    15:15
    16:31
    17:31
    18:31
    19:31
    20:31
    21:31
    22:31
    23:31
    24:31
    25:31
    26:31

메모리를 확장하는 정책이 조금 다를 뿐입니다.

 

문자열은 문자들의 추가가 빈번하게 발생할 수 있으므로 reserve한 정확한 크기만큼 할당하지 않고 메모리 확장 정책에 따라 일정한 크기만큼 메모리 공간을 확보합니다.


#include <iostream>
#include <string>
using namespace std;

void main( )
{  
    string str;

    str.reserve(26);

    cout << "size : capacity " << endl;
    for(int i = 0 ; i < 26  ; i++)
    {
        str.push_back('A'+i);
        cout << str.size() <<":" << str.capacity() << endl;
    }
}
  1. size : capacity
    1:31
    2:31
    3:31
    4:31
    5:31
    6:31
    7:31
    8:31
    9:31
    10:31
    11:31
    12:31
    13:31
    14:31
    15:31
    16:31
    17:31
    18:31
    19:31
    20:31
    21:31
    22:31
    23:31
    24:31
    25:31
    26:31

 26만큼의 메모리를 예약하지만 실제 메모리 확장 정책에 따라 31크기만큼 확보합니다.

 

2, 문자열 관련 함수

문자열 관련해서 여러 가지 함수를 제공합니다.

 

입력 스트림도 지원합니다.

#include <iostream>
#include <string>
using namespace std;

void main( )
{  
    string str;

    cin >> str ; // Hello! 입력
    cout << str << endl;
}
  1. Hello!

 >> 연산자가 중복되어 있습니다.

 

 

기본적인 문자열 함수.

 #include <iostream>
#include <string>
using namespace std;
void main( )
{  
    string str1= "Hello!";
    string str2;

    str2 = str1;
    cout << str1 << " , " << str2 << endl;
    if( str1 == str2 )
        cout << "true" << endl;
    str2 += str1;
    cout << str2 << endl;
    str2 = str1.substr(0, 2);
    cout << str2 << endl;
    cout << str1.find('e') << endl;
}
  1. Hello! , Hello!
    true
    Hello!Hello!
    He
    1

 쉽게 알 수 있습니다.

 

또 string 컨테이너는 char * 관련 문자열 함수를 지원합니다.

#include <iostream>
#include <string>
using namespace std;

void main( )
{  
    string str = "Hello!";

    const char * s1 = str.c_str();
    cout << s1 << endl;

    char buf[100]={0};
    str.copy(buf, 6);
    cout << buf << endl;

}

  1. Hello!
    Hello!

 c_str()함수는 '\0'문자를 포함한 문자열을 리턴합니다. 버퍼에 문자열을 받아오는 copy()함수도 지원합니다.

 

이외에 string은 '임의 접근 반복자'를 지원하므로 임의 접근 반복자를 사용하는 여러 알고리즘을 이용할 수 있습니다.


출처 : http://blog.daum.net/coolprogramming/76

728x90
저작자표시 비영리 변경금지

'Basic Programming > STL' 카테고리의 다른 글

STL - Set, MultiSet 컨테이너  (0) 2016.04.04
STL - Deque 컨테이너  (0) 2016.04.04
STL - List 컨테이너  (0) 2016.03.23
STL - Vector 컨테이너  (0) 2016.03.23
STL - Standard Template Library (STL)  (0) 2016.03.22
728x90

list는 '시퀀스 컨테이너'이며 '노드 기반 컨테이너'입니다. 그래서 데이터의 삽입, 삭제가 시퀀스 중간에 자주 발생할 때 사용하면 좋은 컨테이너입니다.

 

list의 주요 개념을 그림으로 표현하면

 

 

 

1, list의 반복자

위 그림처럼 list는 앞쪽과 뒤쪽 모두에 데이터를 추가(push_front(), push_back())할 수 있는 함수들을 제공합니다. 또 list는 이중 연결 리스트로 구현되어 있어 앞뒤로 이동 가능한 '양방향 반복자'를 제공합니다. 연결 리스트의 특징인 중간에 삽입, 삭제가 빈번하게 발생할 때 효율적인 컨테이너입니다.

 

list 간단한 예제(데이터 앞쪽, 뒤쪽 추가)

#include <iostream>
#include <list>
using namespace std;

void main( )
{
    list<int> lt;


    lt.push_back(10); // 리스트 뒤쪽에 추가
    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    list<int>::iterator iter;
    for( iter = lt.begin() ; iter != lt.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;

    lt.push_front(60); // 리스트 앞쪽에 추가
    lt.push_front(70);
    lt.push_front(80);
    for( iter = lt.begin() ; iter != lt.end() ; iter++)
        cout << *iter << ' ';
    cout << endl;

}

  1. 10 20 30 40 50
    80 70 60 10 20 30 40 50

 list는 데이터를 앞뒤에 추가할 수 있는 '시퀀스 컨테이너'로 push_front()와 push_back()함수를 제공합니다.(push_front()를 제공하는 컨테이너는 list와 deque뿐입니다.)

10~50까지 리스트 뒤쪽에 추가되며 60, 70, 80은 계속 앞쪽에 추가됩니다.

 

 

 

 

  list는 '연속 메모리 기반 컨테이너'가 아니므로 operator[]연산자는 가지고 있지 않고 반복자를 통해서만 컨테이너의 요소들에 접근할 수 있습니다. list는 양방향 반복자를 제공합니다. 그래서 반복자에 산술 연산은 불가능하다.(산술 연산이 가능한 반복자는 '임의 접근 반복자'뿐입니다. '연속 메모리 기반 컨테이너'가 임의 접근 반복자를 제공합니다.) 8개의 STL 컨테이너 모두 양방향 반복자 이상을 제공하며 이 중 '연속 메모리 기반 컨테이너'인 string, vector, deque는 산술 연산이 가능한 임의 접근 연산자를 제공합니다.

 

다음은 양방향 반복자를 사용하는 예제입니다.

#include <iostream>
#include <list>
using namespace std;
void main()
{
    list<int> lt;


    lt.push_back(10);

    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    list<int>::iterator iter;
    for( iter = lt.begin() ; iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    iter--;

// iter += 2; 산술 연산은 불가능

    cout << *iter << endl;
    cout << *--iter << endl;
    cout << *--iter << endl;
    cout << *--iter << endl;
    cout << *--iter << endl;

}

  1. 10 20 30 40 50
    50
    40
    30
    20
    10

 양방향 반복자로 반복자에 ++, -- 연산자 모두 가능하며 산술연산은 불가능합니다.

 

 

 

  모든 STL 컨테이너는 시작과 끝을 가리키는 반복자 쌍을 반환하는 begin()과 end()를 가진다고 했습니다. 또 모든 컨테이너는 이와 반대인 rbegin(), rend() 함수로 끝과 시작을 가리키는 반복자 쌍을 제공합니다.

 

rbegin()과 rend()함수의 사용

#include <iostream>
#include <list>
using namespace std;

void main()
{
    list<int> lt;

    lt.push_back(10);

    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    list<int>::iterator iter;
    for( iter = lt.begin() ; iter != lt.end(); iter++)
        cout << *iter << ' ';
    cout << endl;

    list<int>::reverse_iterator riter;
    for( riter = lt.rbegin() ; riter != lt.rend(); riter++)
        cout << *riter <<' ';
    cout << endl;
}

  1. 10 20 30 40 50
    50 40 30 20 10

 list의 뒤에서 앞쪽으로 이동하도록 reverse_iterator를 제공합니다. 이 시작과 끝을 가리키는 반복자 쌍을 반환하는 함수가 rbegin()과 rend()입니다. 반복자의 자세한 내용은 뒤쪽에서 다시 공부합니다.

 

 

 

2, list의 주요 특징과 함수

  list의 장점 중 하나가 데이터 요소의 삽입, 삭제시에 다른 '시퀀스 컨테이너'보다 '효율적이다'는 것입니다. 이유는 '연속 메모리 기반 컨테이너'처럼 컨테이너 요소들이 밀려나지 않기 때문입니다.

모든 컨테이너는 insert()함수와 erase()함수를 가지고 있어 반복자가 가리키는 위치의 요소를 삽입하거나 삭제할 수 있습니다. 또 STL이 제공하는 여러 삽입, 삭제 알고리즘을 사용할 수 있습니다.

이때 '연속 메모리 기반 컨테이너'는 주의할 점이 있습니다. 연속 메모리 기반 컨테이너는 요소의 삽입과 삭제가 '선형 시간'이라는 것입니다. 또 메모리가 재할당될 수 있고 컨테이너의 모든 다른 요소들이 복사될 수 있다는 것입니다.

 

vector와 list의 삽입 예제

#include <iostream>
#include <list>
#include <vector>
using namespace std;

void main()
{
    vector<int> v;
    list<int> lt;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);


    lt.push_back(10);

    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    vector<int>::iterator viter = v.begin();
    viter++;
    viter = v.insert( viter, 80); // vector의 두 번째 요소로 삽입
     cout << *viter << endl;

    list<int>::iterator liter = lt.begin();
    liter++;

    liter = lt.insert( liter, 80); // list의 두 번째 요소로 삽입
      cout << *liter << endl;

    cout << " vector : ";
    for( viter = v.begin() ; viter != v.end(); viter++)
        cout << *viter << ' ';
    cout << endl;

    cout << " list : ";
    for( liter = lt.begin() ; liter != lt.end(); liter++)
        cout << *liter << ' ';
    cout << endl;
}

  1. 80
    80
     vector : 10 80 20 30 40 50
     list : 10 80 20 30 40 50

 결과는 같지만 내부적인 동작은 전혀 다릅니다. vector의 요소는 밀려나며 메모리 재할당 및 복사가 발생할 수 있습니다.

아래는 위 예제의 그림입니다.

 

와

 

 

 

아래는 erase()함수 예제입니다.

#include <iostream>
#include <list>
#include <vector>
using namespace std;

void main()
{
    vector<int> v;
    list<int> lt;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);


    lt.push_back(10);    lt.push_back(20);
    lt.push_back(30);
    lt.push_back(40);
    lt.push_back(50);

    vector<int>::iterator viter = v.begin();
    viter++;
    viter = v.erase( viter); // vector의 두 번째 요소로 삭제
     cout << *viter << endl;

    list<int>::iterator liter = lt.begin();    liter++;
    liter = lt.erase( liter); // list의 두 번째 요소로 삭제
     cout << *liter << endl;

    cout << " vector : ";
    for( viter = v.begin() ; viter != v.end(); viter++)
        cout << *viter << ' ';
    cout << endl;

    cout << " list : ";
    for( liter = lt.begin() ; liter != lt.end(); liter++)
        cout << *liter << ' ';
    cout << endl;
}

  1. 30
    30
     vector : 10 30 40 50
     list : 10 30 40 50

 erase()함수를 사용한 삭제도 '삽입' 동작과 같은 특징을 보입니다.

 

컨테이너 요소의 삽입, 삭제는 다음에 다시 공부하겠습니다.


출처 : http://blog.daum.net/coolprogramming/76

728x90

'Basic Programming > STL' 카테고리의 다른 글

STL - Set, MultiSet 컨테이너  (0) 2016.04.04
STL - Deque 컨테이너  (0) 2016.04.04
STL - String 컨테이너  (0) 2016.04.04
STL - Vector 컨테이너  (0) 2016.03.23
STL - Standard Template Library (STL)  (0) 2016.03.22
728x90

vector는 STL 컨테이너에서 가장 많이 사용하는 컨테이너 중 하나입니다.

 

STL 컨테이너는 각각 자신만의 특징을 가지고 있습니다. 각 컨테이너의 특징은 성능('시간 복잡도'나 '공간 복잡도')과 STL 여러 요소에 영향을 주기 때문에 각 컨테이너의 특징을 이해하는 것은 상당히 중요합니다. 그래야 자신의 프로그램에 맞는 적절한 컨테이너를 선택하여 사용할 수 있습니다.

 

vector의 주요 특징은 앞장에서 배운 것처럼 '시퀀스 컨테이너'이면서 '연속 메모리 기반 컨테이너'입니다. 또 컨테이너에 데이터가 삽입될수록 메모리가 자라나게 됩니다. 연속 메모리 기반이므로 메모리가 자라나면 기존 메모리를 삭제하고 새로운 메모리를 재할당하여 사용합니다.

vector의 주요 개념을 그림으로 표현하면

 

 

 

컨테이너에 앞서 계산 성능을 평가하는 '계산 시간 복잡도'를 간단히 정리하고 가겠습니다.

시간 복잡도는 "어떤 일을 얼마나 오랜 시간 동안 수행해야 하는가?"에 대한 함수로 나타내는 것을 의미합니다.

'시간 복잡도'는 크게 네 가지로 볼 수 있습니다.

  • 상수 시간 복잡도(constant time complexity) : 작업양이 증가할 때 변하지 않는 일정한 수행 성능을 보인다는 것.
  • 로그 시간 복잡도(logarithmic time complexity) : 작업양이 증가할 때 수행 시간도 일정하게 늘어나지만, 로그 함수의 비율로 늘어나는 것.
  • 선형 시간 복잡도(linear time complexity) : 작업양이 증가할 때 수행 시간도 비례해서 늘어나는 것.
  • 지수 시간 복잡도(exponential time complexity) : 작업양이 증가할 때 수행 시간도 지수함수의 비율로 늘어나는 것.

그림으로 보면

 

 

 

1, vector의 특징과 주요 함수

예제로 vector의 함수들을 공부합니다.

 

가장 간단한 예제(정수 추가 후 출력)

#include <iostream>
#include <vector>
using namespace std;
void main ( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);
    v.push_back(40);
    v.push_back(50);

    for( int i = 0 ; i < v.size() ; i++)
        cout << v[i] << ' ';
    cout << endl;
}
  1. 10 20 30 40 50
  •  push_back()컨테이너 v에 요소를 추가하는 함수입니다. (모든 시퀀스 컨테이너는 요소를 끝에 추가할 수 있고 push_back()함수를 가지고 있습니다.)
  •  size()는 v 요소의 개수를 반환합니다. (모든 컨테이너는 컨테이너의 요소 개수를 반환하는 size()함수를 가지고 있습니다.)
  •  operator[]() 함수는 i 번째 인덱스의 요소를 반환합니다.(모든 연속 메모리 기반의 컨테이너와 map은 operator[]()함수를 가지고 있습니다.)

 

vector의 중요한 특징 중 하나가 연속 메모리 기반 컨테이너이므로 요소가 추가될 때 메모리가 자라난다는 것입니다. 추가될 때마다 메모리가 자라난다는 것은 메모리를 재할당해야(메모리의 크기를 늘려야 하므로) 한다는 것을 말합니다. 그래서 너무 비효율적으로 메모리 재할당되는 것을 막기 위해 요소가 추가될 때마다 메모리를 늘리지 않고 미리 여유 메모리 공간을 확보합니다.(여유 메모리의 크기를 늘리는 정책은 컴파일러마다 조금씩 다릅니다.)

 

중요 특징 - capacity(할당된 메모리 공간의 크기)와 size(저장된 데이터 요소의 개수)

#include <iostream>
#include <vector>
using namespace std;

void main ( )
{
    vector<int> v;


    cout << "size"<< ":" << "capacity " << endl;
    v.push_back(10);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(20);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(30);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(40);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(50);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(60);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(70);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(80);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(90);
    cout << v.size() << " : " << v.capacity() << endl;
    v.push_back(100);
    cout << v.size() << " : " << v.capacity() << endl;

    for( int i = 0 ; i < v.size() ; i++)
        cout << v[i] << ' ';
    cout << endl;
}

  1. size:capacity
    1 : 1
    2 : 2
    3 : 3
    4 : 4
    5 : 6
    6 : 6
    7 : 9
    8 : 9
    9 : 9
    10 : 13
    10 20 30 40 50 60 70 80 90 100

10개의 정수를 push_back()하고 있습니다. size는 v에 저장된 요소의 개수이며 capacity는 할당된 메모리 공간의 크기입니다. VS2008 컴파일러는 기존 메모리의 반만큼의 메모리를 더 늘려서 메모리를 할당합니다. 또 기존 메모리의 모든 컨테이너 요소를 재할당된 메모리로 복사합니다.

 

 

  

 

 

그래서 컨테이너 요소의 개수가 유동적인 곳에는 vector가 비효율적입니다.

위 내용을 해결하는 방법은 두 가지 정도가 있습니다.

첫째는 생성자를 이용하여 메모리 공간(capacity)과 크기(size)을 미리 확보하고 초기화하는 것입니다.

#include <iostream>
#include <vector>
using namespace std;

void main( )
{
    vector<int> v(10);

    cout << v.size() << " : " << v.capacity() << endl;
    for(int i = 0 ; i < v.size() ; i++)
        cout << v[i] << ' ';
    cout << endl;

    for(int i = 0 ; i < v.size() ; i++)
        v[i] =  (i+1)*10;

    for(int i = 0 ; i < v.size() ; i++)
        cout << v[i] << ' ';
    cout << endl;
}
  1. 10 : 10
    0 0 0 0 0 0 0 0 0 0
    10 20 30 40 50 60 70 80 90 100

 v(10) 처럼 size를 10으로 설정하면 0으로 초기화된 size 10개와 메모리 공간이 확보됩니다. 값을 변경할 때 operator[]()함수를 사용했습니다.


아래는 위 예제의 그림입니다.( vector<int> v(10); )

 

 

 

둘째는 reserve()함수를 이용하여 메모리 공간(capacity)만 미리 확보하는 것입니다.

#include <iostream>
#include <vector>
using namespace std;

void main( )
{
    vector<int> v;

    v.reserve(10);

    cout << "size"<< ":" << "capacity " << endl;
    cout << v.size() << " : " << v.capacity() << endl;
    for(int i = 0 ; i < 10 ; i++)
    {
        v.push_back((i+1)*10);
        cout << v.size() << " : " << v.capacity() << endl;
    }

    for(int i = 0 ; i < v.size() ; i++)
        cout << v[i] << ' ';
    cout << endl;
}
  1. size:capacity
    0 : 10
    1 : 10
    2 : 10
    3 : 10
    4 : 10
    5 : 10
    6 : 10
    7 : 10
    8 : 10
    9 : 10
    10 : 10
    10 20 30 40 50 60 70 80 90 100

메모리 공간(capacity)은 미리 확보했으므로 push_back()함수를 호출해도 메모리 재할당이 발생하지 않습니다.

 

아래는 위 예제의 그림입니다. ( v.reserve( 10 ); )

 

 

 

2, vector의 반복자

모든 컨테이너는 자신만의 반복자를 갖습니다.

반복자를 사용하는 간단한 예제

#include <iostream>
#include <vector>
using namespace std;

void main( )
{
    vector<int> v;

    for(int i = 0 ; i < 10 ; i++)
        v.push_back(i+1);

    vector<int>::iterator iter;
    for( iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter << endl;
}
  1. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10

 모든 컨테이너의 반복자는 각 컨테이너 클래스의 내포 클래스(vector<int>::iterator)로 정의되어 있습니다. 또 반복자는 반복자끼리 비교할 수 있는 ==과 != 가 연산자 중복되어 있으며 다음 요소로 이동하도록 ++연산자와 반복자가 가리키는 컨테이너 요소에 접근하도록 *연산자와 ->연산자가 중복되어 있습니다.

 

 

 

vector의 반복자는 임의 접근 반복자로 반복자에 산술 연산이 가능합니다.

#include <iostream>
#include <vector>
using namespace std;

void main( )
{
    vector<int> v;

    for(int i = 0 ; i < 10 ; i++)
        v.push_back(i+1);

    vector<int>::iterator iter;
    for( iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter << endl;

    iter = v.begin();
    iter += 3;
    cout <<"[3] : " << *iter << endl;
    *iter = 0;
    cout <<"[3] : " << *iter << endl;
}
  1. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    [3] : 4
    [3] : 0

vector의 반복자는 iter에 산술연산이 가능합니다. (모든 연속메모리 기반 컨테이너는 임의 접근 반복자를 제공합니다.)

또 *연산자를 사용하여 반복자가 가리키는 메모리에 접근하고 변경할 수 있습니다.

그림으로 보면

 

 

 

만약 읽기만 가능한 반복자를 사용해야 한다면 const_iterator를 사용해야합니다.

#include <iostream>
#include <vector>
using namespace std;

void main( )
{
    vector<int> v;

    for(int i = 0 ; i < 10 ; i++)
        v.push_back(i+1);

    vector<int>::const_iterator iter;
    for( iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter << endl;

    iter = v.begin();
    iter += 3;
    cout <<"[3] : " << *iter << endl;
    //*iter = 0; 에러! const_iterator는 가리키는 요소를 변경할 수 없습니다.
    cout <<"[3] : " << *iter << endl;
}
  1. 1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    [3] : 4
    [3] : 4

 iter는 상수 반복자(const iterator)로 가리키는 요소의 변경이 불가능합니다. 반복자는 STL의 마지막 부분에서 자세히 공부합니다.


출처 : http://blog.daum.net/coolprogramming/76

728x90

'Basic Programming > STL' 카테고리의 다른 글

STL - Set, MultiSet 컨테이너  (0) 2016.04.04
STL - Deque 컨테이너  (0) 2016.04.04
STL - String 컨테이너  (0) 2016.04.04
STL - List 컨테이너  (0) 2016.03.23
STL - Standard Template Library (STL)  (0) 2016.03.22
728x90

STL은 표준 C++ 라이브러리의 일부분으로 Standard Template Library의 약자입니다.

STL은 사람마다 조금씩 다른 정의를 내립니다. C++의 권위자인 Scott Meyers는 STL을 "반복자를 가지고 동작하는 C++ 표준 라이브러리의 일부분"이라고 정의했습니다.

STL은 우리가 C++프로그래밍에서 만들어야 하는 여러 가지 자료구조 클래스와 알고리즘 등을 미리 만들어 놓은 라이브러리로 반복자라는 놈을 통해서 동작하는 라이브러리입니다.

 

STL의 주요 구성 요소로 컨테이너, 반복자, 알고리즘, 함수자가 있습니다.

  • 컨테이너(Container) : 객체들을 저장하는 객체 혹은 클래스(vector, list, string, map 등)
  • 반복자(iterator) : 컨테이너에 저장된 요소를 순회하고 접근하는 객체 혹은 클래스(추상화)
  • 알고리즘(Algorithm) : 데이터를 다루기위한 일련의 함수(find, short, search 등)
  • 함수자(Functor) : 함수처럼 동작하는 객체로 operator() 연산자를 오버로딩한 클래스의 객체

 

그림으로 간단하게..

 

 

 

1, 컨테이너

컨테이너는 동일한 타입의 객체를 저장, 관리할 목적으로 만들어 놓은(추상화한) 클래스입니다.(혹은 그 컨테이너 클래스에 의해 만들어진 객체를 컨테이너라고도 합니다.)


컨테이너는 크게 두 가지로 나뉩니다.

  • 표준 시퀀스 컨테이너(standard sequence container) : vector, string, deque, list인 선형방식의 컨테이너
  • 표준 연관 컨테이너(standard associative container) : set, multiset, map, multimap인 비선형방식의 컨테이너

 

 

또 컨테이너는 데이터를 하나의 메모리 단위로 저장하느냐에 따라 두 가지로 나뉩니다.

  • 연속 메모리 기반 컨테이너(contiquous-memory) : 보통 데이터 여러개가 하나의 메모리 단위에 저장합니다. 배열 기반 컨테이너(array-based container)라고도 합니다.
  • 노드 기반 컨테이너(node-based) : 데이터 하나를 하나의 메모리 단위에 저장합니다.

 

위 두 그림을 꼭 기억하세요. 컨테이너의 종류는 상당히 중요합니다. 종류에 따라 여러 가지 특징(성능, 무효화, 알고리즘 사용)이 달라지기 때문입니다. 자세한 내용은 다음에 하나하나 공부하도록 하겠습니다.

 

대표적인 컨테이너가 vector입니다.

간단한 vector 예제입니다.

#include <iostream>
#include <vector>
using namespace std;
void main( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    for(int i = 0 ; i < v.size() ; i++)

        cout << v[i] << endl;

}

  1. 10
  2. 20
  3. 30

 vector<int> 클래스와 이 클래스로 생성한 객체 v가 컨테이너입니다. push_back()과 size()는 멤버 함수입니다. 

v[i]는 operator[]() 멤버 함수인 연산자 중복 함수입니다. 컨테이너 v는 int형 객체(정수) 10, 20, 30을 저장합니다.

 

2, 반복자

반복자는 포인터와 비슷한 놈이라고 알아두시면 되겠습니다. 단 반복자는 컨테이너에 저장된 객체들에 접근하고 순회하는 일반화된 방법을 제공합니다.

그래서 반복자는 몇 가지 특징을 가져야 합니다.

  • 컨테이너 내부의 객체를 가리키고 접근할 수 있어야 한다.
  • 컨테이너 내부의 모든 객체를 순회할 수 있어야 한다.

STL의 모든 컨테이너는 자신만의 반복자를 제공합니다.

 

반복자는 조작 방법에 따라 다섯 가지로 나뉩니다.

  • 입력 반복자(input iterator) : 현 위치의 데이터를 읽기만 가능한 반복자
  • 출력 반복자(output iterator) : 현 위치에 데이터를 쓰기만 가능한 반복자
  • 순방향 반복자(forward iterator) : 입력, 출력 반복자 기능 +  순방향으로 이동 가능한 반복자
  • 양방향 반복자(bidirectional iterator) :  순방향 반복자 기능 + 역방향으로 이동 가능한 반복자
  • 임의 접근 반복자(random access iterator) : 양방향 반복자 기능 + 반복자의 산술 연산이 가능한 반복자

 

임의 접근 반복자를 예로 보겠습니다. vector는 임의 접근 반복자를 제공합니다.

#include <iostream>
#include <vector>
using namespace std;

void main( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(20);
    v.push_back(30);

    vector<int>::iterator iter;
    for(iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter << endl;

    iter = v.begin()+2;
    cout << *iter << endl;
}

  1. 10
    20
    30
  2. 30

 vector<int>::iterator처럼 반복자 클래스는 vector 클래스의 내포 클래스로 정의되어 있습니다. begin() 멤버 함수는 컨테이너 v에 저장된 첫 번째 객체를 가리키는 반복자를 반환합니다. end() 멤버 함수는 저장 객체의 끝을 의미하는 반복자를 리턴합니다. 또 임의 접근 반복자는 v.begin()+2처럼 반복자에 산술 연산이 가능합니다.

반복자는 뒤에서 다시 공부합니다.

 

3, 알고리즘

일반적인 용어의 알고리즘은 어떤 문제를 해결하기 수행 절차나 방법을 의미합니다. 만약 '정렬'이라는 문제가 주어진다면 정렬이라는 문제를 해결하는 방법(알고리즘)은 무수히 많습니다. 또 검색, 삭제, 복사 등의 문제도 모두 수많은 해결 방법이 존재합니다. 이런 해결 방법의 절차를 알고리즘이라 합니다.

 

 STL은 프로그램에서 반복되는 여러 가지 문제들의 해결 방법(알고리즘)을 일반화된 함수(템플릿 함수)로 제공합니다.

 

대표적인 정렬 알고리즘입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void main( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(80);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);

    vector<int>::iterator iter;
    for(iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter <<' ';
    cout << endl;

    sort(v.begin(), v.end());

    for(iter = v.begin() ; iter != v.end() ; iter++)
        cout << *iter <<' ';
    cout << endl;
}
  1. 10 80 30 20 50
    10 20 30 50 80

 모든 알고리즘은 반복자로 동작합니다. sort()는 v의 첫 번째 객체를 가리키는 반복자와 마지막을 의미하는 반복자를 인자로 받아 정렬합니다.

 

for 루프도 for_each()알고리즘을 사용하여 작성할 수 있습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void Print(const int& n)
{
    cout << n <<' ';
}
void main( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(80);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);

    for_each(v.begin(), v.end(), Print);
    cout << endl;

    sort(v.begin(), v.end());

    for_each(v.begin(), v.end(), Print);
    cout << endl;
}
  1. 10 80 30 20 50
    10 20 30 50 80

 for_each()는 v.begin() 반복자부터 v.end()반복자까지 v 컨테이너에 저장된 모든 객체를 인자로 Print함수를 호출합니다. for_each() 알고리즘은 QuicStart2의 '함수 포인터와 함수자3'를 참고하세요.

알고리즘은 뒤에서 다시 공부합니다.

 

for_each()는 아래와 비슷하게 정의되어 있습니다.

template<class _InIt,class _Fn1>
inline  _Fn1 for_each(_InIt _First, _InIt _Last, _Fn1 _Func)
{  
    for (; _First != _Last; ++_First)
        _Func(*_First);
    return (_Func);
}

 

4, 함수자

함수자는 함수처럼 사용할 수 있는 객체입니다. 함수자는 멤버 함수 operator()를 가지고 있기 때문에 객체를 함수처럼 사용할 수 있습니다.

 함수자는 QuickStart2의 '함수 포인터와 함수자2'를 참고하세요.

 

대표적인 함수자 클래스가 less<>와 greater<> 입니다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

void Print(const int& n)
{
    cout << n <<' ';
}
void main( )
{
    vector<int> v;

    v.push_back(10);
    v.push_back(80);
    v.push_back(30);
    v.push_back(20);
    v.push_back(50);

    for_each(v.begin(), v.end(), Print);
    cout << endl;

    sort(v.begin(), v.end(), less<int>() );

    for_each(v.begin(), v.end(), Print);
    cout << endl;

    sort(v.begin(), v.end(), greater<int>() );

    for_each(v.begin(), v.end(), Print);
    cout << endl;
}
  1. 10 80 30 20 50
    10 20 30 50 80
    80 50 30 20 10

  sort()함수의 세 번째 인자로 비교 함수자(predicate)를 전달하면 이 비교 함수자를 이용하여 정렬 객체를 비교합니다.

 

함수자 greater<>와 less는 아래와 비슷하게 정의되어 있습니다.

template<class _Ty>
struct greater{  
    bool operator()(const _Ty& _Left, const _Ty& _Right) const
    {  
        return (_Left > _Right);
    }
};
template<class _Ty>
struct less
{
    bool operator()(const _Ty& _Left, const _Ty& _Right) const
    {  
        return (_Left < _Right);
    }
};



728x90

'Basic Programming > STL' 카테고리의 다른 글

STL - Set, MultiSet 컨테이너  (0) 2016.04.04
STL - Deque 컨테이너  (0) 2016.04.04
STL - String 컨테이너  (0) 2016.04.04
STL - List 컨테이너  (0) 2016.03.23
STL - Vector 컨테이너  (0) 2016.03.23

+ Recent posts

티스토리툴바