STL 구현

작성일 | In

vector

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#pragma once
#include <string>
namespace JH{
	typedef unsigned int size_t;
	template <typename T>
	class vector{
		private:
			T *arr;
			size_t ncapacity, nsize;
			void realloc(size_t); //O(n)
		public:
			//constructor
			vector(); //O(1)
			vector(size_t); //O(n)
			vector(size_t size, T value); //O(n)
			//destructor
			~vector(){ delete[] arr; } //O(1)
			//element eccess
			T at(size_t); //O(1)
			T operator [] (size_t); //O(1)
			T front(){ return at(0); } //O(1)
			T back(){ return at(nsize-1); } //O(1)
			//iterators
			T* begin(){ return arr; } //O(1)
			T* end(){ return arr+nsize(); } //O(1)
			//capacity
			bool empty(){ return (nsize==0); } //O(1)
			size_t size(){ return nsize; } //O(n)
			size_t capacity(){ return ncapacity; } //O(1)
			//modifiers
			void clear(); //O(1)
			void push_back(T); //amortized O(1)
			void pop_back(); //amortized O(1)
			void resize(size_t); //O(n)
			std::string iterType();
	};

	template <typename T>
	vector<T>::vector(){
		arr = nullptr;
		ncapacity = nsize = 0;
	}

	template <typename T>
	vector<T>::vector(size_t size){
		ncapacity = nsize = size;
		arr = new T[size];
		for(int i=0; i<size; i++) arr[i] = 0;
	}

	template <typename T>
	vector<T>::vector(size_t size, T value){
		ncapacity = nsize = size;
		arr = new T[size];
		for(int i=0; i<size; i++) arr[i] = value;
	}

	template <typename T>
	void vector<T>::realloc(size_t newSize){
		T *tmp = arr;
		arr = new T[newSize];
		for(int i=0; i<nsize && i<newSize; i++){
			arr[i] = tmp[i];
		}
		if(tmp) delete[] tmp;
		ncapacity = newSize;
	}

	template <typename T>
	T vector<T>::at(size_t idx){
		if(idx < nsize) return arr[idx];
		else return 0;
	}

	template <typename T>
	T vector<T>::operator [] (size_t idx){
		return at(idx);
	}

	template <typename T>
	void vector<T>::clear(){
		nsize = 0;
		realloc(0);
	}

	template <typename T>
	void vector<T>::push_back(T value){
		if(nsize == ncapacity){
			int newSize;
			if(!nsize) newSize = 16;
			else newSize *= 2;
			realloc(newSize);
		}
		arr[nsize++] = value;
	}

	template <typename T>
	void vector<T>::pop_back(){
		if(nsize == 0) return;
		nsize--;
		if(nsize < ncapacity/2){
			realloc(ncapacity/2);
		}
	}

	template <typename T>
	void vector<T>::resize(size_t size){
		realloc(size);
	}

	template <typename T>
	std::string vector<T>::iterType(){
		return "random access";
	}
}

linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
#pragma once
#include <iostream>
#include <string>
namespace JH{
	template <typename T>
	class node{
		public:
			T data;
			node<T>* prv;
			node<T>* nxt;
			node(){
				data = 0, prv = nxt = nullptr;
			}
			node(T value){
				data = value, prv = nxt = nullptr;
			}
	};

	template <typename T>
	class list{
		private:
			node<T> *nbegin;
			node<T> *nend;
			size_t nsize;
		public:
			//constructor
			list(){
				nbegin = new node<T>();
				nend = new node<T>();
				nbegin->nxt = nend;
				nend->prv = nbegin;
				nsize = 0;
			} //O(1)
			//destructor
			~list(); //O(n)
			//iterators
			node<T>* begin(){ return nbegin->nxt; } //O(1)
			node<T>* end(){ return nend; } //O(1)
			//capacity
			size_t size(){ return nsize; } //O(1)
			bool empty(){ return (nsize == 0); } //O(1)
			//element access
			T front(){ return nbegin->nxt->data; } //O(1)
			T back(){ return nend->prv->data; } //O(1)
			//modifiers
			void insert(node<T>*, T); //O(1)
			void insert(int, T); //O(n)
			void erase(node<T>*); //O(1)
			void erase(int); //O(n)
			void push_back(T); //O(1)
			void pop_back(); //O(1)
			void push_front(T); //O(1)
			void pop_front(); //O(1)
			void print(); //O(n)
			std::string iterType();
	};

	template <typename T>
	void list<T>::insert(node<T>* prv, T value){
		if(prv == nend){
			std::cout << "reject" << std::endl;
			return;
		}
		if(prv == nullptr){
			std::cout << "NullPointerException" << std::endl;
			return;
		}
		nsize++;
		node<T> *ptr = new node<T>(value);
		ptr->prv = prv;
		ptr->nxt = prv->nxt;
		prv->nxt->prv = ptr;
		prv->nxt = ptr;
	}

	template <typename T>
	void list<T>::insert(int pos, T value){
		node<T> *iter = nbegin;
		for(int i=0; i<pos; i++){
			iter = iter->nxt;
		}
		insert(iter, value);
	}

	template <typename T>
	void list<T>::erase(node<T>* ptr){
		if(ptr == nbegin){
			std::cout << "reject" << std::endl;
			return;
		}
		if(ptr == nullptr){
			std::cout << "NullPointerException" << std::endl;
			return;
		}
		nsize--;
		ptr->prv->nxt = ptr->nxt;
		ptr->nxt->prv = ptr->prv;
		delete ptr;
	}

	template <typename T>
	void list<T>::erase(int pos){
		node<T> *iter = nbegin;
		for(int i=0; i<=pos; i++){
			iter = iter->nxt;
		}
		erase(iter);
	}

	template <typename T>
	void list<T>::push_back(T value){
		insert(nend->prv, value);
	}

	template <typename T>
	void list<T>::pop_back(){
		erase(nend->prv);
	}

	template <typename T>
	void list<T>::push_front(T value){
		insert(nbegin, value);
	}

	template <typename T>
	void list<T>::pop_front(){
		erase(nbegin->nxt);
	}

	template <typename T>
	list<T>::~list(){
		auto now = nbegin;
		auto nxt = nbegin->nxt;
		while(now != nend){
			if(now) delete now;
			now = nxt;
			if(now != nend) nxt = now->nxt;
		}
	}

	template <typename T>
	void list<T>::print(){
		auto iter = begin();
		for(; iter != end(); iter = iter->nxt) std::cout << iter->data << std::ends;
	}

	template <typename T>
	std::string list<T>::iterType(){
		return "bidirectional";
	}
}

stack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "vector.h"
#include "list.h"
#pragma once

namespace JH{
	template <typename T>
	class stack{
		private:
			vector<T> arr;
		public:
			bool empty(){ return arr.empty(); } //O(1)
			size_t size(){ return arr.size(); } //O(1)
			T top(){ return arr.back(); } //O(1)
			void push(T value){ arr.push_back(value); } //amortized O(1)
			void pop(){ arr.pop_back(); } //amortized O(1)
	};

	template <typename T>
	class stack_list{
		private:
			list<T> arr;
		public:
			bool empty(){ return arr.empty(); } //O(1)
			size_t size(){ return arr.size(); } //O(1)
			T top(){ return arr.back(); } //O(1)
			void push(T value){ arr.push_back(value); } //amortized O(1)
			void pop(){ arr.pop_back(); } //amortized O(1)
	};
}

queue

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#pragma once
#include "list.h"
namespace JH{
	template <typename T>
	class queue{
		private:
			list<T> arr;
		public:
			bool empty(){ return arr.empty(); } //O(1)
			size_t size(){ return arr.size(); } //O(1)
			T back(){ return arr.back(); } //O(1)
			T front(){ return arr.front(); } //O(1)
			void push(T value){ arr.push_back(value); } //amortized O(1)
			void pop(){ arr.pop_front(); } //amortized O(1)
	};
}