"unordered"의 의미

표준 C++ 라이브러리에는 set, multiset, map, multimap 4개의 컨테이너가 준비되어 있습니다. 이것들은 binary-tree를 그 구현에 이용한 것입니다. 대소 관계에 근거해 요소를 binary-tree로 나누어 내린 것으로 삽입이나 검색에 필요로 하는 시간 계산량은 Ο(logN) 즉 요소 수의 log에 비례합니다.

 

이번 TR1에서 새롭게 추가된 unordered_set, unordered_multiset, unordered_map, unordered_multimap은 종래의 set, multiset, map, multimap 과 각각 기능적으로는 같습니다. 다른 것은 그 구현이 binary-tree는 아니고 해시표(hash-table)가 이용되고 있습니다. 최대의 특징은 그 스피드에 있습니다.

 

 

해시표가 빠른 이유

해시표는 간단하게 말하면 「일렬로 줄선 버켓」입니다. 각각의 버켓에는 일련 번호가 붙어 있어 각 버켓에는 복수의 볼(요소)을 저장 할 수 있습니다. 버켓은 볼을 요소로 하는 가변장 배열이라고 생각해도 좋을 것입니다.

 

여기에 버켓이 한 개 있고 N개의 볼이 들어가 있다고 합시다. 볼에는 번호가 써 있습니다. 이 때 적당한 번호를 지정하고 그 번호가 쓰여진 볼을 버켓안에서 찾아오는 것을 생각합니다.

버켓 안의 볼은 무 순서이기 때문에 목적의 볼을 찾아내려면 한개씩 꺼내어 그것이 목적의 것인지를 조사하지 않으면 안됩니다. 행운이 있다면 첫번째에 바로 찾을 수 있지만 최악의 케이스는 끝까지 조사했지만 발견되지 않았을 때입니다. 평균하면 볼 찾기에 필요한 비교 회수는 N/2 즉 검색에 필요로 하는 시간은 N에 비례합니다.

 

그럼 버켓을 두 개 준비하여 짝수 차례의 볼을번 버켓에 / 홀수 차례의 볼을번 버켓에 넣는다고 약속해 둡니다. 그러면 적당한 번호의 볼을 찾아내려면 그 번호가 짝수라면번 버켓 / 홀수라면 1  버켓의 내용만을 조사하면 된다. 볼의 번호에 큰 편향이 없으면 각 버켓 내의 볼은 거의 동수의 N/2 이니까 검색에 필요로 하는 시간은 버켓 한 개의 경우의 반입니다.

 

이 상태로 버켓 수를 M개로 하여 각 볼은 거기에 붙은 번호를 M으로 나눈 나머지가 나타내 보이는 버켓에 넣읍시다. 그러면 검색 시에 조사하지 않으면 안 되는 볼의 수, 즉 검색에 필요로 하는 시간은 N/M으로 단축됩니다.

 

그 말은 M N과 같은 정도로 해 두면 N/M이 대체로 1이 됩니다. 이것은 볼의 총수에 관계없이 거의 순간에 검색이 종료하는 것을 의미합니다. 요소의 검색 대상이 되는 모집단의 요소 수를 1로 접근하는 것으로 검색 스피드를 올리려는 전략입니다.

 

여기서 중요한은 각 볼을 어느 버켓에 저장 할까를 결정하는 수단입니다. 상기의 예에서는 「볼 번호를 버켓 수로 나눈 나머지」라고 하고 있습니다만 만약 볼 번호에 큰 편향이 있으면 버켓 내의 볼수에 편향이 생겨 검색 시간이 성장해 버립니다. 볼이 많이 찬 버켓과 거의 텅 빔의 버켓이 가능하게 되니까요.

 

요소()x 로부터 어떠한 일의인 값(버켓 번호)을 도출하는 함수를 「해쉬 함수 h(x)」라고 이름 붙입시다.

해쉬 함수 h가 채우지 않으면 안 되는 조건은:

x = y 이라면 h(x) = h(y)

입니다. 그렇지 않으면 볼 검색시에 들어가 있어야할 "모레의 버켓"안을 찾아 버리게 될테니까.

다만 x ≠ y  h(x) = h(y) 되는 일이 있습니다. 해쉬 함수 버켓 번호를 결정하므로 x y는 같은 버켓에 저장 됩니다.

해쉬 함수가 돌려주는 값(해시 값)이 같은 요소군을 동의어(synonym:동의어)라고 부르고 있습니다.

 

클래스 템플릿: unordered_set

TR1에는 해시표를 사용한 4종의 컨테이너가 정의되고 있습니다.

unordered_set : 요소의 중복을 허락하지 않는 집합

unordered_multise t: 요소의 중복을 허락하는 집합

unordered_map : 요소의 중복을 허락하지 않는 사전

unordered_multimap : 요소의 중복을 허락하는 사전

 

 

이것들을 대표하여 unordered_set에 대해서 그 개요를 설명합니다.

namespace std {

namespace tr1 {

// [6.3.4.3] Class template unordered_set

template < class Value,

class Hash = hash,

class Pred = std::equal_to,

class Alloc = std::allocator >

class unordered_set;

}

}

 

unordered_set 의 템플릿 인수는4.

Value : 컨테이너 요소의 형태

Hash : Value 로부터 해시 값을 요구하는 함수 오브젝트

Pred : Va lue 가 동일할 때 true 되는 함수 오브젝트

Alloc : allocater

 

Hash 의 디폴트 인수는 hash Value를 인수로 하여 size_t를 돌려주는 operator()를 구현합니다. 편입형과 문자열에 대해서는 표준 헤더 functional 에 정의되고 있습니다. 이것들 이외의 형태를 요소로 하는 unordered컨테이너를 이용할 때는 적절한 해쉬 함수 오브젝트를 주지 않으면 안됩니다.

 

 헤더: functional 에 정의된 hash

namespace std {

namespace tr1 {

template < class T>

struct hash : public std::unary_function size_t >

{

std:: size_t operator ()(T val) const ;

};

 

template <> struct hash< bool >;

template <> struct hash< char >;

template <> struct hash< signed char >;

template <> struct hash< unsigned char >;

template <> struct hash< wchar_t >;

template <> struct hash< short >;

template <> struct hash< unsigned short >;

template <> struct hash< int >;

template <> struct hash< unsigned int >;

template <> struct hash< long >;

template <> struct hash< unsigned long >;

template <> struct hash< float >;

template <> struct hash< double >;

template <> struct hash< long double >;

template<class T> struct hash<T*>;

template <> struct hash<std::string>;

template <> struct hash<std::wstring>;

}

}

 

컨테이너에 대한 요소의 삽입/삭제/검색 및 열거에 관한 인터페이스는 종래의 set과 다르지 않습니다:

insert : 요소의 삽입


erase
: 요소의 삭제


clear
: 모든 요소를 삭제하여 컨테이너를 비운다


find
: 요소의 검색


count
: 검색에 의해서 일치한 요소 수


equal_range
: 검색에 의해서 일치하는 요소 위치의 범위

 

unordered 컨테이너 독자적인 멤버 함수를 이하에 나타냅니다

 

 

bucket_count

size_type bucket_count() const

  컨테이너 내의 버켓의 수를 돌려줍니다.

 

max_bucket_count

size_type max_bucket_count() const

 컨테이너 내에 내포 할 수 있는 버켓의 최대수를 돌려줍니다.


bucket

size_type bucket(k)

 요소 k가 저장 될 버켓의 번호를 돌려줍니다.


bucket_size

size_type bucket_size(n)


 n번째의 버켓에 격납된 요소수를 돌려줍니다.

 

begin

local_iterator begin(n)

const_local_iterator begin(n) const

 n번째의 버켓에 저장된 요소의 선두 위치를 돌려줍니다.


end

local_iterator end(n)

const_local_iterator end(n) const

 n번째의 버켓에 격납된 요소의 마지막 위치를 돌려줍니다.


load_factor

float load_factor() const

 버켓에 저장 되고 있는 요소 수의 평균 값 즉 요소 수/버켓 수를 돌려줍니다.


max_load_factor

float max_load_factor() const

 버켓에 저장되는 요소 수의 평균 값의 상한을 돌려줍니다. 요소의 삽입에 의해서 이 상한 값을 넘었을 때 새로운 버켓이 추가되어 각 요소가 버켓에 재 배분됩니다.

 

void max_load_factor( float z)

 버켓에 저장 되는 요소 수의 평균 값의 상한을 z로 설정합니다.


rehash

void rehash(size_type n)

 버켓 수가 적어도  n이 되도록 버켓 수가 조정되어 각 요소가 재배분됩니다.

 

 

 

set 과의 속도 비교

마지막으로 해시표에 의한  unordered_set binary-tree에 의한 set 과의 속도를 비교해 봅시다. 1~100000의 난수를 2백만개 삽입했을 때의 각각의 소요 시간을 계측합니다.

 

set    unordered_set 속도 비교

// min/max매크로의 간섭 방지

#define NOMINMAX

#include <windows.h>

#include <iostream>

#include <set>

#include <unordered_set>

#include <unordered_map>

#include <random>

 

using namespace std;

 

int main()

{

set< int > s;

tr1::unordered_set< int > us;

const int N = 100000;

tr1::mt19937 rng; // 메르센누·트이스타

tr1::uniform_int<> dice(1,N); // 정수일 모양 분포

tr1::variate_generator     <tr1::mt19937&, tr1::uniform_int<> > sample(rng, dice);

 

long t;

const int TIMES = 2000000;

rng.seed(12345);

t = GetTickCount();

for ( int i = 0; i < TIMES; ++i ) {

s.insert(sample());

}

t = GetTickCount() - t;

cout << t << "(set)\n" ;

 

rng.seed(12345);

//us.rehash(N); /* 버켓수의 조정 */

t = GetTickCount();

for ( int i = 0; i < TIMES; ++i ) {

us.insert(sample());

}

 

t = GetTickCount() - t;

cout << t << "(unordered_set)\n" ;

}

}

 

< 실행 결과 >

1562(set)

1188(unordered_set)

 

 

25% 정도 unordered_set 쪽이 빠른 것 같습니다. 그다지 큰 속도 차이가 나지 않았습니다만 이것은 컨테이너 내에 요소가 추가되는것에 따라서 버켓 수의 확장과 요소의 재 배분이 자주 행해지는데 필요로 하는 시간을 포함하고 있습니다. 코드 중간의 //us.rehash(N); 의 코멘트를 없애고 처음부터 충분한 수의 버켓을 확보했을 경우 실행 결과는:

 

1563(set)

875(unordered_set)

되어 set 의 약2배의 속도를 얻을 수 있었습니다.

 

 

출처 : http://codezine.jp/a/article/aid/2171.aspx

 

 

저작자 표시
신고
by 흥배 2010.03.17 08:30

표준 C++ 라이브러리가 제공하는 다양한 함수에는 1(혹은 2)의 인수를 주는 함수 오브젝트를 인도하는 것이 다수 있습니다.

 

정수는 몇 개?

#include <iostream>
#include <algorithm>

using namespace std;

 

// n정수라면 true를 돌려준다

bool is_positive( int n)

{

return n > 0;

}

 

int main()

{

const int N = 8;

int data[N] = { -3, -2, -1, 0, 1, 2, 3, 4 };

   /* count_if(first, last, pred):

* first이상 last미만의 범위에 있 x에 대해

* pred(*x) true (!=0) 되는 것의 개수를 돌려준다 */

cout << count_if(data, data+N, &is_positive) << " positives\n" ;

}

 

< 실행 결과 >

4 positives

 

 

표준 C++ 라이브러리의 함수 오브젝트 less를 사용 하여 상기의 is_positive로 옮겨지지 않는지 생각해 봅시다.

함수 오브젝트 less의 멤버 함수 operator()는 인수를 2개 취하여 1 인수가 2 인수 보다 작으면 true를 돌려줍니다.

 

 

함수 오브젝트 less

std::less< int > int_less;

bool result = int_less(1,2); // true

result = int_less(2,1); // false

result = int_less(2,2); // false

 

 

less를 방금 전의 알고리즘 :count_if의 제3인수에 사용하기 위해 binder1stless::operator() 1 인수를 0으로 속박(고정) 합니다.

 

bind1st/bind2nd에 의한 속박

#include <iostream>
#include <algorithm>
#include <functional>

using namespace std;

 

int main()

{

const int N = 8;

int data[N] = { -3, -2, -1, 0, 1, 2, 3, 4 };

// 1인수를 0으로 속박 하는 것으로,

// 인수가 정수라면 true를 돌려주는 함수 오브젝트가 된다.

cout << count_if(data, data+N, bind1st(less< int >(),0)) << " positives\n" ;

// 2인수를 0으로 속박 하면 정수라면 true를 돌려준다.

cout << count_if(data, data+N, bind2nd(less< int >(),0)) << " negatives\n" ;

}

 

< 실행 결과 >

4 positives

3 negatives

 

 

그러면 「-3 이상, 3 미만의 요소 수」를 요구하려면 어떻게 할까요.

mid lo 이상, hi 미만이라면 true를 돌려준다

template <typename T>

bool in_between(T lo, T mid, T hi) {

return lo <= mid && mid < hi;

}

 

이런 함수 in_between 을 준비하여 제1인수를 -3, 3인수를 3으로 속박 하면 좋겠습니다만 표준 C++이 준비해 주고 있는 바인더(속박 함수) 2항 함수 오브젝트에 대한 bind1st bind2nd 뿐입니다.

TR1은 이와 같이 제한의 어려운 바인더를 일반 화해, operator() 에게 주는 임의의 인수를 속박 하는 범용 바인더 : bind 를 제공해 줍니다.

 

 

bind를 사용해 -3 이상, 3 미만의 요소를 센다

#include <iostream>

#include <algorithm>

#include <functional>

#include <boost/tr1/functional.hpp>

using namespace std;

 

// lo <= mid < hi 이라면 true를 돌려준다

template <typename T>

bool in_between(T lo, T mid, T hi) {

return lo <= mid && mid < hi;

}

 

int main()

{

const int N = 8;

int data[N] = { -3, -2, -1, 0, 1, 2, 3, 4 };

// 플레이스홀더: _1, _2, ... 를 유효하게 한다

using namespace tr1::placeholders;

// in_between의 제1,3인수를 각각 -3,3으로 속박 한다

cout << count_if(data, data+N,

tr1::bind(&in_between< int >, -3, _1, 3)) << " numbers are [-3,3)\n" ;

}


실행 결과

6 numbers are [-3,3)

 

 

플레이스홀더의 수/위치/순서는 자유롭게 선택할 수 있기 때문에 이하의 샘플과 같이 3항 함수의 인수 1개를 속박 해  2항 함수로 할 수도 있습니다.

 

요소의 소트

#include <iostream>

#include <algorithm>

#include <functional>

#include <boost/tr1/functional.hpp>

 

using namespace std;

 

// 오름/내림차순의 어느 쪽에도 사용할 수 있는 비교 함수

template <typename T>

bool compare(T x, T y, bool descend) {

return descend ? (x < y) : (y < x);

}

 

int main()

{

const int N = 8;

int data[N] = { 0, -1, 1, -2, 2, -3, 3, 4 };

using namespace tr1::placeholders;

// 내림차순로 소트sort의 제3인수는 2항 함수 오브젝트

sort(data, data+N, tr1::bind(&compare< int >, _1, _2, false ));

for ( int i = 0; i < N; ++i ) cout << data[i] << ' '; cout << endl;

// 승순으로 소트

sort(data, data+N, tr1::bind(&compare< int >, _1, _2, true ));

for ( int i = 0; i < N; ++i ) cout << data[i] << ' '; cout << endl;

// 이것도 역시 승순으로 소트(플레이스홀더의 순서에 주목)

sort(data, data+N, tr1::bind(&compare< int >, _2, _1, false ));

for ( int i = 0; i < N; ++i ) cout << data[i] << ' '; cout << endl;

}


실행 결과

4 3 2 1 0 -1 -2 -3-3 -2 -1 0 1 2 3 4-3 -2 -1 0 1 2 3 4

 

 

한층 더 bind 는 클래스의 멤버 함수마저도 바인드 해 줍니다.

 

멤버 함수의 바인드

#include <iostream>

#include <string>

#include <boost/tr1/functional.hpp>

 

using namespace std;

 

class Sandwitch {

string mid_;

public :

Sandwitch( const string& mid) : mid_(mid) {}

string make( const string& head, const string& tail) const {

return head + mid_ + tail;

}

};

 

int main()

{

Sandwich s( " and " );

Sandwich* p = &s;

using namespace tr1::placeholders;

// s.make("boys,"girls")

cout << tr1::bind(&Sandwich::make, s, "boys" , _1)( "girls" ) << endl;

// p->make("ladies","gentlemen")

cout << tr1::bind(&Sandwich::make, p, "ladies" , _1)( "gentlemen" ) << endl;

// p->make("black","white")

cout << tr1::bind(&Sandwich::make, p, _2, _1)( "while" ,"black" ) << endl;

// s.make("hit","away")

cout << tr1::bind(&Sandwich::make, _1, "hit" , "away" )(s) << endl;

// p->make("adam","eve");

cout << tr1::bind(&Sandwich::make, _1, "adam" , "eve" )(p) << endl;

// s.make("love","peace")

cout << tr1::bind(&Sandwich::make, _1, _2, _3)(s, "love" ,"peace" ) << endl;

}


실행 결과

boys and girls

ladies and gentlemen

black and while

hit and away

adam and eve

love and peace

 

 

출처 : http://codezine.jp/a/article/aid/2158.aspx

저작자 표시
신고
by 흥배 2010.03.15 08:30

요소의 접근

 

tuple(0을 기점으로서) n번째의 요소는 함수 get을 개입시켜 접근 합니다. 다만 n은 정수가 아니면 안됩니다. get은 참조를 돌려주므로 좌변 값으로 이용하는 것으로 요소에 대입이 가능합니다.

    

get에 의한 참조와 대입

#include <iostream>

#include <string>

#include <boost/tr1/tuple.hpp> // tuple

 

using namespace std;

 

int main()

{

tr1::tuple exam;

tr1::get<0>(exam) = "Steve" ;

tr1::get<1>(exam) = 567;

tr1::get<2>(exam) = tr1::get<1>(exam) / 5.0;

cout << tr1::get<0>(exam) << "너의"

" 득점=" << tr1::get<1>(exam) <<

" 평균=" << tr1::get<2>(exa m) << endl;

}

 

 

  pair와의 인터페이스의 통일 때문에  pair에 대해서도 함수  get 적용할 수 있습니다.
    

pair에 대해서 get 한다

#include <iostream>

#include <string>

#include <utility>  // pair

#include <boost/tr1/tuple.hpp>// tuple

 

using namespace std;

 

int main()

{

pair police = make_pair( "???" , 110);

tr1::get<0>(police) = "순경" ;

 

cout << tr1::get<0>(police) << ':' << tr1::get<1>(police) << endl;

}

 

 

 

일괄 대입 / 일괄 참조

 

pair에 있어서 make_pair와 같이 tuple에는 함수 make_tuple 준비되어 있습니다. 또 함수  tie 에 의해서 복수의 변수를 일괄해 읽어낼 수 있습니다.

    

make_pair/tie

#include <iostream>

#include <string>

#include <boost/tr1/tuple.hpp>   // tuple

 

using namespace std;

 

int main()

{

tr1::tuple exam;

exam = tr1::make_tuple( "Steve" , 567, 567/5.0);

string name;

double mean;

// tie:사용하지 않는 요소에는 ignore(무시)를 지정 할 것

tr1::tie(name, tr1::ignore, mean) = exam;

cout << name << "너의 평균점은" << mean << endl;

}

 

 

 

비교

 

tuple의 비교 연산 == , != , <, <= , >, >= 은 각 요소를 왼쪽에서 순서 대로 비교합니다. 비교 도중에 진위가 확정하면 그 이후의 비교는 행해지지 않습니다.

     

tuple의 비교는 shortcut 된다

#include <iostream>

#include <boost/tr1/tuple.hpp>  // tuple

 

using namespace std;

 

struct Value

{

int n_;

Value( int n) : n_(n) {}

};

 

bool operator ==( const Value& x, const Value& y)

{

bool result = ( x.n_ == y.n_ );

cout << x.n_ << (result ? "==" :"!=" ) << y.n_ << endl;

return result;

}

 

bool operator <( const Value& x, const Value& y)

{

bool result = ( x.n_ < y.n_ );

cout << x.n_ << (result ? "<" :">=" ) << y.n_ << endl;

return result;

}

 

int main()

{

typedef tr1::tuple triple;

triple x(12,34,56);

triple y(12,43,56);

// 2 요소까지의 비교로 진위가 확정 되기 때문에

// 3 요소의 비교는 행해지지 않는다

cout << "x == y :" << boolalpha << (x == y) << endl;

cout << "x < y :" << boolalpha << (x < y) << endl;

}

 

< 실행 결과 >

12==12

34!=43

x == y : false

12>=12

12>=12

34<43

x < y : true

 

 

 

tuple_size,tuple_element

 

tuple_size::value Tuple의 요소 수, tuple_element::type Tuple N번째의 요소의 형태가 됩니다.

 

tuple_size, tuple_element

#include <iostream>

#include <string>

#include <boost/tr1/tuple.hpp>   // tuple

 

using namespace std;

 

// Tuple의 요소

template <<span style="font-family:굴림체; font-size:9pt; color:#0000ff;"> typename Tuple>

int members( const Tuple&)

{

return tr1::tuple_size::value;

}

 

// Tuple N번째를 '+' 한다

template <<span style="font-family:굴림체; font-size:9pt; color:#0000ff;"> int N, typename Tuple>

typename tr1::tuple_element::type

plus( const Tuple& x, const Tuple& y)

{

return tr1::get(x) + tr1::get(y);

}

 

int main()

{

tr1::tuple t1( "Hello" ,12);

tr1::tuple t2( "World" ,34);

cout << members(t1) << " members." << endl;

cout << plus<0>(t1,t2) << endl;

cout << plus<1>(t1,t2) << endl;

}

 

< 실행 결과 >

2 members.

HelloWorld

46

 

출처 : http://codezine.jp/a/article/aid/2134.aspx


저작자 표시
신고
by 흥배 2010.03.09 08:30

표준 C++ 라이브러리에는 두 개의 요소를 가지는 구조체: pair가 정의되어 있습니다.

  

pair

#include <iostream>

#include <string>

#include <utility> // pair

 

using namespace std;

 

int main()

{

   const int N = 3;

   pair phone[N];

 

  phone[0] = pair( "경찰" , 110); // 대입 1

  phone[1].first = "시보" ; // 대입 2

  phone[1].second = 117;

  phone[2] = make_pair( "소방" , 119); // 대입3

 

  phone[0].swap(phone[2]); // 교환

 

  for ( int i = 0; i < N; ++i ) {

    cout << phone[i].first << ':' << phone[i].second << endl;

  }

}


<
실행 결과>

소방:119

시보:117

경찰:110

 


pair로 묶을 수 있는 요소 수는 2개로 한정되기 때문에 그 이상의 요소 수를 정리하는 것은 많이 귀찮습니다.

   

pair에 억지로 3개의 요소 사용

#include <iostream>

#include <string>

#include <utility> // pair

 

using names pace std;

 

// pair string pair

struct musician : pair,string> {

typedef pair,string> base;

musician(string f, string m, string l) : base(make_pair(f,m),l) {}

};

 

ostream& operator <<(ostream& st ream, const musician& m) {

return stream << m.first.first << ' '

<< m.first.second << ' '

<< m.second;

}

 

int main()

{

musician wam( "Wolfgang" ,"Amadeus" ,"Mozart" );

musician jsb( "Johann" ,"Sebastian" ,"Bach" );

cout << wam << endl << jsb << endl;

}

 

< 실행 결과 >

Wolfgang Amadeus Mozart

Johann Sebastian Bach

 

 

TR1에서 제공 되는 tuple은 두 개 묶음인 pair를 확장 하여 임의의 N개의 요소를 묶음으로 할 수 있습니다(N은 구현 의존 boost1.34.1에서는 최대 9개였습니다).

    

tr1::tuple판 '음악가'

#include <iostream>

#include <string>

#include <boost/tr1/tuple.hpp> // tuple

 

using name space std;

 

struct musician : tr1::tuple<string,string,string> {

typedef tr1::tuple<string,string,string> base;

musician(string f, string m, string l) : base(f,m,l) {}

};

 

ostream& operator <<(ostream& stream, const musician& m) {

return stream << tr1::get<0>(m) << ' '

<< tr1::get<1>(m) << ' '

<< tr1::get<2>(m);

}

 

int main()

{

musician wam( "Wolfgang" ,"Amadeus" ,"Mozart" );

musician jsb( "Johann" ,"Sebastian" ,"Bach" );

cout << wam << endl << jsb << endl;

}


le(2/2


출처 : http://codezine.jp/a/article/aid/2134.aspx



저작자 표시
신고
by 흥배 2010.03.08 08:30

function

그런데 범용 바인더 bind 에 의해서 생성된 함수 오브젝트를 변수로 저장하여 얼마든지 알고리즘으로 사용해서 돌리는 것을 생각해 봅시다. 그러기 위해서는 bind가 생성한 함수 오브젝트의 ''을 가지는 변수를 선언하지 않으면 안됩니다.

   

 

bind의 생성하는 함수 오브젝트의 ''

cout << typeid (tr1::bind(&Sandwich::make, _1, _2, _3)).name();

 

실행 결과

class boost::_bi::bind_t< class std::basic_string< char ,

struct std::char_traits< char >,class std::allocator< char > >,

class boost::_mfi::cmf2< class std::basic_string< char ,

struct std::char_traits< char >,class std::allocator< char > >,

class Sandwich,class std::basic_string< char ,

struct std::char_traits< char >,class std::allocator< char > > const &,

class std::basic_string< char ,struct std::char_traits< char >,

class std::allocator< char > > const &>,

class boost::_bi::list3< class boost::arg<1>,class boost::arg<2>,class boost::arg<3> > >

 

……터무니없고 복잡한 형태가 만들어져 있습니다. 이것으로는 변수를 선언할 수 없습니다. 클래스 템플릿 function 은 함수 오브젝트의 범용적인''으로서 기능합니다.

 

 

함수 오브젝트를 통일적으로 취급한다

#include <iostream>

#include <algorithm>

#include <functional>

#include <boost/tr1/functional.hpp>

 

using namespace std;

 

// x < y 이라면 true를 돌려준다

bool less_int( int x, int y) {

return x < y;

}

 

// 승순/내림차순 어느 쪽에도 사용할 수 있는 비교 함수

template <typename T>

bool compare(T x, T y, bool descend) {

return descend ? (x < y) : (y < x);

}

 

int main()

{

const int N = 8;

int data[N] = { 0, -1, 1, -2, 2, -3, 3, 4 };

// template 인수가 조금 특수.

// 반환값 (변수,변수...) 라고 하는 형식.

tr1::function< bool ( int ,int)> comp;

// 승순으로 소트

using namespace tr1::placeholders;

comp = tr1::bind(&compare< int >, _1, _2, true );

sort(data, data+N, comp);

for ( int i = 0; i < N; ++i ) cout << data[i] << ' '; cout << endl;

// 같은 승순으로 소트

comp = &less_int;

sort(data, data+N, comp);

for ( int i = 0; i < N; ++i ) cout << data[i] << ' '; cout << endl;

// 이것도 역시 내림차순으로 소트

comp = less< int >();

sort(data, data+N, comp);

for ( int i = 0; i < N; ++i ) cout << data[i] << ' '; cout << endl;

}

 

 

 

출처 : http://codezine.jp/a/article/aid/2158.aspx

 

저작자 표시
신고
by 흥배 2010.03.07 08:30

괴로운 메모리 관리 - shared_ptr / weak_ptr

 

C/C++ 에서 메모리 관리는 프로그래머에게 맡겨져 있습니다. 귀찮은 것으로 프로그래머의 약간의 실수가 큰 사고로 연결 되는 경우가 허다합니다.

  

 

포인터는 귀찮다

 

string* p = new string( "one" );

string* q = new string( "two" );

p = q; // p,q 모두 "two" 를 가리킨다. "one"은 미아

delete p;

delete q; // "two"를 다중 delete!

 

 

 

std::auto_ptr의 한계

 

표준 C++라이브러리는 메모리 관리를 편하게 하는 std::auto_ptr 를 제공하고 있습니다.

    

auto_ptr 이라면

#include

#include ring>

#include <memory> // std::auto_ptr<T>

 

using namespace std;

 

class item {

private :

string value_;

public :

 item( const char * v= "???" ) : value_(v)

 {

   cout << "item(" << value_ << ") ctor\n" ;

  }

  ~item() { cout << "item(" << value_ << ") dtor\n" ; }

  string value() const { return value_; }

};

 

int main()

{

   auto_ptr<item> p( new item( "one" ));

   auto_ptr<item> q( new item( "two" ));

   p = q; // p는 가리키고 있었 "one" delete, "two"를 가리킨다. q null 된다.

   cout << "p points to " << (p.get() ? p->value() : "(null)" ) << endl;

   cout << "q points to " << (q.get() ? q->value() : "(null)" ) << endl;

}

 

< 실행 결과 >

item(one) ctor

item(two) ctor

item(one) dtor

p p oints to two

q points to (null)

item(two) dtor

 


실행 결과가 나타내 보이는 대로 constructor 와 소멸자의 수가 일치하고 있을 테니 delete 잊거나 다중 delete가 발생하지 않는 것을 압니다. auto_ptr은 소멸 시에 그것이 가리키는 포인터를 delete 하므로 명시적으로 delete 할 필요가 없습니다.

다만  auto_ptr 사이의 복사(대입)를 하면 포인터의 소유권(=삭제 책임)이 이동 하여 복사 처(source)에서는 포인터가 없어집니다(실행 결과의 q "two"를 가리키고 있지 않아요). 그 때문에 복수의 auto_ptr가 하나의 인스턴스를 가리켜 공유할 수 없습니다.

    


auto_ptr 에서는 인스턴스를 공유할 수 없다

class person {

string name_;

public :

person(string n) : namae_(n) {}

auto_ptr child; // 자식

};

 

person sazae( "소라" );

person masuo( "마스오" );

auto_ptr tara( new person( "타라" ));

// "타라" "소라" "마스오"의 자식로 하고 싶지만

sazae.child = tara; // 이 순간 "타라"의 소유권이 tara로부터

// sazae.child로 이동(양도된다)

masuo.child = tara; // masuo.child "타라"를 가리킬 수 없다

 

 

new된 인스턴스를 자동적으로 delete 해 주는 auto_ptr 은 편리 한 것은 틀림 없습니다만 이 제한이 있기 때문에 용도가 한정되어 버립니다.

 

 

std::tr1::shared_ptr - 공유 포인터

 

TR1에서 새롭게 추가된 shared_ptr은 참조 카운트라고 하는 것으로 인스턴스를 관리합니다. shared_ptr은 그 내부에 그 인스턴스를 참조하고 있는 shared_ptr의 총 수를 보관 유지하고 있습니다.  shared_ptr 의 소멸자는 내부의 참조수를 -1 하여 그것이 0이 되었을 때 인스턴스가 어디에서도 참조되지 않게 되었다 라고 판단 하고 인스턴스를 delete 합니다.

     

shared_ptr

#include <iostream>

#include <string>

#include <boost/tr1/memory.hpp> // std::tr1::shared_ptr

 

using namespace std;

 

class item {

private :

string value_;

public :

item( const char * v= "???" ) : value_(v) {

cout << "item(" << value_ << ") ctor\n" ;

 }

~item() { cout << "item(" << value_ << ") dtor\n" ; }

string value() const { return value_; }

};

 

int main()

{

   // p1 "something"을 가리킨다. 참조수:1

   tr1::shared_ptr<item> p1( new item( "something" ));

   cout << "p1->value() = " << p1->value() << endl;

   {

      // p2 "something"을 가리킨다. 참조수:2

      tr1::shared_ptr<item> p2 = p1;

      cout << "p2->value() = " << p2->value() << endl;

      // 여기서 p2사라진다. 참조 회수:1

   }

   cout << "p1->value() = " << p1->value() << endl;

   // 여기서 p1사라진다. 참조수:0되어 "something" delete된다

}


< 실행 결과 >

item(something) ctor

p1->value() = something

p2->value() = something

p1->value() = something

item(something) dtor


std::tr1:weak_ptr 약 참조 포인터 shared_ptr 을 사용하는 것에 의해서 번잡한 메모리 관리 로부터 해방됩니다만 이것으로도 아직 순환 참조 라고 하는 문제가 남아 있습니다.

 


순환 참조란

#include <iostream>

#include <string>

#include <boost/tr1/memory.hpp> // std::tr1::shared_ptr

 

class Person {

public :

string name; // 이름

tr1::shared_ptr spouse; // 배우자

Person(string n) : name(n) {}

void info() const {

cout << "My name is " << name

<< " and my spouse is " << spouse->name << endl;

}

};

 

int main()

{

   // one "adam"을 가리킨다. 참조수:1

   tr1::shared_ptr<Person> one( new Person( "adam" ));

   {

      // two "eve"을 가리킨다: 참조수:1

      tr1::shared_ptr<Person> two( new Person( "eve" ));

      one->spouse = two; // "adam"의 아내는 "eve" 참조수:2

      two->spouse = one; // "eve"의 남편은 "adam" 참조수:2

      one->info();

      two->info();

      // 여기서 two사라진다. 참조수:1 ... 0은 아니기 때문에 "eve" delete 되지 않는다

   }

   one->info();

   // 여기서 one사라진다. 참조수:1 ... 0은 아니기 때문에 "adam"delete 되지 않는다

}

 

< 실행 결과 >

My name is adam and my spouse is eve

My name is eve and my spouse is adam

My name is adam and my spouse is eve

 

이 예와 비슷하게 복수의 shared_ptr 이 서로를 서로 참조해 루프를 형성하면(순환 하는) 참조수가 0이 되는 것이 없기 때문에 인스턴스가 delete 되지 않고 남아 버립니다.

 

이 문제를 해소하기 위해 TR1은 한층 더 하나 더 weak_ptr을 제공합니다. weak_ptrshared_ptr 가 보관 유지하는 참조수의 증감에 관여하지 않습니다. 또한 weak_ptr의 멤버 expired()에 의해서 인스턴스의 소실을 알 수 있습니다.

    


weak_ptr에 의한 해결

#include <iostream>

#include <string>

#include <boost/tr1/memory.hpp>

// std::tr1::shared_ptr, std::tr1::weak_ptr

 

class Person {

public :

string name;

tr1::weak_ptr<spouse> spouse;

Person(string n) : name(n) {}

void info() const {

cout << "My name is " << name

<< " and my spouse " ;

if ( spouse.expired() ) // 인스턴스의 유무를 판단한다

cout << "has gone...\n" ;

else

cout << spouse.lock()->name << endl;

}

};

 

int main()

{

   // one "adam"을 가리킨다. 참조수:1

   tr1::shared_ptr<Person2> one( new Person2( "adam" ));

   {

      // two "eve"를 가리킨다: 참조수:1

      tr1::shared_ptr<Person2> two( new Person2( "eve" ));

      // weak_ptr은 참조수의 증감에 관여하지 않는다

      one->spouse = two; // "adam"의 아내는 "eve" 참조수:1

      two->spouse = one; // "eve"의 남편은 "adam" 참조수:1

      one->info();

      two->info();

      // 여기서 two사라진다. 참조수:0 되어 "eve" delete 된다

   }

   one->info();

   // 여기서 one사라진다. 참조수:0 되어 "adam" delete 된다

}

 

< 실행 결과 >

My name is adam and my spouse eve

My name is eve and my spouse adam

My name is adam and my spouse has gone...

정리

차기 C++규격 「C++0x」 에서 확장 예정의 라이브러리 「TR1」로부터 arrayshared_ptr /weak_ptr를 소개했습니다. 이것들을 활용하는 것으로 C++에서 귀찮은 메모리 관리가 훨씬 편해지겠지요.

TR1에는 그 외에도 편리한 클래스가 다수 수록되고 있습니다. 속편을 기대하세요.



원본 : http://codezine.jp/a/article/aid/1937.aspx

저작자 표시
신고
by 흥배 2010.02.27 08:30

std::tr1::array - 고정


프로그램 중에서 가장 많이 사용하고 있는 것이 배열입니다. 언제나 사용하고 있는 배열 int data[5] 와 같은 것들을 클래스로 제공하는 것입니다.


 
배열을 사용한 간단한 샘플

#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

 

int main()

{
      const size_t N = 5;
      int arr[N] = {1,2,3,4,5};
      // 배열의 요소를 출력 한다 
   copy(arr, arr+N, ostream_iterator<
int >(cout, " " ));
   cout << endl;
}

 

배열에 대해 표준 C++ <algorithm>을 적용할 때 적용 범위 즉 반복자의 묶음으로서 배열의 선두와 말미를 이 예에서는 arr arr+N 을 줍니다.

 


표준 C++ 라이브러리의 컨테이너 std::vector 라면


vector< int > ivec;
// 배열의 요소를 출력 한다
copy(ivec.begin(), ivec.end(), ostream_iterator<
int >(cout, " " ));


와 같이 반복자를 돌려주는 멤버 begin() /end()사용할 수 있습니다. 고정 배열 array는 표준 C++ 라이브러리의 컨테이너와 같은 멤버를 가지면서 그 실체는 빌트인 배열이라고 하는 품격이 틀린 클래스입니다.


array 라면...

#include  <iostream>
#include <algorithm>
#include <iterator>
#include < boost/tr1/array.hpp > // std::tr1::array
using namespace std;

 


int main() {
   // template인수에는 요소의 형태와 요소 수를 지정한다 
   tr1::
array< int ,5> arr = {{ 1,2,3,4,5}}; // {{ }} 둘러쌀 것 
   copy(arr.begin(), arr.end(), ostream_iterator<
int >(cout, " " ));
}

 

std::tr1::array template인수 T, N에는 각각 요소의 형태와 요소 수를 지정합니다. 각 요소의 초기화가 필요하면 요소 줄을 {{ }} 둘러싸 주세요.

 



std::tr1::array 의 주요한 멤버들을 아래에 나타냅니다.


size()

요소 수 N을 돌려줍니다.

operator[](n) , at(n)
n
번째의 요소. at(n) 은 범위 외( n >= N ) std::range_error 예외를 throw합니다.

front() , back()
각각 선두 요소/말미 요소를 돌려줍니다.

begin() , end()
각각 선두/말미의 반복자를 돌려줍니다.

rbegin() , rend()
각각 선두/말미의 역순 반복자를 돌려줍니다. 역순으로 출력

tr1::array< int ,5> arr = {{1,2,3,4,5}};
copy(arr. rbegin() , arr. rend() , ostream_iterator< int >(cout, " " ));

 
swap(other)
array other
와의 사이에 각 요소를 교환합니다. X y를 통째로 교환

tr1::array< int ,5> x;
tr1::array< int ,5> y;x.swap(y) ;

 
assign(value)
전 요소에 value 를 대입합니다모든 요소를 -1 로 초기화

tr1::array< int ,5> x;x.assign(-1) ;

 

== , !=, <= , >, >=
array 를 비교합니다. 대소 관계는 사전순서(lexicographical)에 근거합니다.

 


원본 : http://codezine.jp/a/article/aid/1937.aspx

저작자 표시
신고
by 흥배 2010.02.25 08:30

오늘 TR1 unordered_map을 사용해 보려고 했는데 갑자기 컴파일 에러가 미친듯이 나더군요. 에러 위치가 제 코드가 아니고 모두 unordered_map쪽 이었습니다.

 

array는 문제 없이 잘 되는데 이것만 에러가 나서 순간 당황했습니다.

 

아직 TR1을 사용하는 사람이 별로 없어서 물어볼 때도 없어서 얼릉 구글링을 했습니다.

바로 나오더군요.

 

http://social.msdn.microsoft.com/Forums/en-US/vcgeneral/thread/eaf24519-84e3-442e-ac7d-adab82a81ede/

 

문제는 TR1을 사용할 수 있는 VS SP1을 설치한 후에 Windows SDK를 설치하면 SDK SP1의 일부 파일을 덮어 쉬워 버려서 발생하는 문제였습니다.

 

다시 SP1을 설치하니 unordered_map 에러가 모두 사라졌습니다.

신고
by 흥배 2009.03.21 13:04

VS 2008에 추가된 TR1의 라이브러리 사용법과 Boost의 TR1 사용법이 같습니다.

예전에 블로그에 올렸던 글인데 한번 더 링크를 겁니다.


Install, array, shared_ptr, weak_ptr

N개 이상의 요소를 정리하는「tuple」

bind, function

unordered containers : unordered_set, unordered_multiset, unordered_map, unordered_multimap

 


신고
by 흥배 2009.03.21 12:53

현재 VS 2008을 사용하고 있습니다. 이것을 사용하게 된 이유 중의 하나가 TR1을 사용하기 위해서인데 생각보다 늦게 이제서야 사용하게 되었습니다.

 

먼저 가장 간단하게 사용할 수 있는 ‘array’를 사용하였습니다.

기존의 배열을 대체하여 사용할 수 있는 것입니다.

 

저는 이 ‘array’를 처음 사용하는 것은 아닙니다. 2004년에 boost 라이브러리에 있는 ‘array’를 사용했었습니다. 그 당시 만들었던 일본 온라인 마작 게임에서 자주 사용하였습니다.

그러나 솔직히 이때는 꼭 사용해야 될 이유는 없이 사용했었습니다. 보통 이렇게 사용하면 뭔가 문제를 일으킬 수 있는데 ‘array’라는 것이 배열의 Wrapper 한 것이라서 문제 될 것은 없었습니다.

 

 

이번에 이것을 사용하게 된 이유는


1. STL 라이브러리와 매끄러운 결합

배열도 사용할 수 있지만 STL의 컨테이너와는 좀 다르게 사용해야 되고 한계도 있죠.

 

 

2. 메모리 영역 침범 방지

서버의 경우는 개발자마다 다르지만 보통 정적 할당을 사용합니다. 그리고 성능 향상을 위해 배열을 자주 사용합니다. 그런데 작업을 하다가(대부분 기획 변경에 의해 기존 코드를 수정할 때) 반복문 등에서 할당된 배열 크기를 넘어서 메모리 쓰기를 하여 서버가 죽지는 않지만 이상한 행동을 하게 될 때가 있습니다. 이럴 때가 제일 골치 아픕니다. 서버가 아예 죽어버리면 덤프 파일을 보고 찾아 낼 수도 있는데 서버는 죽지는 않았는데 이해되지 않은 행동을 하고 있어서 어디가 문제인지 찾기가 어려워집니다.

 

할당된 배열의 크기를 넘어서는 경우의 예를 들면

int RoomCharCds[ MAX_ROOM_CHAR ]로 했는데

반복문에서는

for( int i = 0; i < MAX_IN_ROOM_CHAR; ++i )

{

RoomCharCds[i] = 0;

}

이렇게 사용하는 경우입니다. 위 경우는 상수 변수의 이름이 비슷하여 배열 할당에 사용한 것과 반복문에서 사용하는 것이 다른데 같이 사용해버려 일어나는 문제입니다.

문제가 터져서 의심되는 부분을 유심히 보기 전까지는 찾기가 꽤 힘듭니다.

 

‘array’를 사용하면 반복문 사용 전에

int CharCount = RoomCharCds.max_size();

for( int i = 0; i < CharCount; ++i )

이렇게 사용하니 범위를 넘어서는 일은 없게 됩니다.

 

 

3. TR1을 사용해보자



앞으로 새로 개발할 때 클래스의 멤버 변수에서는 배열 대신 ‘array’를 사용할 생각이고

기존에 만들어 놓은 것들도 그 부분을 만지게 될 때는 ‘array’로 대체할 예정입니다.

 

VS 2008을 사용하지 못하는 분들은 boost 라이브러리로 사용해 보기를 권합니다.

‘array’ 이외에도 유용한 라이브러리가 많이 있습니다.

신고
by 흥배 2009.03.21 12:48
| 1 2 |