CLOSE

Search For:




BY TAGS

linux HTTP golang flutter java fintech 개발환경 kubernetes network Docker devops database tutorial cli 분산시스템 www 블록체인 AWS system admin bigdata 보안 금융 msa mysql redis Linux command dns javascript CICD VPC FILESYSTEM S3 NGINX TCP/IP ZOOKEEPER NOSQL IAC CLOUD TERRAFORM logging IT용어 Kafka docker-compose Dart

17. STL References

 Recommanded Free YOUTUBE Lecture: <% selectedImage[1] %>
STL References
C++ Programming HOW-TO
이전다음

17. STL References

STL에 관한 다음 사이트들을 방문해보라 :

STL tutorials:

Main STL sites:

17.1. STL 개요

STL은 프로그래머에게 몇가지 유용한 데이터구조와 알고리즘을 제공한다. 이는 다음과 같은 것들이 있다.

  • 컨테이너. 두 가지 타입이 있다 :

    • 순차적(Sequential). 여기에는 vector, list, deque 등이 있다.

    • 정렬된 조합(Associative). 여기에는 set, map, multiset, multimap 이 있다.

  • Iterator. 컨테이너의 내용을 살펴볼 수 있게 해주는 포인터 같은 것들이다.

  • 일반적인(generic) 알고리즘들. STL은 컨테이너 타입에 대해 동작하는 여러가지 효과적으로 구현된 표준 알고리즘들 (예를들어 find, sort, merge 등)이 있다. (몇몇 container들은 이 중 일부를 특별한 목적으로 멤버함수로 갖고 있다)

  • Function obejct. function object는 operator()의 정의를 제공하는 class의 instance이다. 이는 이 object들을 함수 같이 사용할 수 있다는 것이다.

  • Adaptors. STL은 다음과 같은 것들을 제공한다.

    • Container adaptor는 vector를 stack을 만들기 위한 기초로 사용할 수 있게 해준다.

    • function adaptor 는 이미 존재하는 function object로부터 새로운 function object를 만들 수 있게 해준다.

  • Allocators. 모든 STL 컨테이너 class는 프로그램이 사용하는 메모리 정보를 갖고 있기 위한 allocator class를 사용한다. 하지만 나는 이 부분은 생략할 것이다.

앞으로 vector, list, set 그리고 map 컨테이너의 사용법을 살펴볼 것이다. 이들을 사용하기 위해서는 내가 STL iterator에 대해 말할 수 있도록 iterator를 쓸 줄 알아야 할 것이다. 또 set과 map 컨테이너를 사용한다는 것은 내가 function object에 대해 뭔가 설명할 수 있도록 간단한 function object가 있어야 한다는 것이다. STL이 지원하는 알고리즘에 대해서는 간단히 설명할 것이고, adoptor는 언급하지 않을 것이다.

몇몇 함수 인자의 타입에 대해서 이름이 바뀔 수 있다. 예를들어 대부분의 int 타입 인자들은 실제로는 size_type이라는 type을 갖고 이것이 적절한 기본 타입으로 tyepdef되는 형태에 의해 쓰인다. 만약 여러 함수들의 실제 인자 타입을 알고싶다면 작업하는 것에 대한 문서나 헤더파일을 참고해라.

STL에서 제공되는 몇가지 유틸리티 class들이 있는데, 이 중 제일 중요한 것은 pair class이다. 이는 다음과 같이 정의되어있다.

template<class T1, class T2>
class pair {
public:
    T1 first;
    T2 second;
    pair(const T1& a, const T2& b) : first(a), second(b) {}

};

그리고 쉽게 pair를 만들도록 다음과 같은 make_pair 함수가 제공된다 :

pair<T1,T2> make_pair(const T1& f, const T2&,s)

또한 ==와 < 연산자도 있다. 이 template class에는 복잡한 것이 없고 그냥 사용하면 된다. 이를 이용하기 위해서는 #include 로 <utility>를 include하면 된다. pair는 여러곳에서 쓰일 수 있는데, 특히 set과 map class에서 많이 나타난다.

17.2. 헤더 파일

STL을 사용하기 위해서는 적절하게 헤더파일을 #include 해주어야 한다. 만약 컴파일러가 표준에 맞지 않는다면 약간 다를 수도 있지만, 표준에 맞는 컴파일러 (g++ 같은)는 다음과 같이 하면 된다 :

  • <vector> : 벡터 타입

  • <list> : 리스트 타입

  • <set> : 집합(set) 타입

  • <map> : 맵 타입

  • <algorithm> : 일반적인 알고리즘 들

표준 C++ 라이브러리는 .h 를 뒤에 붙이지 않는 다는 것에 주의해라. 만약 옛버전의 혹은 좋지 않은 컴파일러를 사용하는데, 위와 같이 해서 include가 되지 않는다면 .h를 붙여서 시도해보아라. 하지만 그보다는 새로운 컴파일러를 구하는 게 더 나을 것이다.

17.3. 컨테이너 class 인터페이스

컨테이너 class들은 서로 같은 이름을 갖는 멤버함수를 많이 갖는다. 이 함수들은 모든 class에 대해 똑같은 (혹은 매우 비슷한) 인터페이스를 제공한다 (그러나 물론 그 내부 구현은 다를 것이다). 아래의 표는 우리가 살펴볼 함수들을 나열한 것이다. 별표는 그 컨테이너 타입이 그 이름의 멤버 함수를 제공한다는 것이다.

표 2. 컨테이너 Class 인터페이스

연산자/함수명목적 vector list set map
== 비교 * ***
< 비교 * * * *
begin iterator * * * * 
end iterator * * * *
size 원소의 수 * * * *
empty 비었는지 * * * *
front 첫번째 원소 * *
back 마지막 원소 * *
[ ] 원소 접근 및 변경 * * 
insert 원소(들) 추가 * * * *
push_back 맨 뒤에 원소 추가 * *
push_front 맨 앞에 원소 추가 *
erase 원소(들) 삭제 * * * *
pop_back 맨 뒤 원소 삭제 * *
pop_front 맨 앞 원소 삭제 *
   

만약 아래의 내용중 의문가는 부분이 있으면 (아마도 잇을 것이다), 조그만 테스트 프로그램을 하나 짜서 어떻게 돌아가는 지 알아볼 수 있을 것이다.

17.4. 벡터 : Vectors

벡터는 C++의 배열과 비슷한, 하지만 이를 발전시킨 컨테이너이다. 특히, 벡터는 선언시에 얼마나 벡터가 커야할지를 알 필요가 없고, push_back 함수를 이용하여 언제나 새로운 원소를 추가할 수 있다. ( 사실 insert 함수가 어디에든 새 원소들을 넣을 수 있게 해주지만, 이는 매우 비효율적이다. 만약 이를 자주 해야한다면 list를 대신 사용하는 것을 고려해보아라. )

17.4.1. 벡터 만들기

벡터는 class template이므로, 선언시에 벡터가 갖게 될 객체의 타입을 선언해주어야 한다. 예를들어 다음과 같다.

vector<int> v1;
vector<string> v2;
vector<FiniteAutomaton> v3;

위 내용은 v1을 int 값을 갖는 벡터로, v2를 string을 갖는 벡터로, v3를 FiniteAutomaton (아마도 미리 이런 타입이 선언되었을 것이다) 를 갖고 있는 벡터로 선언한다. 이 선언들은 벡터의 크기에 대해 전혀 알려주지 않고 ( 구현에 따라 기본 벡터 사이즈가 있을 것이다. ) , 필요에 따라 얼마든지 늘려서 쓸 수 있다.

그러나 다음과 같이 선언함으로써 초기 크기를 정해줄 수도 있다.

vector<char> v4(26);

이는 v4가 문자(char)의 벡터가 되고, 처음에는 26개의 글자를 가질 수 있다는 것이다. 또한, 벡터 안에 들어가는 수들을 초기화 하는 방법도 있는데, 이는 다음과 같다.

vector<float> v5(100,1.0);

위 선언은 v5 가 100개의 1.0으로 초기화 된 실수값을 갖는 벡터임을 선언한다.

17.4.2. 벡터를 체크하기

한번 벡터를 만든 후에는, size 함수를 써서 현재 벡터의 크기를 알아낼 수 있다. 이 함수는 아무 인자 없이 벡터에 들어있는 원소 수를 나타내는 integer를 리턴한다. ( 엄밀하게 말하자면 size_type 타입이 리턴되지만, 이것이 바로 integer로 바뀌어진다 ) 그렇다면 다음의 작은 프로그램으로 무엇이 출력될까?

<vector-size.cpp>=
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v1;
    vector<int> v2(10);
    vector<int> v3(10,7);

    cout << "v1.size() returns " << v1.size() << endl;
    cout << "v2.size() returns " << v2.size() << endl;
    cout << "v3.size() returns " << v3.size() << endl;
}

벡터가 비었는지를 체크하기 위해서는, empty 함수를 쓰면 된다. 이것도 역시 아무 인자 없이 boolean 값을 리턴하는데, 비어있으면 true를, 비어있지 않으면 false를 리턴한다. 그렇다면 다음의 프로그램은 무엇을 프린트할까 (true는 1로, false는 0으로 프린트된다)?

<vector-empty.cpp>=
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v1;
    vector<int> v2(10);
    vector<int> v3(10,7);

    cout << "v1.empty() has value " << v1.empty() << endl;
    cout << "v2.empty() has value " << v2.empty() << endl;
    cout << "v3.empty() has value " << v3.empty() << endl;
}

17.4.3. 벡터의 원소에 접근하기

벡터의 원소는 []연산자를 사용해서 접근할 수 있다. 따라서 모든 원소를 프린트하려면 다음과 같이 하면 된다.

vector<int> v;
// ...
for (int i=0; i<v.size(); i++)
     cout << v[i];

(이는 원래의 배열을 사용하는 것과 매우 비슷하다).

또한, [] 연산자는 벡터 원소의 값을 바꾸기 위해서도 쓰일 수 있다.

vector<int> v;
// ...
for (int i=0; i<v.size(); i++)
      v[i] = 2*i;

front 함수는 벡터의 첫번째 원소를 리턴한다.

vector<char> v(10,'a');
// ...
char ch = v.front();

또한, front를 이용해서 첫번째 원소의 값을 바꿀 수도 있다.

vector<char> v(10,'a');
// ...
v.front() = 'b';

back 함수는 front와 같은 역할을 하지만, 벡터의 맨 마지막 원소를 리턴하는 것이 다르다.

vector<char> v(10,'z');
// ...
char last = v.back();
v.back() = 'a';

[]를 사용하는 간단한 예제를 보자.

<vector-access.cpp>=
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> v1(5);
    int x;
    cout << "Enter 5 integers (seperated by spaces):" << endl;
    for (int i=0; i<5; i++)
          cin >> v1[i];
    cout << "You entered:" << endl;
    for (int i=0; i<5; i++)
          cout << v1[i] << ' ';
    cout << endl;
}

17.4.4. 벡터의 원소를 추가 / 삭제하기

위에 언급된 [] 외에도, 벡터의 원소에 접근하거나 바꿀 수 있는 방법이 몇가지 더 있다.

  • push_back은 새로운 원소를 벡터의 끝에 더할 것이다.

  • pop_back은 벡터의 끝에서 원소를 하나 없앨 것이다.

  • insert 는 하나 또는 여러개의 원소를 벡터의 원하는 위치에 삽입할 것이다.

  • erase는 하나 또는 여러개의 원소를 원하는 위치에서 없앨 것이다.

그런데 insert나 erase는 벡터에서 오버헤드가 큰 연산임에 주의하라. 만약 insert나 erase를 써야한다면, 벡터 대신 list 데이터구조를 사용하는 것이 더 효율적일 것이다.

<vector-mod.cpp>=
#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> v;

    for (int i=0; i<10; i++) v.push_back(i);
    cout << "Vector initialised to:" << endl;
    for (int i=0; i<10; i++) cout << v[i] << ' ' ;
    cout << endl;

    for (int i=0; i<3; i++) v.pop_back();
    cout << "Vector length now: " << v.size() << endl;
    cout << "It contains:" << endl;
    for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
    cout << endl;

    int a1[5];
    for (int i=0; i<5; i++) a1[i] = 100;

    v.insert(& v[3], & a1[0],& a1[3]);
    cout << "Vector now contains:" << endl;
    for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
    cout << endl;

    v.erase(& v[4],& v[7]);
    cout << "Vector now contains:" << endl;
    for (int i=0; i<v.size(); i++) cout << v[i] << ' ';
    cout << endl;
}

위의 예에서는 벡터 v가 선언된 후, push_back을 사용하여 초기화 되었다. 그리고 pop_back으로 뒤의 몇 원소가 없어졌고, 배열이 하나 만들어져서 그 내용이 insert를 사용해서 v에 삽입되었다. 마지막으로 몇몇 원소들을 지우기 위해 erase가 사용되었다. 위에 사용된 함수들은 다음과 같은 인자들을 받는다.

  • push_back : vector에 들어가는 것과 같은 타입의 인자를 하나 받는다.

  • pop_back : 인자를 받지 않는다. 그리고 빈 벡터에 대해 pop_back을 하면 안된다.

  • insert 는 세 가지 형태로 쓰인다.

    • insert(pos, T& x) : 원소 x 하나를 pos가 가리키는 위치에 삽입한다.

    • insert(pos, start, end) : 다른 컨테이너 안의 내용을 pos가 가리키는 위치에 삽입한다.

    • 삽입되는 원소들은 start에서 시작해서, end를 만날 때까지 (end가 가리키는 것은 들어가지 않는다) 이다.

    • insert(pos, int rep, T& x) : rep 개의 x값을 pos 위치에 삽입한다. (같은 값을 여러번 삽입)

위의 코드에 나와있듯이, pos가 가리키는 포지션 값은 원소가 삽입될 곳의 주소여야 한다. 마찬가지로 start와 end도 주소값이어야 한다. (사실 이것은 이들이 iterator이기 때문이다. 이에 대해서는 다음 장에서 더 살펴볼 것이다.)

  • erase는 두 가지 형태로 쓰인다 (pos, start와 end는 insert와 같은 형식을 갖는다)

    • erase(pos) : pos가 가리키는 위치의 원소를 없앤다.

    • erase(start,end) : start에서 end까지(end는 포함하지 않음)에 해당하는 원소들을 없앤다.

17.4.5. Vector Iterator

벡터 v의 원소들을 차례대로 보는 가장 쉬운 방법은 위에 한 방법같이 하는 것이다.

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

또다른 방법은 바로 iterator를 이용하는 것이다. iterator는 컨테이너의 포인터라고 생각하면 된다. 따라서 이를 증가시키면서 원소를 하나씩 접근하는 것이 가능하다. 벡터가 아닌 컨테이너의 경우는 iterator가 원소를 차례대로 접근할 수 있는 유일한 방법이다.

type T의 원소를 갖고 있는 벡터의 경우 :

vector<T> v;

iterator는 다음과 같이 선언된다.

vector<T>::iterator i;

이러한 iterator는 begin()이나 end()같은 함수에 의해 리턴되는 값으로 만들어진다. 같은 타입의 iterator들은 == 나 != 로 비교가능하고, ++을 이용한 증가나 *를 이용한 참조 등이 가능하다. [ 이 외에도 벡터 iterator는 더 많은 연산자를 갖고 있다. 이에 대해서는 다음 장을 참고해라 ].

다음은 iterator를 어떻게 벡터와 사용하는 지에 대한 예제이다.

<vector-iterator.cpp>=
#include <iostream>
#include <vector>

using namespace std;

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

    int j = 1;

    vector<int>::iterator i;

    // v를 1에서 10까지의 정수로 채운다.
    i = v.begin();
    while (i != v.end())
    {
        *i = j;
        j++;
        i++;
    }

    // v의 각 원소를 제곱한다.
    for (i=v.begin(); i!=v.end(); i++) *i = (*i) * (*i);

    // v의 내용을 출력한다.
    cout << "The vector v contains: ";
    for (i=v.begin(); i!=v.end(); i++) cout << *i << ' ';
    cout << endl;

}

*i 가 등호의 왼쪽(LHS)에서는 값을 변경하기 위해, 오른쪽(RHS)에서는 값을 참조하기 위해 쓰인 것에 주목해라.

17.4.6. 벡터의 비교

두 개의 벡터를 ==와 <를 이용해서 비교할 수 있다. ==는 양 쪽의 벡터가 같은 수의 원소를 갖고 대응되는 각원소들이 모두 같을 때 true를 리턴할 것이다. <은 두 벡터의 원소들을 차례대로 사전순서(lexicographical order)대로 비교한다. 예를들어 v1과 v2를 비교한다고 해보자 (v1 < v2). i=0이라 할 때, v1[i] < v2[i] 이면 true를 리턴하고, v1[i] > v2[i] 이면 false를 리턴한다. 만약 둘이 같으면 i를 증가시킨다 (즉, 다음 원소로 넘어간다). 만약 v1의 끝이 v2가 끝나기 전에 나타났다면 (즉, v1의 원소의 개수가 더 작고, v1이 v2의 앞부분과 내용이 같을 때) true를 리턴하고, 그렇지 않으면 false를 리턴한다. 다음의 예를 보자.

(1,2,3,4) < (5,6,7,8,9,10) 는 false.
(1,2,3) < (1,2,3,4) 는 true
(1,2,3,4) < (1,2,3) 는 false
(0,1,2,3) < (1,2,3) 는 true

아래의 코드는 위에서 세번째 예를 보여준다.

<vector-comp.cpp>=
#include <vector>
#include <iostream>

using namespace std;

int main()
{
    vector<int> v1;
    vector<int> v2;
    for (int i=0; i<4; i++) v1.push_back(i+1);
    for (int i=0; i<3; i++) v2.push_back(i+1);

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

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

    cout << "v1 < v2 is: " << (v1<v2 ? "true" : "false") << endl;
}
<= 와 >= 역시 예상하는 대로 동작할 것이다.

17.5. Iterator 와 STL

17절장을 봐라.

17.6. 리스트

17절장을 봐라.

17.7. 집합(Set)

set 컨테이너 타입은 벡터같이 인덱스를 통해 원소에 접근하는 것이 아니라, 원소를 직접 저장하고 뺄 수 있도록 해준다. set 컨테이너는 서로 다른 원소들만을 갖는 수학적인 집합과 같이 동작한다. 그러나, 수학적인 집합과는 다르게, 집합 안의 원소들은 (사용자가 지정하는) 어떤 순서 대로 저장되게 된다. 실제로 이것은 set 컨테이너로 수학적인 집합을 구현하는 데 있어 작은 제한일 뿐이고, 이렇게 함으로써 순서가 없는 것보다 많은 연산에서 더 효율적이 될 수 있다.

17.7.1. Set을 만들기

set 컨테이너를 만들기 위해서는 두 가지 template 인자가 필요하다 - 이는 set이 갖게 될 원소들의 타입과 두 원소를 비교할 수 있는 비교함수 function object의 타입이다.

set<T, Compare> s;

(set < T > s와 같은 선언도 가능해야한다. 이는 두번째 인자로서 디폴트 template 인자인 less < T >를 사용한다. 하지만 많은 C++ 컴파일러 (g++포함)가 기본 template 인자를 지원하지 못하고 있다.)

간단한 타입 T 에 대해서는 less < T > function object를 쓸 수도 있다. ( "function object"가 무엇인가 하는 고민은 할필요 없다.) 예를들어 아래와 같이 선언하면 된다.

set<int> s1;
set<double> s2;
set<char> s3;
set<string> s4;

( 선언할 때 뒤쪽의 > 두 개가 space로 띄어져 있음에 주의하라. 이는 compiler가 >를 쉬프트 연산자(>>) 와 구별하기 위해 꼭 필요한 것이다.) 각각의 경우 function object들은 각각의 타입에 맞게 <를 사용할 것이다. (이는 각각 int, double, char, string 타입이다. )

아래의 코드는 정수(int)의 set을 선언하고, insert 메쏘드를 사용하여 정수를 몇개 추가한다. 그리고 set을 차례대로 보면서 원소들을 출력한다. 재미있는 것은 추가하는 순서가 어떤 순서이든지 set의 내용은 정렬된 상태로 출력된다는 것이다.

<set-construct1.cpp>=
#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    set<int>::iterator i;

    s.insert(4);
    s.insert(0);
    s.insert(-9);
    s.insert(7);
    s.insert(-2);
    s.insert(4);
    s.insert(2);

    cout << "The set contains the elements: ";
    for (i=s.begin(); i!=s.end(); i++) cout << *i << ' ';
    cout << endl;
}

4가 두번 추가되었음에도 불구하고, 한번밖에 나오지 않는 것에 주의해라. 이는 집합이기 때문에 당연한 것이다.

17.7.2. Function Objects란 무엇인가?

C++의 멋진 특징 중 하나는 연산자의 오버로딩이다. 따라서 새로 만들어진 class에 대해 + 가 어떤 의미든지 갖도록 할 수 있다. 그런데, C++에서 오버로드 할 수 있는 연산자 중 함수 호출 연산자인 ()가 있고, 이는 class의 인스턴스가 함수와 같이 동작할 수 있도록 해줄 수 있다. 이것이 function object이다.

간단한 예제를 보자.

<function-object.cpp>=
#include <iostream>

using namespace std;

template<class T>
class square {
public:
    T operator()(T x) { return x*x; }
};
// 이는 *가 정의되는 어떤 T에 대해서든지 쓰일 수 있다.

int main()
{
    // function object를 만든다.
    square<double> f1;
    square<int> f2;

    // 이를 사용한다.
    cout << "5.1^2 = " << f1(5.1) << endl;
    cout << "100^2 = " << f2(100) << endl;

    // 아래의 내용은 컴파일 에러를 출력할 것이다.
    // cout << "100.1^2 = " << f2(100.1) << endl;
}

function object는 STL의 몇몇 부분, 특히 set과 map에서 많이 쓰인다.

function object가 필요한 경우를 생각해보자. 아래의 내용을 만족하는 comp라는 것을 생각해보자.

  1. 만약 comp(x,y), comp(y,z)가 true이면, comp(x,z)도 역시 true이다.

  2. comp(x,x)는 언제나 false이다.

어떤 x,y에 대해 comp(x,y)와 comp(y,x)가 false이면 x와 y는 같은 객체이다.

이는 숫자에서 미만관계 ( < )를 나타낸다. 위에서 쓰인 less < T > function object 는 type T에 대해 < 연산자로 정의되어 있다. 즉, 다음과 같다.

template<class T>
struct less {
  bool operator()(T x, T y) { return x<y; }
}

(진짜 정의는 레퍼런스를 사용하고, 적절한 const 선언을 사용하며 binary_function template class를 상속받는다.)

이는 만약 T가 < 연산자를 그 타입에 대해 정의해놓았다면, T 타입의 집합을 선언할 때, 비교를 위한 것으로 less < T > 를 사용할 수 있다는 것이다. 만약 < 연산자가 하고자 하는 것과 맞지 않을 수도 있다. 이럴 때는 다른 예가 있다. 이는 < 연산자를 이용하여 간단한 class를 만들고, 다른 방식의 비교를 하는 function object를 만든다. 오버로딩 된 <와 () 연산자가 STL과 잘 돌아가기 위해서는 const 를 적당히 써줘야 한다는 것에 주의하라.

<set-construct2.cpp>=
#include <iostream>
#include <set>

using namespace std;

// 이 class는 두 개의 멤버 변수를 갖는다.
// 오버로딩된 <은 멤버 f1값을 갖고 두 class를 비교한다.
class myClass {
private:
    int f1;
    char f2;
public:
    myClass(int a, char b) : f1(a), f2(b) {}
    int field1() const { return f1; }
    char field2() const { return f2; }
    bool operator<(myClass y) const
    { return (f1<y.field1()); }
};

// 이 function object는 멤버 f2의 값을 기초로
// myClass 타입의 객체들을 비교한다.
class comp_myClass {
public:
    bool operator()(myClass c1, myClass c2) const
    { return (c1.field2() < c2.field2()); }
};

int main()
{
    set<myClass> s1;
    set<myClass>::iterator i;
    set<myClass, comp_myClass> s2;
    set<myClass, comp_myClass>::iterator j;

    s1.insert(myClass(1,'a'));
    s2.insert(myClass(1,'a'));
    s1.insert(myClass(1,'b'));
    s2.insert(myClass(1,'b'));
    s1.insert(myClass(2,'a'));
    s2.insert(myClass(2,'a'));

    cout << "Set s1 contains: ";
    for (i=s1.begin(); i!=s1.end(); i++)
    { 
        cout << "(" << (*i).field1() << "," 
                << (*i).field2() << ")" << ' ';
    }
    cout << endl;

    cout << "Set s2 contains: ";
    for (j=s2.begin(); j!=s2.end(); j++)
    {
        cout << "(" << (*j).field1() << "," 
                << (*j).field2() << ")" << ' ';
    }
    cout << endl;
}

(1,a)와 (2,a)를 가진 집합 s1은 f1을 기준으로 비교를 한다. 따라서 (1,a)와 (1,b)는 같은 원소로 취급된다. (1,a)와 (1,b)를 가진 집합 s2는 f2를 기준으로 비교를 하기 때문에 (1,a)와 (2,a)가 같은 원소로 취급된다.

17.7.3. 출력하기

위의 예에서 집합의 내용을 출력하는 것은 별로 좋지 않다. 아래의 헤더파일은 operator<< 을 오버로딩하는 간단한 표현을 갖고 있다. 이는 간단한 원소 타입을 갖는 작은 집합에서는 잘 동작한다.

<printset.h>=
#ifndef _PRINTSET_H
#define _PRINTSET_H

#include <iostream>
#include <set>

template<class T, class Comp>
std::ostream& operator<<(std::ostream& os, const std::set<T,Comp>& s)
{
    std::set<T,Comp>::iterator iter = s.begin();
    int sz = s.size();
    int cnt = 0;

    os << "{";
    while (cnt < sz-1)
    {
        os << *iter << ",";
        iter++;
        cnt++;
    }
    if (sz != 0) os << *iter;
    os << "}";

    return os;
}
#endif

여기서 출력을 위해 사용한 << 용법은 집합의 원소들이 << 연산자를 사용할 수 있도록 정의되어있다고 가정한 것이다. 그래서 이를 콤마(,)로 구분하고 대괄호로 둘러싸서 출력되도록 한 것이다. 이는 다음 예에서도 사용될 것이다.

17.7.4. 원소의 수 구하기

집합이 공집합인지는 empty() 메쏘드를 사용하여 알 수 있다. 집합에 몇개의 원소가 들어있는지는 size() 메쏘드를 사용하여 알 수 있다. 이들은 인자없이 불려서 각각 true 나 false 혹은 정수(int)를 리턴한다.

<set-size.cpp>=
#include <iostream>
#include <set>
#include "printset.h"

using namespace std;

int main()
{
    set<int> s;

    cout << "The set s is  "
            << (s.empty() ? "empty." : "non-empty.") << endl; 
    cout << "It has " << s.size() << "elements." << endl;

    cout << "Now adding some elements... " << endl;

    s.insert(1);
    s.insert(6);
    s.insert(7);
    s.insert(-7);
    s.insert(5);
    s.insert(2);
    s.insert(1);
    s.insert(6);

    cout << "The set s is now  
            << (s.empty() ? "empty." : "non-empty.") << endl;
    cout << "It has " << s.size() << "elements." << endl;
    cout << "s = " << s << endl;
}

17.7.5. 집합이 서로 같은지 검사하기

두 집합이 서로 같은지는 == 연산자를 사용하여 검사할 수 있다. 이는 T::operator== 를 사용하여 각 원소를 차례대로 검사함으로써 이루어진다.

<set-equality.cpp>=
#include <iostream>
#include <set>
#include "printset.h"

using namespace std;

int main()
{
    set<int> s1, s2 ,s3;

    for (int i=0; i<10; i++)
    {
        s1.insert(i);
        s2.insert(2*i);
        s3.insert(i);
    }

    cout << "s1 = " << s1 << endl;
    cout << "s2 = " << s2 << endl;
    cout << "s3 = " << s3 << endl;
    cout << "s1==s2 is: " << (s1==s2 ? true. : false.) << endl;
    cout << "s1==s3 is: " << (s1==s3 ? true. : false.) << endl;
}

또한, 두 집합을 <으로 비교하는 것도 가능하다. s1 < s2 는 s1이 사전순서로(lexicographically) s2보다 작으면 true, 그렇지 않으면 false이다.

17.7.6. 원소를 추가하거나 삭제하기

집합에 원소를 추가하는 것은 insert 메쏘드 (위에 사용한 것과 같이)를, 삭제하는 것은 erase 메쏘드를 통해 이루어진다.

타입 T의 원소들을 갖고 있는 집합의 경우, 다음과 같이 이루어진다 :

  • pair < iterator, bool> insert(T& x). 이는 표준 insert 함수이다. 리턴값은 무시할수도 있고, 성공적으로 추가했는지를 알기 위해 사용할 수도 있다 (같은 원소가 이미 집합에 있을 경우 실패한다). 만약 추가가 성공했다면, bool 값은 true이고, iterator는 금방 추가된 원소를 가리키게 될 것이다. 만약 원소가 이미 존재하는 것이라면, bool 값은 false이고, iterator는 이미 있는 값이 동일한 원소를 가리키게 될 것이다.

  • iterator insert(iterator position, T& x). 이 insert 함수는 인자로서 추가하고자 하는 원소 외에 iterator를 받는데, 이는 추가할 위치를 찾기 시작할 iterator이다. 리턴되는 iterator는 위와 마찬가지로 새로 추가된 원소나 이미 존재하는 같은 값의 원소이다.

  • int erase(T& x). 이 erase함수는 지우고자 하는 원소를 인자로 받아 만약 그 원소가 존재하면 지우고서 1을 리턴하고, 없으면 0을 리턴한다.

  • void erase(iterator position). 이 erase함수는 특정 원소를 가리키는 iterator를 인자로 받아 그 원소를 지운다.

  • void erase(iterator first, iterator last). 이 erase함수는 두 iterator를 인자로 받아 [first,last] 범위의 모든 원소를 지운다.

아래의 예는 위 함수들의 사용법을 보여준다.

<set-add-delete.cpp>=
#include <iostream>
#include <set>
#include "printset.h"

using namespace std;

int main()
{
    set<int> s1;

    // 표준적인 방식으로 원소를 추가한다.
    s1.insert(1);
    s1.insert(2);
    s1.insert(-2);

    // 특정위치에 원소 삽입
    s1.insert(s1.end(), 3);
    s1.insert(s1.begin(), -3);
    s1.insert((s1.begin()++)++, 0);

    cout << "s1 = " << s1 << endl;

    // 성공적으로 추가되었는지 체크
    pair<set<int>::iterator,bool> x = s1.insert(4);
    cout << "Insertion of 4 " << (x.second ? worked. : failed.) 
            << endl;
    x = s1.insert(0);
    cout << "Insertion of 0 " << (x.second ? worked. : failed.) 
            << endl;

    // insert에서 리턴된 iterator를 두번째 형태의 insert의 인자로
    // 사용할 수 있다.
    cout << "Inserting 10, 8 and 7." << endl;
    s1.insert(10);
    x=s1.insert(7);
    s1.insert(x.first, 8);

    cout << "s1 = " << s1 << endl;

    // 몇 원소들을 지운다.
    cout << "Removal of 0 " << (s1.erase(0) ? worked. : failed.)
            << endl;
    cout << "Removal of 5 " << (s1.erase(5) ? worked. : failed.)
            << endl;

    // 원소를 찾아서, 지운다. (find 함수는 다음 장을 참조)
    cout << "Searching for 7." << endl;
    set<int>::iterator e = s1.find(7);
    cout << "Removing 7." << endl;
    s1.erase(e);

    cout << "s1 = " << s1 << endl;

    // 마지막으로 모든 원소를 지운다.
    cout << "Removing all elements from s1." << endl;
    s1.erase(s1.begin(), s1.end());
    cout << "s1 = " << s1 << endl;
    cout << "s1 is now " << (s1.empty() ? empty. : non-empty.)
            << endl;
}

17.7.7. 원소를 찾기

어떤 원소가 집합에 있는지 체크해주는 두가지 함수가 있다.

  • iterator find(T& x). 이 함수는 집합에 원소 x가 존재하는지 찾는다. 만약 찾으면 이를 가리키는 iterator를 리턴하고, 없으면 end()를 리턴한다.

  • int count(T& x). 이함수는 존재하면 1을, 없으면 0을 리턴한다. (multiset에서의 count함수는 같은 원소가 여러개 있을 수 있으므로 리턴값이 1보다 더 클 수도 있다. count라는 말의 뜻을 생각해보라! )

find의 사용법은 이미 위에 보인 적이 있다. 우리는 count를 이용하여 간단한 template기반의 집합에 속하는지 test하는 함수를 만들 수 있다. (이는 인자 x에 대한 레퍼런스를 제공한다.)

<setmember.h>=
#ifndef _SETMEMBER_H
#define _SETMEMBER_H
#include <set>

template<class T, class Comp>
bool member(T x, std::set<T,Comp>& s)
{
 return (s.count(x)==1 ? true : false);
}
#endif

// 이는 다음과 같이 쓰일 수 있다.

<set-membership.cpp>=
#include <iostream>
#include <set>
#include "printset.h"
#include "setmember.h"

using namespace std;

int main()
{
    set<int> s;
    for (int i= 0; i<10; i++) s.insert(i);
    cout << "s = " << s << endl;
    cout << "1 is " << (member(1,s) ?  : not) << " a member of s "
            <<  endl;
    cout << "10 is " << (member(10,s) ?  : not) << " a member of s "
            <<  endl;
}

17.7.8. 집합 연산

STL은 부분집합, 합집합, 교집합, 차집합, 대칭차집합(XOR) 등의 집합연산을 generic 알고리즘으로 제공한다. 이 함수들을 이용하기 위해서는 algo.h를 include 해야한다. (아래의 내용중 iter는 적절한 iterator를 의미한다).

  • bool includes(iter f1,iter l1,iter f2,iter l2).

    위 함수는 [f2,l2] 범위에 있는 것들이 [f1,l1] 안의 것들을 포함하는 지를 체크한다. 만약 포함하면 true를, 그렇지 않으면 false를 리턴한다. 따라서 한 집합이 다른 집합을 포함하는 지를 보려면, 다음과 같이 하면 된다.

    includes(s1.begin(), s1.end(), s2.begin(), s2.end())

    The includes function checks the truth of 3#3 ( that is of 4#4). 이 함수는 집합이 < 연산자를 이용해 정렬되었다고 본다. 만약, <이 아닌 다른 연산자 가 사용되었다면, 이(function object)를 마지막 인자로서 추가로 넘겨주면 된다.

  • iter set_union(iter f1,iter l1,iter f2,iter l2,iter result).

    이는 [f1,l1]과 [f2,l2] 범위에 있는 집합들의 합집합을 만든다. 인자로 주는 result 값은 새로만들어진 합집합의 첫 인자를 가리키는 iterator이다. 리턴값은 새로운 집합의 끝(end)를 가리키는 iterator이다.

result 인자가 iterator란 말은, 다음과 같은 식으로 set_union을 사용하면 안된다는 것이다.

      set<int> s1, s2, s3;
      // s1 과 s2의 원소를 가지고 합집합을 만든다.
      // (그러나 이런 식으로는 동작하지 않음)
      set_union(s1.begin(), s1.end(), 
                s2.begin(), s2.end(), 
                s3.begin());

그 이유는 begin()과 end()가 집합이나 맵에 사용될 때는 상수 input iterator가 되기 때문이다. 이러한 iterator는 집합의 원소를 읽기 위해서는 사용될 수 있지만, 값을 쓸 수는 없다. (또한 만약 값을 쓸 수 있게 한다면 집합의 순서를 망가뜨릴 수 있는 위험이 있기 때문이기도 하다)

해결책은 set_type의 insert iterator를 사용하는 것이다. 이는 (*i)=value 같은 불가능한 구문을 s.insert(i,value)의 형태로 쓸 수 있게 해준다. (여기서 s는 iterator i가 가리키는 집합이다. 이는 다음과 같이 쓰인다.

      // 편의를 위해 Typedef를 사용
      typedef set<int> intSet;  
      intSet s1, s2, s3;
      // s1과 s2에 몇 원소를 추가.
      // 그리고 합집합을 구한다.
      set_union(s1.begin(), s1.end(), 
                s2.begin(), s2.end(), 
                inserter(s3,s3.begin()) );

이제 위에 나오는 것들을 종합적으로 사용하는 예제를 보자.

<set-theory.cpp>=
#include <iostream>
#include <set>
#include <algorithm>
#include <iterator>
#include "printset.h"

using namespace std;

int main()
{
    typedef set<int> intSet;

    intSet s1, s2, s3, s4;

    for (int i=0; i<10; i++)
    { s1.insert(i);
        s2.insert(i+4);
    }
    for (int i=0; i<5; i++) s3.insert(i);

    cout << "s1 = " << s1 << endl;
    cout << "s2 = " << s2 << endl;
    cout << "s3 = " << s3 << endl;

    // s1이 s2의 부분집합인가?
    bool test = includes(s2.begin(),s2.end(),s1.begin(),s1.end());
    cout << "s1 subset of s2 is " << (test ? true. : false.) << endl;

    // s3가 s1의 부분집합인가?
    test = includes(s1.begin(),s1.end(),s3.begin(),s3.end());
    cout << "s3 subset of s1 is " << (test ? true. : false.) << endl;

    // s1과 s2의 합집합.
    set_union(s1.begin(), s1.end(), s2.begin(), s2.end(),
            inserter(s4,s4.begin()) );
    cout << "s1 union s2 = " << s4 << endl;

    // s4를 지우고, s1과 s2의 교집합을 구한다.
    // ( 만약 s4를 지우지 않으면 원래 s4에 들어있는 것들도
    // 같이 들어가게 될 것이다. )
    s4.erase(s4.begin(),s4.end());
    set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(),
            inserter(s4,s4.begin()) );
    cout << "s1 intersection s2 = " << s4 << endl;

    // 차집합
    s4.erase(s4.begin(),s4.end());
    set_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
            inserter(s4,s4.begin()) );
    cout << "s1 minus s2 = " << s4 << endl;

    // 차집합은 대칭적이지 않다. (즉, A-B != B-A)
    s4.erase(s4.begin(),s4.end());
    set_difference(s2.begin(), s2.end(), s1.begin(), s1.end(),
            inserter(s4,s4.begin()) );
    cout << "s2 minus s1 = " << s4 << endl;

    // 대칭차집합
    s4.erase(s4.begin(),s4.end());
    set_symmetric_difference(s1.begin(), s1.end(), s2.begin(), s2.end(),
            inserter(s4,s4.begin()) );
    cout << "s1 symmetric_difference  s2 = " << s4 << endl;

    // 대칭차집합은 대칭적이다. (즉, commutative)
    s4.erase(s4.begin(),s4.end());
    set_symmetric_difference(s2.begin(), s2.end(), s1.begin(), s1.end(),
            inserter(s4,s4.begin()) );
    cout << "s2 symmetric_difference  s1 = " << s4 << endl;
}

17.8. 맵

17절장을 보아라.

17.9. STL 알고리즘

17절장을 보아라.

이전처음으로다음
Templates C++에서의 쓰레드

Recent Posts

Archive Posts

Tags

About

Joinc proposes educational computer-engineering contents. Especially, the contents focus on recently popular and meaningful topics, technically helpful for those who already work or to-be developers in the computer industry and theoretical or typical topics covered in undergraduate courses.

Get in Touch

  • joinc.help@gmail.com

Categories

Copyrights © - Joinc, All Rights Reserved.
Inherited From - Yundream Rebranded By - Joonphil