About STL : C++ STL 프로그래밍(9)-알고리즘1

한빛미디어

2009-10-22

by HANBIT

40,602

제공 : 한빛 네트워크
저자 : 최흥배
이전기사 :

제가 한빛 네트워크에 C++ STL 글을 연재한지 벌써 1년이 넘었습니다. template부터 시작하여 이전 회까지는 STL의 컨테이너들에 대해 설명했습니다. 이제 알고리즘에 대한 것만 남았습니다. 제가 쓴 글들을 보고 C++ STL을 공부하는데 얼마나 도움이 되는지 알 수 없지만 조금이나마 도움이 되었기를 바랍니다.
앞으로 2회에 걸쳐서 STL의 알고리즘 중 많이 사용하고 있는 것을 중심으로 설명하겠습니다.
STL의 컨테이너는 그 자체만으로도 대단히 유용한 것이지만 알고리즘과 결합되면 유용성은 더욱 더 커집니다.
STL의 알고리즘은 컨테이너처럼 제네릭(총칭적)합니다. 제네릭 하다고 하는 이유는 STL에 있는 다양한 알고리즘을 한 종류의 컨테이너에만 사용할 수 있는 것이 아닌 vector, list, deque, map 등 여러 가지 다양한 컨테이너에 사용할 수 있기 때문입니다(참고로 STL 컨테이너만이 아닌 일반 배열 구조도 알고리즘에 사용할 수 있습니다).

9.1 STL 알고리즘 분류

STL 알고리즘은 크게 네 가지로 분류 할 수 있습니다.

변경 불가 시퀀스 알고리즘
변경 가능 시퀀스 알고리즘
정렬 관련 알고리즘
범용 수치 알고리즘

변경 불가 시퀀스 알고리즘에는 find와 for_each 등이 있으며 대상 컨테이너의 내용을 변경하지 못합니다. 변경 가능 시퀀스 알고리즘으로는 copy, generate 등이 있으며 대상 컨테이너 내용을 변경합니다.
정렬 관련 알고리즘은 정렬이나 머지를 하는 알고리즘으로 sort와 merge 등이 있습니다.
범용 수치 알고리즘은 값을 계산하는 알고리즘으로 accumulate 등이 있습니다.

STL의 모든 알고리즘을 설명하기에는 많은 지면이 필요하므로 위에 소개한 알고리즘 카테고리 별로 자주 사용하는 알고리즘 중심으로 어떤 기능이 있으며 어떻게 사용하는지 설명하겠습니다.

9.2 조건자

알고리즘 중에는 함수를 파라미터로 받아들이는 것이 많습니다. 알고리즘에서 함수를 파라미터로 받아들이지 않거나 기본 함수 인자를 사용하며 알고리즘을 사용하는 컨테이너의 데이터는 기본 자료 형만을 사용할 수 있습니다. 유저 정의형 자료 형(struct, class)을 담는 컨테이너를 알고리즘에서 사용하기 위해서는 관련 함수를 만들어서 파라미터로 넘겨줘야 합니다.
알고리즘에 파라미터로 넘기는 함수는 보통 함수보다는 함수객체를 사용하는 편입니다.

9.3 변경 불가 시퀀스 알고리즘

9.3.1. find

컨테이너에 있는 데이터 중 원하는 것을 찾기 위해서는 find 알고리즘을 사용하면 됩니다.
참고로 알고리즘을 사용하려면 algorithm 헤더 파일을 추가해야 합니다.

#include < algorithm >

find의 원형

template
InputIterator find( InputIterator _First, InputIterator _Last, const Type& _Val );

첫 번째 파라미터에 찾기를 시작할 반복자 위치, 두 번째 파라미터에 마지막 위치(반복자의 end()와 같이 이 위치의 바로 앞까지 검색함), 세 번째 파라미터에는 찾을 값을 넘깁니다.
find가 성공하면 데이터가 있는 위치를 가리키는 반복자를 반환하고, 실패하면 반복자의 end()를 반환합니다.

find 사용 방법

vector< int > ItemCodes;
……..
// ItemCodes 컨테이너의 시작과 끝 사이에서 15를 찾는다.
find( ItemCodes.begin(), ItemCodes.end(), 15 );

find를 사용하여 캐릭터의 아이템을 검색하는 예제 코드 입니다.

< 리스트 1. 캐릭터 아이템 검색 >

#include 
#include 
#include 

using namespace std;


int main()
{
  vector< int > CharItems;
  CharItems.push_back( 12 );
  CharItems.push_back( 100 );
  CharItems.push_back( 77 );

  vector< int >::iterator FindIter;

  // CharItems의 처음과 끝에서 12를 찾는다.
  FindIter = find( CharItems.begin(), CharItems.end(), 12 );
  if( FindIter != CharItems.end() )
  {
    cout << "CharItem 12를 찾았습니다." << endl;
  }
  else
  {
    cout << "CharItem 12는 없습니다" << endl;
  }

  // CharItems 두 번째와 끝에서12를 찾는다
  // ++CharItems.begin()로 반복자를 한칸 이동 시켰습니다.
        FindIter = find( ++CharItems.begin(), CharItems.end(), 12 );
  if( FindIter != CharItems.end() )
  {
    cout << "CharItem 12를 찾았습니다." << endl;
  }
  else
  {
    cout << "CharItem 12는 없습니다" << endl;
  }

  return 0;
}

< 결과 >

<리스트 1>에서는 vector 컨테이너를 대상으로 했지만 vector 이외의 list, deque도 같은 방식으로 사용합니다.
다만 map, set, hash_map의 연관 컨테이너는 해당 컨테이너의 멤버로 find()를 가지고 있으므로 알고리즘에 있는 find가 아닌 해당 멤버 find를 사용합니다.

9.3.2 find_if

find를 사용하면 컨테이너에 있는 데이터 중 찾기 원하는 것을 쉽게 찾을 수 있습니다. 그런데 find만으로는 많이 부족합니다. 이유는 find는 기본형만을 컨테이너에 저장하고 있을 때만 사용할 수 있습니다. 만약 유저 정의형을 저장하는 컨테이너는 find를 사용할 수 없습니다. 이럴 때는 9.2에서 짧게 설명한 조건자를 사용해야 합니다. 즉 조건자에 어떤 방식으로 찾을지 정의하고 알고리즘에서 이 조건자를 사용합니다.
find_if는 기본적으로 find와 같습니다. 다른 점은 조건자를 받아들인다는 것입니다.

find_if 원형

template
InputIterator find_if( InputIterator _First, InputIterator _Last, Predicate _Pred );

find와 비교하면 첫 번째와 두 번째 파라미터는 동일합니다. 세 번째 파라미터가 다릅니다. find는 세 번째 파라미터에 찾기 원하는 값을 넘기지만 find_if는 조건자를 넘깁니다.

find_if 사용법

// 컨테이너에 저장할 유저 정의형 
struct User
{
    …….
    int Money;
    int MobKillCount;
    ……
};

// 조건자
struct FindBestUser()
{
   …………………….
};

vector< User > Users;
……..

find_if( Users.begin(), Users.end(), FindBestUser() );

조건자가 있다는 것 이외에는 find_if는 find와 같으므로 조건자 부분만 잘 보시면 됩니다.

< 리스트 2. 특정 돈을 가지고 있는 유저 찾기 >

#include 
#include 
#include 

using namespace std;

struct User
{
  int Money;
  int Level;
};

struct FindMoneyUser
{
  bool operator() ( User& user ) const { return user.Money == ComparMoney; }
  int ComparMoney;
};

int main()
{
  vector< User > Users;

  User user1; user1.Level = 10; user1.Money = 2000;
  User user2; user2.Level = 5;  user2.Money = -10;
  User user3; user3.Level = 20; user3.Money = 35000;

  Users.push_back( user1 );
  Users.push_back( user2 );
  Users.push_back( user3 );

  vector< User >::iterator FindUser;

  FindMoneyUser tFindMoneyUser; 
  tFindMoneyUser.ComparMoney = 2000;
  FindUser = find_if( Users.begin(), Users.end(), tFindMoneyUser );
  if( FindUser != Users.end() )
  {
    cout << "소지하고 있는 돈은: " << FindUser->Money << "입니다" << endl;
  }
  else
  {
    cout << " 유저가 없습니다. " << endl;
  }

  return 0;
}

< 결과 >

<리스트 2>에서는 조건자 함수를 함수 포인터가 아닌 함수 객체를 사용하였습니다. 함수 객체를 사용한 이유는 함수 객체는 inline화 되므로 함수 포인터와 비교하면 함수 포인터 참조와 함수 호출에 따른 작업이 필요 없으며, 함수 객체를 사용하면 객체에 특정 데이터를 저장할 수 있어서 조건자가 유연해집니다.

<리스트 2>의 FindMoneyUser를 일반 함수로 만들었다면 비교로 사용할 ComparMoney의 값은 함수를 정의할 때 고정됩니다. 그러나 함수 객체로 만들면 객체를 생성할 때 ComparMoney의 값을 설정할 수 있어서 유연해집니다.

<참고>
조건자를 사용하는 알고리즘 : STL의 알고리즘은 조건자를 사용하지 않는 것과 조건자를 사용하는 알고리즘 두 가지 버전을 가지고 있는 알고리즘이 있습니다. 이중 조건자를 사용하는 알고리즘은 보통 조건자를 사용하지 않는 알고리즘의 이름에서 뒤에 "_if"를 붙인 이름으로 되어 있습니다.

9.3.3. for_each

for_each는 순차적으로 컨테이너들에 담긴 데이터를 함수의 파라미터로 넘겨서 함수를 실행시키는 알고리즘입니다.
온라인 게임에서 예를 들면 플레이하고 있는 유저 객체를 vector 컨테이너인 Users에 저장하고 모든 유저들의 현재 플레이 시간을 갱신하는 기능을 구현한다면 플레이 시간을 계산하는 함수 객체 UpdatePlayTime을 만든 후 for_each에 Users의 시작과 끝 반복자와 UpdatePlayTime 함수 객체를 넘깁니다.

for_each 원형

template
Function for_each( InputIterator _First, InputIterator _Last, Function _Func );

첫 번째 파라미터는 함수의 파라미터로 넘길 시작 위치, 두 번째 파라미터는 함수의 인자로 넘길마지막 위치, 세 번째는 컨테이너의 데이터를 파라미터로 받을 함수입니다.

for_each 사용 방법

// 함수 객체
struct UpdatePlayTime
{
……….
};

vector< User > Users;

for_each( Users.begin(), Users.end(), UpdatePlayTime );

아래는 위에서 예를 들었던 것을 완전한 코드로 구현한 예제 코드입니다.

< 리스트 3. for_each를 사용하여 유저들의 플레이 시간 갱신 >

#include 
#include 
#include 

using namespace std;

struct User
{
  int UID;
  int PlayTime;
};

struct UpdatePlayTime
{
  void operator() ( User& user )
  {
    user.PlayTime += PlayTime;
  }

  int PlayTime;
};

int main()
{
  vector< User > Users;

  User user1; user1.UID = 1; user1.PlayTime = 40000;
  User user2; user2.UID = 2; user2.PlayTime = 0;
  User user3; user3.UID = 3; user3.PlayTime = 25000;

  Users.push_back( user1 );
  Users.push_back( user2 );
  Users.push_back( user3 );

  // 현재 플레이 시간
  vector< User >::iterator IterUser;
  for( IterUser = Users.begin(); IterUser != Users.end(); ++IterUser )
  {
    cout << "UID : " << cout << IterUser->UID << "의 총 플레이 시간: " << IterUser->PlayTime << endl;
  }
  cout << endl;

  UpdatePlayTime updatePlayTime;
  updatePlayTime.PlayTime = 200;

  // 두 번째 유저부터 갱신
  for_each( Users.begin() + 1, Users.end(), updatePlayTime );
  
  for( IterUser = Users.begin(); IterUser != Users.end(); ++IterUser )
  {
    cout << "UID : " << cout << IterUser->UID << "의 총 플레이 시간: " << IterUser->PlayTime << endl;
  }

  return 0;
}

< 결과 >

변경 불가 시킨스 알고리즘에는 위에 설명한 find, find_if, for_each 이외에 count, search, equal, adjacent_find, equal 등이 있습니다.

9.4. 변경 가능 시퀀스 알고리즘

9.3의 알고리즘들이 대상이 되는 컨테이너에 저장한 데이터를 변경하지 않는 것들이라면 이번에 설명한 알고리즘들은 제목대로 대상이 되는 컨테이너의 내용을 변경하는 알고리즘들입니다. 컨테이너에 복사, 삭제, 대체 등을 할 때는 이번에 소개할 알고리즘들을 사용합니다.

9.4.1. generate

컨테이너의 특정 구간을 특정 값으로 채우고 싶을 때가 있습니다. 이 값이 동일한 것이라면 컨테이너의 assign() 멤버를 사용하면 되지만 동일한 값이 아니라면 assign()을 사용할 수 있습니다.
이 때 사용하는 알고리즘이 generate입니다. generate 알고리즘에 값을 채울 컨테이너의 시작과 끝, 값을 생성할 함수를 파라미터로 넘깁니다.

generate 원형

template
void generate( ForwardIterator _First, ForwardIterator _Last, Generator _Gen );

첫 번째 파라미터는 값을 채울 컨테이너의 시작 위치의 반복자, 두 번째는 컨테이너의 마지막 위치의 반복자, 세 번째는 값을 생성할 함수 입니다.

generate 사용 방법

// 값 생성 함수
struct SetUserInfo
{
  …….
};

vector< User > Users(5);

generate( Users.begin(), Users.end(), SetUserInfo() );

generate 알고리즘의 대상이 되는 컨테이너는 값을 채울 공간이 미리 만들어져 있어야 합니다. 즉 generate는 컨테이너에 데이터를 추가하는 것이 아니고 기존의 데이터를 다른 값으로 변경하는 것입니다.

< 리스트 4. generate를 사용하여 유저의 기초 데이터 설정>

struct User
{
  int UID;
  int RaceType;
  int Sex;
  int Money;
};

struct SetUserInfo
{
  SetUserInfo() { UserCount = 0; }

  User operator() ()
  {
    User user;

    ++UserCount;
    
    user.UID = UserCount;
    user.Money = 2000;

    if( 0 == (UserCount%2) )
    {
      user.RaceType = 1;
      user.Sex = 1;
      user.Money += 1000;
    }
    else
    {
      user.RaceType = 0;
      user.Sex = 0;
    }

    return user;
  }

  int UserCount;
};

int main()
{
  vector< User > Users(5);

  generate( Users.begin(), Users.end(), SetUserInfo() );
  
  char szUserInfo[256] = {0,};

  vector< User >::iterator IterUser;
  for( IterUser = Users.begin(); IterUser != Users.end(); ++IterUser )
  {
    sprintf( szUserInfo, "UID %d, RaceType : %d, Sex : %d, Money : %d",
    IterUser->UID, IterUser->RaceType, IterUser->Sex, IterUser->Money );

    cout << szUserInfo << endl;
  }
  
  return 0;
}

< 결과 >

9.4.2. copy

copy 알고리즘은 컨테이너에 저장한 것과 같은 자료 형을 저장하는 다른 컨테이너에 복사하고 싶을 때 사용합니다.

컨테이너 A의 데이터를 컨테이너 B에 copy 하는 경우 컨테이너 B에 데이터를 추가하는 것이 아니고 덧쓰는 것이므로 A에서 10개를 복사하는 경우 B에는 10개만큼의 공간이 없다면 버그가 발생합니다. 또 A와 B 컨테이너는 같은 컨테이너 필요는 없습니다만 당연히 컨테이너에 저장하는 자료 형은 같아야 합니다.

copy 원형

template
   OutputIterator copy(
      InputIterator _First, 
      InputIterator _Last, 
      OutputIterator _DestBeg
   );

copy 사용 방법

vector vec1;
……..
vector vec2;

copy( vec1.begin(), vec1.end(), vec2.begin() );

< 리스트 5. copy 알골리즘 사용 예>

#include 
#include 
#include 
#include 

using namespace std;

int main()
{
  vector vec1(10);
  generate( vec1.begin(), vec1.end(), rand );

  cout << "vec1의 모든 데이터를 vec2에 copy" << endl;

  vector vec2(10);
  copy( vec1.begin(), vec1.end(), vec2.begin() );
  for( vector::iterator IterPos = vec2.begin();
    IterPos != vec2.end();
    ++IterPos )
  {
    cout << *IterPos << endl;
  }
  cout << endl;


  cout << "vec1의 모든 데이터를 list1에 copy" << endl;
  list list1(10);
  copy( vec1.begin(), vec1.end(), list1.begin() );
  
  for( list::iterator IterPos2 = list1.begin();
    IterPos2 != list1.end();
    ++IterPos2 )
  {
    cout << *IterPos2 << endl;
  }

  return 0;
}

< 결과 >

9.4.4. remove

remove 알고리즘은 컨테이너에 있는 특정 값들을 삭제하고 싶은 때 사용합니다.
주의해야 될 점은 삭제 후 크기가 변하지 않는다는 것입니다. 삭제가 성공하면 삭제 대상이 아닌 데이터들을 앞으로 몰아 넣고 마지막 위치의(컨테이너의 end()가 아닌 삭제 후 빈 공간에 다른 데이터를 쓰기 시작한 위치) 반복자를 반환합니다. 리턴 값이 가리키는 부분부터 끝(end()) 사이의 데이터 순서는 정의되어 있지 않으면 진짜 삭제를 하기 위해서는 erase()를 사용해야 합니다.

remove 원형

template
ForwardIterator remove( ForwardIterator _First, ForwardIterator _Last, const Type& _Val );

첫 번째 파라미터는 삭제 대상을 찾기 시작할 위치의 반복자, 두 번째 파라미터는 삭제 대상을 찾을 마지막 위치의 반복자, 세 번째 파라미터는 삭제를 할 값입니다.

remove 사용 방법

vector vec1;
…..
remove( vec1.begin(), vec1.end(), 20 );

< 리스트 6. remove 사용 예>

#include 
#include 
#include 
#include 

using namespace std;

int main()
{
  vector vec1;
  vec1.push_back(10);  vec1.push_back(20);  vec1.push_back(20);
  vec1.push_back(40); vec1.push_back(50);  vec1.push_back(30);  

  vector::iterator iterPos;

  cout << "vec1에 있는 모든 데이터 출력" << endl;
  for( iterPos = vec1.begin(); iterPos != vec1.end(); ++iterPos )
  {
    cout << *iterPos << "  " << endl;
  }
  cout << endl;

  cout << "vec1에서 20 remove" << endl;
  vector::iterator RemovePos = remove( vec1.begin(), vec1.end(), 20 );

  for( iterPos = vec1.begin(); iterPos != vec1.end(); ++iterPos )
  {
    cout << *iterPos << "  " << endl;
  }
  cout << endl;

  cout << "vec1에서 20 remove 이후 사용 하지않는 영역 완전 제거" << endl;
  while( RemovePos != vec1.end() )
  {
    RemovePos = vec1.erase( RemovePos );
  }

  for( iterPos = vec1.begin(); iterPos != vec1.end(); ++iterPos )
  {
    cout << *iterPos << "  " << endl;
  }
}

< 결과 >

<리스트 6>에서는 remove 후 erase()로 완전하게 제거하는 예를 나타내고 있습니다.

vector::iterator RemovePos = remove( vec1.begin(), vec1.end(), 20 );

로 삭제 후 남은 영역의 반복자 위치를 받은 후

while( RemovePos != vec1.end() )
{
  RemovePos = vec1.erase( RemovePos );
}

로 완전하게 제거하고 있습니다.

9.4.5. replace

컨테이너의 특정 값을 다른 값으로 바꾸고 싶을 때는 replace 알고리즘을 사용합니다.

replace 원형

template
   void replace(
      ForwardIterator _First, 
      ForwardIterator _Last,
      const Type& _OldVal, 
      const Type& _NewVal
   );

replace 사용 방법

vector vec1;
……
replace( vec1.begin(), vec1.end(), 20, 30 );

< 리스트 7. replace 사용 예>

#include 
#include 
#include 
#include 

using namespace std;

int main()
{
  vector vec1;
  vec1.push_back(10);  vec1.push_back(20);  vec1.push_back(20);
  vec1.push_back(40); vec1.push_back(50);  vec1.push_back(30);

  vector::iterator iterPos;

  cout << "vec1에 있는 모든 데이터 출력" << endl;
  for( iterPos = vec1.begin(); iterPos != vec1.end(); ++iterPos )
  {
    cout << *iterPos << "  " << endl;
  }
  cout << endl;

  cout << "vec1의 세 번째 요소부터 20을 200으로 변경" << endl;
  replace( vec1.begin() + 2, vec1.end(), 20, 200 );

  for( iterPos = vec1.begin(); iterPos != vec1.end(); ++iterPos )
  {
    cout << *iterPos << "  " << endl;
  }

  return 0;
}

< 결과 >

변경 가능 시퀀스 알고리즘에는 generate, copy, remove, replace 이외에도 fill, swap, reverse, transform 등이 있으니 제가 설명하지 않은 알고리즘들은 다음에 여유가 있을 때 공부하시기를 바랍니다.

지금까지 설명한 알고리즘을 보면 어떤 규칙이 있다는 것을 알 수 있을 것입니다. 알고리즘에 넘기는 파라미터는 알고리즘을 적용할 컨테이너의 위치를 가리키는 반복자와 특정 값 or 조건자를 파라미터로 넘기고 있습니다. 그래서 각 알고리즘은 이름과 기능이 다를 뿐 사용 방법은 대체로 비슷합니다. 즉 사용 방법에 일괄성이 있습니다. 그래서 하나의 알고리즘만 사용할 줄 알게 되면 나머지 알고리즘은 쉽게 사용하는 방법을 배웁니다. 이런 것이 바로 STL의 장점이겠죠

이번 회는 이것으로 설명을 마치고 남은 알고리즘은 다음 회에 이어서 계속 설명하겠습니다.

TAG :

이전 글 : Flex 애플리케이션의 성능을 보장하는 10가지 팁

다음 글 : About STL : C++ STL 프로그래밍(10)-알고리즘2

최신 콘텐츠

한빛출판네트워크

인기 검색어 (최근 1개월간)

책

강의/세미나

채널.H

IT/모바일

About STL : C++ STL 프로그래밍(9)-알고리즘1

최근 본 상품0