STL엔 두 개의 map이 있다. 하나는 std::map이고, 다른 하나는 std::unordered_map이다. 이들의 용도는 다음과 같이 간단히 정리할 수 있다. 킷값에 따라 정렬해주는 map이 필요하다면 std::map을 사용하고, 빠른 검색이 필요하다면 std::unordered_map을 사용한다. 우린 키를 정렬할 필요는 없으므로, std::unordered_map을 이용하기로 하자.
이제 2차원 인덱스를 표현할 자료형을 결정해야 한다. C++의 내장 배열을 사용하자니 번거롭고, std::vector를 사용하자니 너무 무겁다. 2011년 8월 12일에 제정된 새로운 C++ 표준에선 std::array를 정의하고 있다. 이건, 고정된 크기의 std::vector라고 생각하면 되는데, std::vector보다 가볍고 C++ 내장 배열보다 편리하다. 행렬의 인덱스는 길이가 2로 고정되므로 std::array는 인덱스의 자료형에 딱 맞는 컨테이너이다.
이제 구현을 해보자. 먼저, 필요한 헤더를 불러온다.
// smat.cc #include <array> #include <cstdlib> #include <iostream> #include <numeric> #include <unordered_map>cstdlib 헤더는 main 함수의 반환 값으로 사용할 EXIT_SUCCESS 매크로를 정의가 들어 있고, numeric 헤더는 해시 값 생성에 사용할 accumulate 함수의 선언이 들어 있다.
다음으로 할 일은 함수자(functor)를 만드는 것이다. std::unordered_map은 해시표를 사용하는 데, 키로부터 해시 값을 계산해서 해시표를 생성해야 한다. 기본 자료형에 대해서는 해시 값을 생성하는 함수자가 이미 선언되어 있지만, 그 외의 자료형에 대해선 우리가 직접 만들어줘야 한다. std::unary_function을 이용해서 간단하게 인덱스의 두 값을 더하는 해시 함수자를 만든다.
namespace std
{
template <>
struct hash<array<int, 2> >: public unary_function<array<int, 2>, size_t>
{
size_t operator()(const array<int, 2>& idx) const
{
return accumulate(idx.begin(), idx.end(), 0);
}
};
}
이제 희소행렬 자체를 구현할 클래스를 선언한다. 행렬 연산을 구현하는 여러 함수도 구현해야겠지만, 여기선 행렬 원소의 읽기와 쓰기에 관련된 연산자 정도만 구현해보자.template <typename T> class SparseMatrix
{
public:
SparseMatrix(int i, int j): i_size(i), j_size(j) {}
T& operator()(int i, int j)
{
std::array<int, 2> idx;
idx[0] = i;
idx[1] = j;
return mat[idx];
}
T operator()(int i, int j) const
{
std::array<int, 2> idx;
idx[0] = i;
idx[1] = j;
typename std::unordered_map<std::array<int, 2>, T>::const_iterator tmp;
tmp = mat.find(idx);
if (tmp == mat.end())
return T();
else
return tmp->second;
}
private:
std::unordered_map<std::array<int, 2>, T> mat;
std::size_t i_size, j_size;
};
눈여겨볼 점은 행렬의 원소를 설정할 때 사용할 operator()와 원소를 조회할 때 사용할 operator() const를 모두 선언해야 한다는 것이다. operator()만 선언한다면, 행렬의 원소를 조회할 때마다 조회하는 인덱스에 해당하는 항목을 map에 만들게 된다. 예를 들어,SparseMatrix<double> sm(3, 3);
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
std::cout << sm(i, j) << " ";
}
std::cout << std::endl;
}
처럼 모든 원소를 조회하기만 해도 내부 저장 장소인 mat에 모든 원소에 해당하는 항목이 만들어져 메모리를 낭비하게 된다.실제로 원소를 설정하고 조회하는 방법은 아래와 같다.
using namespace std;
int main(int argc, char* argv[])
{
SparseMatrix<double> sm(3, 3);
sm(1, 2) = 1;
sm(2, 0) = 2;
const SparseMatrix<double>& sm_ref = sm;
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
cout << sm_ref(i, j) << " ";
}
cout << endl;
}
return EXIT_SUCCESS;
}
operator() const를 호출하려면, 상수 레퍼런스나 상수 포인터를 이용해서 SpareMatrix에 접근해야 한다. 뭐, 대충 이렇다. 이 코드는 C++0x 표준인 std::array와 std::unordered_map을 사용하는데, 이 기능이 시험적으로 구현된 거라서 이용하면 컴파일 할 때 -std=c++0x 옵션을 줘야 한다.$ g++ -Wall -g -pedantic -std=c++0x -o smat smat.cc실행해보면, 잘 작동하는 것을 확인할 수 있다.
$ ./smat 0 0 0 0 0 1 2 0 0 $mat의 크기를 검사해 보면, 단 두 개의 항목만 저장하고 있는 것을 확인할 수 있다. 간단한 희소행렬 완성!
