1. map vs vector


Trie가 메모리를 많이 잡아먹기 때문에

메모리 초과를 내지 않기 위해 map을 쓰는 사람이 많은데

사실 map보단 vector가 Trie 구현에 알맞은 컨테이너이다.


만약 키 값이 알파벳 소문자라면

평균적으로 L - log_26(N)번의 탐색이

한번에 처리된다고 기대할 수 있다.


결론적으로 탐색의 평균 시간 복잡도는 O(1)이다.


N = 값의 개수

L = 값의 길이


메모리 사용량을 비교해보면

vector : 32 + T * size

map    : 24 + (3 pointer + bool + T) * size

이기 때문에


값이 들어있을 경우,

Trie의 경우 말단 노드를 제외하면

vector의 메모리 사용량이 더 적다



2. pointer


사용되는 메모리를 줄이기 위해

동적으로 구현을 할 때에도 포인터를 쓰는 경우가 많다


정적 구현에서 포인터 배열을 쓰는 것 때문에

이런 방식으로 하는 것 같은데


map, vector를 사용한다면

컨테이너 자체가 포인터를 사용하기 때문에

명시적으로 할당해 줄 필요가 없다.





아래는 동일한 문제에서 실행한 결과이다


map


vector


구현은 아래와 같다


struct Trie

{

vector<pair<char, Trie>> branch;

bool exist = false;


Trie* find(char c)

{

for (auto& [k, v] : branch)

if (c == k)

return &v;

return nullptr;

}


template< class I >

void insert(I first, I last)

{

Trie* trie = this;

for (; first != last; ++first)

{

Trie* found = trie->find(*first);

if (found)

trie = found;

else

{

trie->branch.resize(trie->branch.size() + 1, { *first, {} });

trie = &trie->branch.back().second;

}

}

trie->exist = true;

}

};