안녕하세요? cedar 김백일입니다.
이제까지의 팁에서는 시퀀스 컨테이너(sequence container)인
vector, list, deque를 사용한 예제만 사용되었습니다.
이번에는 associative container(연관 또는 연상 컨테이너)인
map 또는 hash_map을 사용하는 예제입니다.
연관 컨테이너는, 키 값을 넣으면 그 키값에 해당하는 원소를 액세스하는 자료구조입니다.
크게 sorted associative container(정렬 연관 컨테이너)와
hash associative container(해쉬 연관 컨테이너)로 나눌 수 있습니다.
前者는 자료구조 전체가 키 값의 크기에 따라 정렬되어 있는 구조입니다.
즉, 트리(tree)를 사용하여 구현한 컨테이너입니다.
저장과 검색 시간이 O(log N)이 걸립니다.
STL의 정렬 연관 컨테이너는 map(multimap)과 set(multiset)이 있는데요,
map은 키 값과 원소가 구분된 pair로 저장되지만,
set은 키 값 자체가 원소라는 것만 다릅니다.
(C++빌더 VCL에서의 Set과 유사하지만 훨씬 강력하지요.)
multi 가 붙는 컨테이너는 키 값이 중복될 수 있다는 점이 다릅니다.
STL에서는 보통 빨강-검정 트리(red-black tree)라는 균형 이진 탐색 트리(balanced binary search tree)로 구현합니다(다른 균형 이진 탐색 트리인 AVL tree보다 더 빠르다고 하지요.)
後者는 물론 해쉬 테이블(hash table)을 말합니다.
저장과 검색시간이 상수, 즉 O(1)이라는 장점이 있지만,
전체 구조가 정렬되어 있지 않다는 단점도 있습니다.
STL에서의 이름은 hash_map, hash_set, hash_multimap, hash_multiset인데요,
그런데 애석하게도, ANSI C++ 표준에는 포함되어 있지 않습니다.
C++빌더6나 gcc 사용자시라면 SGI의 STL 배포본인 STLport가 기본으로 설치되어 있기 때문에 그대로 쓸 수 있지만,
C++빌더5 이하나 다른 컴파일러 사용자시라면
http://stlport.org 에서 다운받으셔서 따로 설치하셔야 합니다.
M$ VC++ 사용자시라면, Dinkumware의 상용 STL을 구입하여 설치하는 방법도 있습니다.
사설이 길었는데요,
실제 map을 사용하는 예제를 들어보죠.
map이란 간단히 말하자면, 인덱스를 정수뿐만 아니라,
operator<() 가 정의된 모든 타입(클래스)를 쓸 수 있는 배열이라고 생각하시면 됩니다.
예를 들어 "word"라는 단어의 빈도가 1234라면
map<string, int> freq;
freq["word"] = 1234;
cout << freq["word"] << endl;
로 쓰면 된다는 겁니다. 간단하죠?
참고: 검색이나 갱신의 경우는 operator[]를 사용하는 것이 좋지만,
새 값을 저장할 경우,
C++의 기본 타입(primitive type)인 int나 float, double 등을 쓰실 때는 상관이 없지만,
생성자와 소멸자의 호출 비용이 큰 클래스를 저장할 때는 operator[]를 쓰면 성능이 저하됩니다.
이 때는 insert 멤버함수를 사용하세요.
freq.insert(make_pair("word", 1234)); // 이 경우는 int를 저장하는 경우니까 별로 속도 차이는 없습니다.
이런 식으로 쓰시는 것이 좋습니다.
다음은 텍스트 파일에서 단어를 하나씩 입력받아,
각 단어별로 빈도와 확률을 구하는 프로그램입니다.
트리나 해쉬테이블을 따로 구현할 필요없이
간단히 배열의 인덱스에 문자열을 쓰는 것만으로 간단히 해결됩니다.
//---------------------------------------------------------------------------
// wordfreq.cpp
//---------------------------------------------------------------------------
#include <cstdlib>
#include <iostream>
#include <fstream>
#pragma hdrstop
#include <string>
#include <map>
//#include <hash_map>
//---------------------------------------------------------------------------
#pragma argsused
using namespace std;
int main(int argc, char* argv[])
{
if (argc < 3) {
cerr << "usage: wordfreq corpusfile freqfile\n";
exit(1);
}
ifstream fin(argv[1]);
ofstream fout(argv[2]);
// Ansi c++ STL의 map은 sorted associative container(red-black tree)
typedef map<string, int> freq_map;
// Hash table(unsorted associative container)을 사용할 경우
//typedef hash_map<string, int> freq_map;
freq_map freq;
string word;
int wc; // word count입니다. 확률을 구하기 위해 필요합니다.
for (wc = 0; fin >> word; wc++) {
// freq에 word가 있으면 1만큼 증가, 없으면 새로 추가하고 빈도를 1로 세팅.
freq[word]++; // 이 코드가 핵심입니다. 무지 간단하죠?
// 만약, 새 단어 추가시의 코드를 다르게 처리하시려면,
// if (freq.count(word)) // count()의 리턴값은 1아니면 0입니다.
// freq[word]++;
// else
// freq.insert(make_pair(word, 1));
// 로 하시면 됩니다.
}
fout.precision(15);
for (freq_map::iterator i = freq.begin(); i != freq.end(); i++)
fout << i->first << '\t' << i->second << '\t' // 결과는 word순으로 정렬됨.
<< (double)i->second / (double)wc << '\n';
return 0;
}
//---------------------------------------------------------------------------
