C++,STL :: 연관 컨테이너를 이용한 단어 갯수 세기(교차참조 테이블)

# 연관 컨테이너(associative container)

데이터를 순차 컨테이너에 저장하지 않고, 연관 컨테이너(associative container)에 저장할 수 있다.
이러한 컨테이너들은 요소들을 삽입한 순서대로 배열하지 않고, 요소의 값에 따라 삽입 순서를 자동적으로 조정한다.
뿐만 아니라, 컨테이너의 순서를 직접 유지시키지 않아도, 이 순서를 통해 특정 요소들을 더 빨리 검색할 수 있다.

연관 자료구조의 가장 일반적인 형태는 키-값 쌍(key-value pair)로 저장하는 것이다. 값 하나 마나 각각의 키를 연결시키면
그 키에 의하여 해당 요소들을 빠르게 삽입하거나, 가져올 수 있다. 그러한 자료구조를 연관 배열(associative array)라고 부른다.
C++에서 가장 일반적인 연관 배열의 형태는 map이다. 이 컨테이너는 <map>헤더에 정의되어 있다.

대부분의 경우에, map은 vector처럼 동작하지만 map의 인덱스는 정수일 필요가 없다.
string도 사용이 가능하고 다른 것들과 순서를 비교할 수 있는 것이라면 어떤 타입이라도 가능하다.

연관 컨테이너와 순차 컨테이너의 또 다른 중요한 차이점은, 연관 컨테이너들은 자체 순서를 갖기 때문에, 요소들의 순서를
직접적으로 변경시키는 작업은 할 수 없다는 것이다. 때문에 연관 컨테이너에 있어서는, 컨테이너의 내용을 변경하는 알고리즘들은
대부분 작동하지 않는다. 이러한 제약에 반해, 연관 컨테이너들은 많은 유용한 연산들을 제공한다.


# 연관 컨테이너를 이용한 단어 갯수 세기 예제

#include <iostream> 
#include <string> 
#include <map> 

usingnamespacestd; 

int main() 
{ 
string s; 
    map<string,int> counters; 

while(cin>>s) 
        ++counters[s]; 

for(map<string,int>::const_iterator iter=counters.begin();  
                            iter!=counters.end(); ++iter) 
    { 
cout<< iter->first<<"\t"<<iter->second<<endl; 
    } 

return0; 
}

# 단어가 어느 라인에 위치하는지를 보여주는 예제

cross_reference_table.cpp

#include <iostream> 
#include <string> 
#include <algorithm> 
#include <vector> 
#include <map> 


usingstd::cout; 
usingstd::cin; 
usingstd::endl; 

usingstd::string; 
usingstd::map; 
usingstd::vector; 
usingstd::find_if; 
usingstd::istream; 
usingstd::getline; 


bool space(char c) 
{ 
return isspace(c); 
} 

bool not_space(char c) 
{ 
return !isspace(c); 
} 

vector<string> split(conststring& str) 
{ 
typedefstring::const_iterator iter; 
    vector<string> ret; 
    iter i=str.begin(); 

while(i!=str.end()) 
    { 
// 첫 빈칸 무시
        i=find_if(i,str.end(),not_space); 

// 단어의 끝 검색
        iter j=find_if(i,str.end(),space); 

// i가 문자열의 끝이 아니라면
if(i!=str.end()) 
// 데이터 저장
            ret.push_back(string(i,j)); 

// 단어의 끝부터 다시 반복
        i=j;  
    } 

return ret; 
} 

map<string, vector<int> > xref(istream& in,vector<string> find_words(conststring&) = split) 
{ 
string line; 
int line_number = 0; 
    map<string, vector<int> > ret; 

// 한 라인을 읽어들임
while(getline(in, line)) 
    { 
// 라인 번호 증가
        ++line_number; 

// 입력받은 라인을 단어별로 쪼개서 저장
        vector<string> words = find_words(line); 

for(vector<string>::const_iterator it=words.begin(); it!=words.end(); ++it) 
        { 
// vector words의 한 요소를 가리키는 반복자를 map의 인덱스로 사용
// vector의 push_back멤버를 호출하여 현재의 라인 번호를 vector에 추가
            ret[*it].push_back(line_number); 
        } 
    } 
return ret; 
} 

int main() 
{ 
cout<<"input :: exit to ctrl+z"<<endl; 

// default로 split를 사용한 xref를 호출
    map<string, vector<int> > ret = xref(cin); 


for(map<string, vector<int> >::const_iterator it=ret.begin(); 
            it != ret.end(); ++it) 
    { 
cout<< it->first << " occurs on line(s) : "; 

// 하나이상의 라인 번호를 출력
        vector<int>::const_iterator line_it = it->second.begin(); 
cout<<*line_it; 

        ++line_it; 

// 만약 존재한다면 나머지 라인번호를 출력
while(line_it != it->second.end()) 
        { 
cout<<", "<<*line_it; 
            ++line_it; 
        } 

cout<<endl; // 개행
    } 
return0; 
}