8장: set, multiset, bitset
8.1 set 데이터 추상(data abstraction)
set은 값들의 콜렉션이다. set 데이터 구조를 구현하는데 사용되는 컨테이너는 순서를 유지하여 값들을 관리하기 때문에, 원소의 삽입과 삭제뿐만 아니라, 특정 값이 콜렉션에 들어있는지의 여부를 검사하는데 있어 최적화되어 있다. 이러한 연산들은 각각 logarithmic 횟수로 수행된다. 반면에 list, vector, deque에서는 각각의 연산들이 최악의 경우에 컨테이너에 담긴 모든 원소들을 살피게 될수도 있다. 이러한 이유때문에, 삽입, 삭제와 값의 포함여부에 대한 검사가 중요한 문제에서는 set을 선택해야 한다. list에서처럼, set도 사이즈에 제한을 받지 않고, 콜렉션으로부터 원소들을 첨가하거나 삭제할 때 늘어나거나 줄어든다.
표준 라이브러리는 두가지 종류의 set을 제공하는데, set 컨테이너에서는 모든 값들이 유일해야 하고, set에 이미 들어있는 값을 중복 삽입하는 것은 무시가 된다. 한편, multiset 컨테이너에서는 같은 값이 여러개 있어도 이를 허용한다.
8.1.1 Include 화일
set이나 multiset을 사용할 때는 set 헤더화일을 반드시 포함시켜야 한다.
#include <set>
8.2 set과 multiset 연산
set과 multiset이 제공하는 멤버 함수들을 자세히 알아본다. 멤버 함수들이 기초적인 연산들을 제공하지만, 13장과 14장에서 설명하는 generic 알고리듬을 사용함으로써 이들 데이터 구조를 좀더 유용하게 사용할 수 있다.
8.2.1 set의 선언과 초기화
set는 템플릿 타입으로 첫번째 인자로 원소 타입을, 두번째 인자로 키값을 비교하는 연산자를 명시해주어야 한다. 두번째 인자는 생략가능한데, 따로 명시하지 않으면, 키타입에서 정의하고 있는 less-than 연산자를 사용한다. 원소의 타입은 int 또는 double과 같은 primitive 타입이나, 포인터 타입 또는 사용자 정의 타입이 될 수 있다. 원소 타입은 상등 연산자(==)와 less-than 연산자(<)를 가지고 있어야 한다. Initializing Sets with Iterators
set은 초기값없이 선언될 수도 있고, 한쌍의 반복자를 써서 다른 컨테이너에 담긴 값들로 초기화할 수도 있다. 이 두가지 경우 모두 비교 함수를 인자로 사용할 수 있으며, 생략가능하다. 이 비교함수는 템플릿 인자로 명시된 비교 함수를 덮어쓴다. 이런식으로 비교함수를 지정함으로써, 값은 같지만 순서를 다르게 매기는 두개 이상의 set을 다루는 경우에 유용하다. set 멤버 함수들이 여러개 개체화되는 것을 막을 수 있기 때문이다. 복사 생성자를 사용하여 다른 set의 복사본이 되는 set을 만들 수 있다.
set <int> set_one;
set <int, greater<int> > set_two;
set <int> set_three(greater<int>());
set <gadget, less<gadget> > gset;
set <gadget> gset(less<gadget>());
set <int> set_four (aList.begin(), aList.end());
set <int> set_five
(aList.begin(), aList.end(), greater<int>());
set <int> set_six (set_four); // copy constructor
한 set을 다른 set에 대입할 수도 있고, swap() 연산을 써서 두 set간의 값들을 교환할 수도 있다.
set_one = set_five;
set_six.swap(set_two);
8.2.2 타입 정의
set과 multiset 클래스는 많은 타입 정의들을 포함한다. 이들은 선언문에서 가장 많이 사용된다. 예를 들어, 정수 set에 사용할 반복자는 다음과 같이 선언된다.
set<int>::iterator location;
iterator뿐만 아니라, 다음 타입들도 정의되어 있다.
|
value_type |
The type associated with the elements the set maintains. |
|
const_iterator |
An iterator that does not allow modification of the underlying sequence. |
|
reverse_iterator |
An iterator that moves in a backward direction. |
|
const_reverse_iterator |
A combination constant and reverse iterator. |
|
reference |
A reference to an underlying element. |
|
const_reference |
A reference to an underlying element that will not permit modification. |
|
size_type |
An unsigned integer type, used to refer to the size of containers. |
|
value_compare |
A function that can be used to compare two elements. |
|
difference_type |
A signed integer type, used to describe the distance between iterators. |
|
allocator_type |
An allocator used by the container or all storage management. |
8.2.3 삽입
list나 vector와 달리 set에 원소를 새로 추가하려면 단한가지 방법밖에 없다. insert() 멤버 함수를 써서 set이나 multiset에 값을 삽입할 수 있는 것이다. multiset의 경우에는 방금 삽입한 값을 가리키는 반복자를 리턴한다. set의 경우에는 pair를 리턴하는데, 첫번째 필드는 반복자이고, 두번째 필드는 부울값으로 원소가 삽입되었는 지의 여부를 표시한다. set에서는 원소를 삽입할 때 이미 콜렉션내에 해당 원소가 있으면, 삽입이 이루어지지 않기 때문이다.
set_one.insert(18);
if (set_one.insert(18).second)
cout << "element was inserted" << endl;
else
cout << "element was not inserted " << endl;
다른 컨테이너에 들어있는 값들을 삽입할 때는 한쌍의 반복자를 사용한다.
set_one.insert(set_three.begin(), set_three.end());
pair 데이터 구조는 값들의 투플이다. 첫번째 값은 first라는 필드명으로 접근하고, 두번째 값은 second라는 필드명으로 접근한다. make_pair()라는 함수는 pair 클래스의 개체를 만드는 작업을 간편하게 해준다.
template <class T1, class T2>
struct pair {
T1 first;
T2 second;
pair (const T1 & x, const T2 & y) : first(x), second(y) { }
};
template <class T1, class T2>
inline pair<T1, T2> make_pair(const T1& x, const T2& y)
{ return pair<T1, T2>(x, y); }
예를 들어, 새로운 원소의 키부분이 이미 존재하는 키값인지 알아보기 위해서, 키값들이 서로 일치하는지를 검사할 때, 상등(==) 연산자를 사용하는 것이 아니라, 비교 함수를 사용한다. 키값들의 순서를 매기기위해 사용되는 비교 함수가 양방향으로 모두 거짓이면, 두 키값은 서로 같다고 본다. 다시 말해서, Compare(key1, key2)가 거짓이고, Compare(key2, key1)도 거짓이면, key1과 key2는 상등이라고 보는 것이다.
8.2.4 set에서의 삭제
set에서 값을 삭제할 때는 erase() 멤버 함수를 사용한다. 인자는 특정 값이거나, 값을 가리키는 반복자 또는 값들의 range를 지정하는 한쌍의 반복자일 수 있다. 첫번째 형태를 multiset에 사용할 때는 인자로 주어진 값과 일치하는 모든 원소들이 삭제되고, 리턴값은 삭제된 원소들의 갯수를 의미한다.
// erase element equal to 4
set_three.erase(4);
// erase element five
set<int>::iterator five = set_three.find(5);
set_three.erase(five);
// erase all values between seven and eleven
set<int>::iterator seven = set_three.find(7);
set<int>::iterator eleven = set_three.find(11);
set_three.erase (seven, eleven);
컨테이너가 가지고 있는 원소들의 타입이 소멸자를 가지고 있다면, 원소가 삭제되기 전에 소멸자를 호출하게 된다.
8.2.5 검색과 카운팅
size() 멤버함수는 컨테이너가 가지고 있는 원소의 갯수를 반환한다. empty() 멤버 함수는 컨테이너가 비어 있을 때 참을 리턴하는데, size()를 0과 비교하는 것보다 대체로 더 빠르다.
find() 멤버 함수는 특정값을 인자로 취해서 set내에 해당 값이 존재하면, 그 값의 위치를 가리키는 반복자를 리턴하고, set내에 존재하지 않으면, end-of-set에 해당하는 반복자를 리턴한다(이는 end()가 리턴하는 값과 같은 것이다). 같은 값이 여러개 존재할 수 있는 multiset의 경우에는 이들 값중에서 적절한 값을 리턴한다.
set<int>::iterator five = set_three.find(5);
if (five != set_three.end())
cout << "set contains a five" << endl;
lower_bound()와 upper_bound() 멤버 함수는 multiset과 같이 쓰일 때 아주 쓸모가 있다. set에 사용하면, 단지 find() 함수를 흉내내는 것에 지나지 않는다. lower_bound() 멤버 함수는 인자로 주어진 키값과 일치하는 첫번째 원소를 리턴하고, 반면에 upper_bound() 멤버 함수는 키값과 일치하는 마지막 원소를 지나서 첫번째 원소를 반환한다. 마지막으로, equal_range() 멤버 함수는 lower bound와 upper bound를 포함하는 반복자의 pair를 리턴한다.
count() 멤버 함수는 인자로 주어지는 값과 일치하는 원소의 갯수를 리턴한다. set의 경우에는 이 값이 0 또는 1인 반면, multiset의 경우에는 음수가 아닌 임의의 값이 될 수 있다. 0이 아닌 정수값은 참으로 간주하므로, count() 함수를 원소의 포함 검사에 사용할 수도 있다. 또는 find()의 리턴값을 end-of-collection 반복자와 비교하여 포함 검사를 할 수도 있다.
if (set_three.count(5))
cout << "set contains a five" << endl;
8.2.6 반복자
begin()과 end() 멤버 함수는 set과 multiset에 대한 반복자를 생성한다. 이들 함수들이 만들어내는 반복자들은 상수이어야 하는데, 이는 set의 원소에 새로운 값을 대입하게 되어 set에 대한 순서 관계가 깨지는 것을 막기 위해서이다. 이들 반복자들을 사용하여, set을 선언했을 때 명시한 비교 연산자로 정해진 순서대로 원소들을 접근할 수 있다. rbegin()과 rend() 멤버 함수는 역순으로 원소들을 접근하는 반복자들을 생성한다.
8.2.7 set 연산
전통적인 집합 연산인 부분집한 검사, union, intersection, difference 연산들은 멤버함수로 제공되지 않지만, 대신에 ordered 구조에 사용되는 generic 알고리듬으로 구현되어 있다. 이들 함수들에 관해서는 14.7절에 자세히 설명되어 있다. 다음은 이들 함수들이 set과 multiset 클래스와 함께 사용하는 법을 간략히 설명하고 있다.
8.2.7.1 부분집합 검사
includes()함수는 한 집합이 다른 집합의 부분집합인지 알아보는데 사용된다. multiset의 경우에는 두번째 집합내에서 일치하는 원소의 갯수가 첫번째 원소의 갯수를 초과해야 한다. 인자의 갯수는 포함되는 집합을 나타내는 반복자 한쌍과 포함하는 집합을 나타내는 반복자 한쌍해서, 모두 4개가 필요하다.
if (includes(set_one.begin(), set_one.end(),
set_two.begin(), set_two.end()))
cout << "set_one is a subset of set_two" << endl;
원소를 비교하는데 사용되는 것은 less-than 연산자(<)이며, set을 선언할 때 명시한 비교 연산자를 사용하는 것이 아니다. 이것이 맘에 안들면, 다른 형태의 includes() 함수를 사용하면 된다. 이것은 두 집합의 원소의 순서를 매기기 위해서 사용되는 비교 함수가 인자로 추가되어, 총 5개의 인자를 필요로 한다.
8.2.7.2 합집합과 교집합
set_union() 함수는 두 집합의 합집합을 구성하는데 사용된다. 연산에 관여되는 두집합은 반복자의 쌍으로 표시하고, 합집합의 결과는 5번째 인자로 명시된 출력 반복자로 복사된다. 결과를 set으로 구성하기 위해서, 삽입 반복자를 사용하여 출력 반복자를 만들어야 한다.(삽입 반복자에 관해서는 2.4절을 참고)
// union two sets, copying result into a vector
vector<int> v_one (set_one.size() + set_two.size());
set_union(set_one.begin(), set_one.end(),
set_two.begin(), set_two.end(), v_one.begin());
// form union in place
set<int> temp_set;
set_union(set_one.begin(), set_one.end(),
set_two.begin(), set_two.end(),
inserter(temp_set, temp_set.begin()));
set_one.swap(temp_set); // temp_set will be deleted
set_intersection() 함수도 이와 비슷하며, 두집합의 교집합을 형성한다.
includes() 함수에서처럼 원소를 비교할 때는 선언시 명시한 비교 연산자대신에 less-than 연산자(<)를 사용한다. 이것이 부적절하다고 생각되면, 6번째 인자로 비교 연산자를 요구하는 다른 형태의 set_union()과 set_intersection()을 사용하면 된다.
multiset의 합집합 연산은 두집합을 합병하는 연산과는 구별되어야 한다. 한 집합이 7을 3개 포함하고 있고, 다른 집합이 7을 2개 포함하고 있다고 가정하자. 이들의 합집합은 7을 3개만 포함하지만 합병한 결과에는 5개가 포함된다. 합병은 merge() 함수를 이용한다(14.6절 참고). 이 함수의 인자는 set_union() 함수와 동일하다.
8.2.7.3 차집합
차집합 연산에는 두가지 형태가 있다. 단순 차집합은 첫번째 집합의 원소중에서 두번째 집합에 속하지 않는 원소들을 나타낸다. 대칭 차집합은 두번째 집합의 원소를 제외한 첫번째 집합의 원소들과 첫번째 집합의 원소를 제외한 두번째 집합의 원소들을 합한 것이다. 이들은 각각 set_difference()와 set_symmetric_difference() 함수로 구성된다. 이들 함수들은 set_union()와 사용법이 비슷하다.
8.2.8 기타 generic 알고리듬
set은 순서를 매기고, 상수 반복자를 가지기 때문에, 13절과 14절에 설명하고 있는 generic 함수중에는 set에 적용할 수 없거나 별로 유용하지 않는 것들이 많다. 그러나, 다음 표는 set 데이터 타입과 함께 사용될 수 있는 몇가지 함수들을 보여주고 있다.
|
용도 |
이름 |
해당절 |
|
Copy one sequence into another |
copy |
|
|
Find an element that matches a condition |
find_if |
|
|
Find a sub-sequence within a set |
search |
|
|
Count number of elements that satisfy condition |
count_if |
|
|
Reduce set to a single value |
accumulate |
|
|
Execute function on each element |
for_each |
8.3 예제 프로그램 - 철자 검사기
A simple example program that uses a set is a spelling checker. The checker takes as arguments two input streams; the first representing a stream of correctly spelled words (that is, a dictionary), and the second a text file. First, the dictionary is read into a set. This is performed using a copy() and an input stream iterator, copying the values into an inserter for the dictionary. Next, words from the text are examined one by one, to see if they are in the dictionary. If they are not, then they are added to a set of misspelled words. After the entire text has been examined, the program outputs the list of misspelled words.
void spellCheck (istream & dictionary, istream & text)
{
typedef set <string, less<string> > stringset;
stringset words, misspellings;
string word;
istream_iterator<string> dstream(dictionary), eof;
// first read the dictionary
copy (dstream, eof, inserter(words, words.begin()));
// next read the text
while (text >> word)
if (! words.count(word))
misspellings.insert(word);
// finally, output all misspellings
cout << "Misspelled words:" << endl;
copy (misspellings.begin(), misspellings.end(),
ostream_iterator<string>(cout, "\n"));
}
void findMisspell(stringset & words, string & word)
{
for (int I = 1; I < word.length(); I++) {
swap(word[I-1], word[I]);
if (words.count(word))
cout << "Suggestion: " << word << endl;
// put word back as before
swap(word[I-1], word[I]);
}
}
8.4 bitset 추상(abstraction)
bitset은 set과 vector의 cross이다. vector<bool>과 같이, 추상은 이진값의 집합이다. 그러나, 논리적 bit별 연산을 사용하여 bitset상에 set 연산을 수행할 수 있다. bitset 클래스는 원소를 접근하는데 사용할 반복자를 제공하지 않는다.
8.4.1 Include 화일
#include <bitset>
8.4.2 bitset의 선언과 초기화
bitset은 템플릿 클래스이지만, 템플릿 인자가 타입이 아니라 정수값이 된다. 이 값은 set이 포함하는 비트의 갯수를 나타낸다.
bitset<126> bset_one; // create a set of 126 bits
좀 다른 기법으로 set의 사이즈를 생성자의 인자로 명시할 수도 있다. 실제 사이즈는 템플릿 인자로 사용된 값과 생성자 인자로 사용된 값 중 더 작은 값으로 정해진다. 이렇게 하는 것은 프로그램에서 두개 이상의 서로 다른 사이즈의 bit vector를 포함하는 경우에 유용하다. 템플릿 인자로 더 큰값을 사용함으로써, 해당 클래스에 대한 메쏘드를 한번만 생성하게 된다. 그러나, 실제 사이즈는 생성자가 결정하게 된다.
bitset<126> bset_two(100); // this set has only 100 elements
생성자의 세번째 형태는 '0'과 '1'이라는 문자로 이루어진 문자열을 인자로 받는다. 이 문자열에 속하는 문자와 같은 갯수의 원소를 가지는 bitset을 만들고, 문자열에 명시된 값들로 초기화한다.
bitset<126> small_set("10101010"); // this set has 8 elements
8.4.3 접근과 검사
bitset의 각각의 bit는 첨자 연산을 사용하여 접근이 가능하다. bit가 1인지 0인지를 알아보기 위해서는 test() 멤버 함수를 사용한다. bitset에 한 bit가 'on'인지를 알아보기 위해서는 any() 멤버 함수를 사용하고 불값을 리턴한다. any()의 반대는 none() 멤버 함수이다.
bset_one[3] = 1;
if (bset_one.test(4))
cout << "bit position 4 is set" << endl;
if (bset_one.any())
cout << "some bit position is set" << endl;
if (bset_one.none()) cout << "no bit position is set" << endl;
set() 함수는 특정 bit를 세팅하는데 사용된다. 'bset_one.set(I)'는 'bset_one[I] = true'과 동일하다. 아무 인자 없이 이 함수를 호출하면 모든 비트를 'on'으로 세팅한다. reset() 함수도 사용법이 비슷한데, 인자로 명시된 위치의 비트를 'off'로 세팅하고, 인자가 없으면, 모든 비트를 'off'로 세팅한다. flip() 함수도 제공되는데 비트를 가리키는 레퍼런스에 대한 멤버 함수로서 제공된다.
bset_one.flip(); // flip the entire set
bset_one.flip(12); // flip only bit 12
bset_one[12].flip(); // reflip bit 12
size() 멤버 함수는 bitset의 사이즈를 리턴하고, count() 멤버 함수는 세팅되어 있는 비트들의 갯수를 리턴한다.
8.4.4 set 연산
bitset에 대한 set 연산은 bit-wise 연산자를 사용하여 구현되는데, 정수값에 대해 수행되는 방식과 비슷하다.
bitset에 부정 연산자(~ 연산자)를 적용하면 인자로 지정된 bitset의 원소들의 반대값을 포함하는 새로운 bitset을 리턴한다.
두 bitset의 교집합은 and 연산자(& 연산자)를 통해 이루어진다. 대입형태의 연산자도 가능하며, 이때 좌변이 두집합의 disjunction이 된다.
bset_three = bset_two & bset_four;
bset_five &= bset_three;
두 집합의 합집합도 or 연산자(| 연산자)를 사용하여 비슷한 방식으로 이루어진다. exclusive-or는 exclusive-or 연산자(^ 연산자)를 사용하여 이루어진다.
왼쪽 쉬프트 연산자(<< 연산자)과 오른쪽 쉬프트 연산자(>> 연산자)는 bitset을 왼쪽 또는 오른쪽으로 쉬프트하는데 사용된다. 한 비트를 왼쪽으로 'n'만큼 쉬프트하면, 새로운 비트 위치 I는 이전의 I-n의 값이 된다(?). 새로운 위치들은 0값들로 쉬프트된다.
8.4.5 변환
to_ulong() 멤버 함수는 bitset을 'unsigned long'으로 바꾼다. 더 많은 원소를 가지는 bitset에 이 연산을 수행하면 에러를 발생한다.
to_string() 멤버 함수는 bitset을 'string' 타입으로 바꾼다. 이때 string은 bitset의 원소갯수만큼의 문자를 가지게 된다. 각각의 0비트는 문자 '0'으로 바꾸고, 1비트는 문자 '1'로 바꾼다.
출처 : http://quartzd.tistory.com