12. deque: 끝단에서 빠른 자료구조

template<
    class Ty,
    class Allocator = std::allocator<Ty>
> class deque;

// 1.	기본 생성자
//		아무것도 할당되지 않은 상태로 초기화.
deque<int> q1;

// 2.	size를 전달 받는 생성자.
//		size이상의 공간을 할당하고 값을 기본값 으로 채움
deque<int> q2(5);						// 0 0 0 0 0

// 2-2.	size와 초기화 값 v을 받는 생성자
//		size이상의 공간을 할당하고,  v값으로 채움
deque<int> q2_2(5, 1);					// 1 1 1 1 1

// 3.	initializer_list
deque<int> q3 = { 1,2,3,4,5 };		// 1 2 3 4 5
deque<int> q3_2{ 1,2,3,4,5 };
deque<int> q3_3({ 1,2,3,4,5 });

// 4.	iterator
deque<int> q4(q3.begin(), q3.end());	// 1 2 3 4 5;

// 5.	copy
deque<int> q5(q4);					// 1 2 3 4 5

// 6. move
deque<int> q6(move(q5));			// 1 2 3 4 5

#include<iostream>
#include<deque>

using namespace std;

int main() {
	deque<int> q{ 1,2,3,4,5 };

	q.front() = 10;		// 1->10
	q.back();			// 5

	q.at(3) = 0;			// 4->0

	for (int i = 0; i < 5; i++) {
		cout << q[i] << endl;		// 10 2 3 0 5
	}
}

deque<int> q{ 1,2,3,4,5 };
q.size();			// 5
q.empty();			// false
q.max_size();		// 메모리의 총량

q.pop_back();		// 5를 제거한다.
q.shrink_to_fit();	// 5가 있던 요소의 메모리 블록을 해제한다.

deque<int> q{ 1,3,4 };
auto iter = q.begin() + 1;
iter = q.insert(iter, 2);		// 1 2 3 4
q.insert(iter+1, 100);			// 1 2 100 3 4 
q.emplace(q.end(), 5);			// 1 2 100 3 4 5

q.erase(q.begin()+2);			// 1 2 3 4 5

q.push_back(6);		// 1 2 3 4 5 6
q.push_front(0);	// 0 1 2 3 4 5 6		

q.pop_front();		// 1 2 3 4 5 6
q.pop_front();		// 2 3 4 5 6
q.pop_front();		// 3 4 5 6
q.pop_front();		// 4 5 6

q.pop_back();		// 4 5

deque<int>q{ 1,2,3,4,5,6,7 };
q.resize(3);		// 1 2 3
q.resize(5, 10);	// 1 2 3 10 10

q.clear();			// empty

#include<cassert>
#include<memory>

// int형 전용 Deque
// 연산은 대부분 msvc++ std::deque의 연산을 그대로 가져오려고 했음
// https://github.com/microsoft/STL/blob/main/stl/inc/deque
class Deque {
private:
	const int blockSize = 4;
	const int minimumMapSize = 8;

	int** map;
	int mapSize;
	int offset;
	int size;

	// map의 크기를 확장한다.
	void expandMap(int count) {
		int newSize = mapSize << count;
		int** newMap = constructMap(newSize);

		int blockOffset = offset / blockSize;
		
		// offset 부터 끝까지 복사
		const int copySize = mapSize-blockOffset;
		copyMap(newMap, blockOffset, map, blockOffset, copySize);
		if (blockOffset) {
			const int restSize = (mapSize - copySize);
			copyMap(newMap, blockOffset + copySize, map, 0, restSize);
		}

		if (map != nullptr) {
			delete[] map;
		}
		map = newMap;
		mapSize = newSize;
	}

	int** constructMap(int size) {
		int** m = new int* [size];
		memset(m, 0, size * sizeof(int*));
		return m;
	}

	void copyMap(int** newMap, int newOff, int** oldMap, int oldOff, int _size) {
		_size *= sizeof(int*);
		memcpy_s(newMap + newOff, _size, oldMap + oldOff, _size);
	}
	int getBlock(int i) {
		return (i / blockSize) & (mapSize - 1); // 나머지 연산 대신 & 사용
	}

	int* newBlock() {
		return new int[blockSize];
	}


public:
	Deque()
		: map(constructMap(minimumMapSize)),
		mapSize(minimumMapSize),
		offset(0), size(0) {}
	~Deque() {
		for (int i = 0; i < mapSize; i++) {
			if (map[i] != nullptr) {
				delete[] map[i];
			}
		}
		delete[] map;
	}

	void push_front(int v) {
		// 맵이 꽉 찼다면 확장한다.
		if ((offset + size) % blockSize == 0 && mapSize <= ((size + blockSize) / blockSize)) {
			expandMap(1);
		}

		// 새로운 offset을 구한다.
		offset &= mapSize * blockSize - 1;  // 나머지 연산 대신 & 사용
		int newOffset = offset != 0 ? offset : mapSize * blockSize;
		
		// offset 위치에 block이 없다면 생성한다.
		const auto block = getBlock(--newOffset);
		if (map[block] == nullptr) {
			map[block] = newBlock();
		}

		// 요소를 삽입한다.
		map[block][newOffset & (blockSize-1)] = v;
		offset = newOffset;
		++size;
	}

	void push_back(int v) {
		// 맵이 꽉 찼다면 확장한다.
		if ((offset + size) % blockSize == 0 && mapSize <= ((size + blockSize) / blockSize)) {
			expandMap(1);
		}

		// 새로운 offset을 구한다.
		offset &= mapSize * blockSize - 1;  // 나머지 연산 대신 & 사용
		int newOffset = offset + size;
		const int block = getBlock(newOffset);
		if (map[block] == nullptr) {
			map[block] = newBlock();
		}

		// 요소를 삽입한다.
		map[block][newOffset & (blockSize-1)] = v;
		++size;
	}

	int& operator[](int index) {
		assert((0 <= index && index < size));
		auto block = getBlock(index+offset);
		return map[block][index & (blockSize-1)];
	}

	int& front() { return (*this)[0]; }
	int& back() { return (*this)[size-1]; }
};