[C++/Game Server] STL Allocator

STL Allocator

• vector나 map 같은 STL 컨테이너들은 내부적으로 new, delete를 기본적으로 사용하여 메모리 할당을 하고 있음
  • new, delete는 유동적이기 때문에, 메모리 할당 오류를 제대로 잡아내지 못할 수 있음
  • STL 컨테이너들의 메모리 할당 로직 중간에 개입하고 싶을 수 있음

vector의 2번째 인자로 allocator를 받고있는 것을 확인할 수 있음

• STL Allocator를 만들어 Allocator를 대체하는 메모리 체크 버전 STL 컨테이너를 따로 만들어서 메모리 할당 로직 중간에 개입하거나, 오류를 탐색할 때 사용할 수 있음

vector<int32, BaseAllocator> v;

• 이렇게 넣으면 될 것 같지만 STL 컨테이너마다 내부에서 기본적으로 요구하는 함수들이 BaseAllocator에 모두 구현되어 있지 않을 확률이 큼
• vector 뿐만 아니라 stack, queue 등 다른 컨테이너들도 자신들만의 매개변수가 다를 것임

 

Allocator.h

/*-------------------------
	STL Allocator
-------------------------*/

template <typename T>
class StlAllocator {
public:
	using value_type = T;

	StlAllocator() {}

	template <typename Other>
	StlAllocator(const StlAllocator<Other>&) {}
	// 오류 해결용으로 작성

	T* allocate(size_t count) {
		const int32 size = static_cast<int32>(count * sizeof(T));
		return static_cast<T*>(xxalloc(size));
	}

	void deallocate(T* ptr, size_t count) { xxrelease(ptr); }
};

• allocate(size_t n): 단순히 n * sizeof(T) 만큼의 메모리를 빌려오는 역할로, 여기서 내부적으로 xxalloc을 호출
• deallocate(T* ptr, size_t n): 빌렸던 메모리를 다시 xxrelease를 통해 돌려줌
• 다음과 같이 StlAllocator의 기본틀을 잡아놓고, 이전에 만들었던 Allocator(xxalloc, xxrelease)로 메모리 할당을 대신해 줌
  • CoreMacro.h에 설정된 모드별 Allocator(StompAllocator or BaseAllocator)로 메모리 할당 로직이 돌아감
• xnew와 달리 여기서 객체의 생성자/소멸자를 직접 호출하지는 않음
  • 그건 STL 컨테이너가 내부적으로 알아서 할 일이고, 이 할당자는 오직 메모리 덩어리만 가져다주는 역할에 충실

 

Container.h (rebind)

template <typename T>
using Vector = vector<T, StlAllocator<T>>;

template <typename T>
using List = list<T, StlAllocator<T>>;

template <typename Key, typename T, typename Pred = less<Key>>
using Map = map<Key, T, Pred, StlAllocator<pair<const Key, T>>>;

template <typename Key, typename Pred = less<Key>>
using Set = set<Key, Pred, StlAllocator<Key>>;

template <typename T>
using Deque = deque<T, StlAllocator<T>>;

template <typename T, typename Container = Deque<T>>
using Stack = stack<T, Container>;

template <typename T, typename Container = Deque<T>>
using Queue = queue<T, Container>;

template <typename T, typename Container = vector<T>, typename Pred = less<T>>
using PriorityQueue = priority_queue<T, Container, Pred>;

using String = basic_string<char, char_traits<char>, StlAllocator<char>>;
using Wstring = basic_string<wchar_t, char_traits<wchar_t>, StlAllocator<wchar_t>>;

template <typename Key, typename T, typename Hasher = hash<Key>, typename KeyEq = equal_to<Key>>
using HashMap = unordered_map<Key, T, Hasher, KeyEq, StlAllocator<pair<const Key, T>>>;

template <typename Key, typename Hasher = hash<Key>, typename Keyeq = equal_to<Key>>
using HashSet = unordered_set<Key, Hasher, Keyeq, StlAllocator<Key>>;

• 다음과 같이 STL 컨테이너들이 필요로 하는 매개변수를 맞춰주고, allocator를 STL Allocator로 설정하여 각 STL 컨테이너가 메모리 할당을 할 때, 사용자가 설정한 Allocator로 STL 컨테이너들의 메모리 할당 로직을 수정할 수 있음

PriorityQueue: 같은 Pred = less<T>인데 오름차순, 내림차순이 다른 이유

• std::map과 std::set은 내부적으로 이진 탐색 트리(정확히는 Red-Black Tree) 구조를 사용
  • std::less 적용 시: 작은 값이 왼쪽, 큰 값이 오른쪽에 배치
• PriorityQueue도 내부적으로 less를 써서 비교하는 것은 같지만, 우선순위(누구를 제일 위에 둘 것인가)의 개념이 추가되기 때문에 정렬 방식이 다름
  • Map, Set: 전체 데이터를 순서대로 줄 세우기 → less면 작은 게 앞으로(오름차순)
  • PriorityQueue: 가장 우선순위가 높은 놈 하나만 맨 위에 올리기 → C++ 표준은 값이 클수록 우선순위가 높다고 정의하므로, less를 쓰면 가장 큰 값이 top()에 오게 되어, 꺼낼 때 내림차순으로 보이게 됨

컨테이너	내부 구조	정렬/출력 형태	특징
Set / Map	Red-Black Tree	오름차순 (1, 2, 3...)	begin()부터 순회하면 작은 값부터 나옴
Vector / List	선형 구조	정렬 안 됨	넣은 순서대로 유지됨
PriorityQueue	Heap	내림차순 (10, 9, 8...)	pop() 할 때 큰 값부터 나옴 (Max Heap)