수정1
전에 올렸던 소스에서 Double Free Bug가 일어나서 급하게 수정했습니다.
추가한건 소멸자함수, 수정한 부분은 operator=입니다.
=============================================================================
수정2
수정하기 전의 소스에서 begin이나 rend함수를 통해 arr에 접근이 가능해져서 아래와 같은 소스로
데이터 삭제가 가능합니다.
delete [](arr.begin());
이를 방지하기위해
vector_base로 캡슐화 시켰고, 기존의 T*리턴하는 함수들을 모두 iterator로 변경하였습니다.
또, 현재 다른 STL함수들과 호환성을 위해 수정중입니다.
#ifndef __CLASS_VECTOR__ #define __CLASS_VECTOR__ #include <memory> #include <cstring> // 메모리 재할당을 위한 클래스. template<typename T> class vector_base{ public: T *rebind(T *_arr, unsigned int size){ int i; T *karr = new T[size]; for(i = 0; i < (size - 1)/2; i++) karr[i] = _arr[i]; delete []_arr; _arr = nullptr; return karr; } }; // 실질적으로 동작하는 vector 클래스. // T 자료형을 기준으로 잡고 iterator구현. template<typename T> class vector{ typedef T* _iterator; typedef T* _reverse_iterator; typedef const T* _const_iterator; typedef const T* _const_reverse_iterator; typedef unsigned int size_type; typedef T& reference; private: T *arr = nullptr; // 데이터 저장영역. vector_base<T> v_base; // capacity의 크기보다 length가 커지면 재할당을 하기위해 have-a구조로 만들어놓음. size_type len = 0; // 자료의 개수 size_type capacity = 0; // 할당되는 공간 수 public: vector(){ } explicit vector(size_type capacity_) : capacity(capacity_) { } explicit vector(size_type length, size_type capacity_) : len(length), capacity(capacity_) { } explicit vector(T *arr_, size_type capacity_) : arr(arr_), capacity(capacity_) { } explicit vector(T *arr_, size_type length, size_type capacity_) : arr(arr_), len(length), capacity(capacity_) { } ~vector(){ if(arr != nullptr) delete []arr; } void push_back(T data); void pop_back(); _iterator begin(){ return arr; } _const_iterator begin() const { return arr; } _iterator end(){ return arr + len; } _const_iterator end() const { return (arr + len); } _reverse_iterator rbegin(){ return (arr + len - 1); } _reverse_iterator rend(){ return (arr - 1); } reference front(){ return arr[0]; } reference back(){ return arr[len - 1]; } T at(unsigned int idx){ if(arr != nullptr) return arr[idx]; } size_type size(){ return len; } size_type length(){ return size(); } size_type alloc_size(){ return capacity; } bool empty() const { if(arr == nullptr){ return true; } else{ return false; } } void clear(){ len = 0, capacity = 0; } vector<T> *operator=(vector<T> &t); bool operator!=(vector<T> &t); T operator[](const unsigned int idx) const; T operator[](unsigned int idx); // iterator를 가지는 vector클래스이므로 have-a구조로 표현. public: class iterator{ private: T *p; public: void operator=(T *v_s); bool operator==(T *v_s) { return p == v_s ? true : false; } bool operator!=(T *v_s); T operator*() { return *p; } _iterator operator++(){ return p++; } _iterator operator++(int){ return p++; } _iterator operator--(){ return p--; } _iterator operator--(int){ return p--; } _iterator operator+=(int s){ return p += s; } _iterator operator-=(int s){ return p -= s; } }; class reverse_iterator{ private: T *p; public: void operator=(T*v_s); bool operator!=(T *v_s); bool operator==(T *v_s) { return p == v_s ? true : false; } T operator*() { return *p; } _reverse_iterator operator++() { return p--; } _reverse_iterator operator++(int) { return p--; } _reverse_iterator operator--() { return p++; } _reverse_iterator operator--(int){ return p++; } _reverse_iterator operator+=(int s){ return p -= s; } _reverse_iterator operator-=(int s){ return p += s; } }; }; template<typename T> void vector<T>::push_back(T data){ if(capacity <= len){ capacity = size() * 2 + 1; arr = v_base.rebind(arr, size() * 2 + 1); } arr[len] = data; len++; } template<typename T> void vector<T>::pop_back(){ len--; } template<typename T> vector<T> *vector<T>::operator=(vector<T> &t){ delete []arr; len = 0, capacity = 0; arr = new T[t.capacity]; std::cout << arr << std::endl; int i; for(i = 0; i < t.alloc_size(); i++) arr[i] = t[i]; len = t.len; capacity = t.alloc_size(); return this; } template<typename T> bool vector<T>::operator!=(vector<T> &t){ if(len != t.size()) return true; int i = 0; while(i <= len - 1 && i <= t.size() - 1){ if(arr[i] != t.arr[i]) return true; i++; } return false; } template<typename T> T vector<T>::operator[](const unsigned int idx) const{ if(arr != nullptr && idx < size()) return arr[idx]; return arr[0]; } template<typename T> T vector<T>::operator[](unsigned int idx){ if(arr != nullptr && idx < size()) return arr[idx]; return arr[0]; } template<typename T> void vector<T>::iterator::operator=(T *v_s){ p = v_s; } template<typename T> bool vector<T>::iterator::operator!=(T *v_s){ if(p != v_s) return true; else return false; } template<typename T> void vector<T>::reverse_iterator::operator=(T *v_s){ p = v_s; } template<typename T> bool vector<T>::reverse_iterator::operator!=(T *v_s){ if(p != v_s) return true; else return false; } #endif
#ifndef __VECTOR__ #define __VECTOR__ template<typename T> class vector; // 메모리 재할당을 위한 구조체. template<typename T> struct allocator{ public: T *rebind(T *_arr, unsigned int size){ int i; T *karr = new T[size]; for(i = 0; i < (size - 1)/2; i++) karr[i] = _arr[i]; if(_arr != nullptr) delete []_arr; _arr = nullptr; return karr; } }; // 데이터가 저장될 class // opeartor를 통해 vector에서 구현이 쉽도록 함. template<typename T> class vector_base{ private: T data; public: friend class vector<T>; vector_base<T> &operator=(T t){ data = t; return *this; } bool operator==(vector_base<T> t){ return data == t.data ? true : false; } bool operator!=(vector_base<T> t){ return data != t.data ? true : false; } bool operator>(vector_base<T> t){ return data > t.data ? true : false; } bool operator>=(vector_base<T> t){ return data >= t.data ? true : false; } bool operator<(vector_base<T> t){ return data < t.data ? true : false; } bool operator<=(vector_base<T> t){ return data <= t.data ? true : false; } vector_base<T> operator++(){ vector_base<T> k; k.data = this->data++; return k; } vector_base<T> operator--(){ vector_base<T> k; k.data = this->data--; return k; } template<typename U> friend std::ostream &operator<<(std::ostream &os, vector_base<U> &v_base); }; template<typename T> std::ostream &operator<<(std::ostream &os, vector_base<T> &v_base){ os << v_base.data; return os; } // vector 클래스 // vector_base 자료형을 기준으로 잡고 iterator구현. template<typename T> class vector{ typedef vector_base<T>* _iterator; typedef vector_base<T>* _reverse_iterator; typedef const vector_base<T>* _const_iterator; typedef const vector_base<T>* _const_reverse_iterator; typedef unsigned int size_type; typedef T* pointer; typedef T& reference; typedef T value_type; // iterator를 가지는 vector클래스이므로 have-a구조로 표현. public: class iterator{ private: _iterator p = nullptr; // ptr를 움직이기 위해 필요한 멤버변수 public: iterator() { } iterator(vector_base<T> *v_s) : p(v_s) { } void operator=(iterator v_s){ p = v_s.p; } bool operator!=(iterator v_s){ return p != v_s.p; } T operator*() { return p->data; } iterator operator++(){ return p++; } iterator operator++(int){ return p++; } iterator operator--(){ return p--; } iterator operator--(int){ return p--; } iterator operator+=(int s){ return p += s; } iterator operator-=(int s){ return p -= s; } bool operator>(const iterator iter)const { return p->data > *iter; } bool operator<(const iterator iter)const { return p->data < *iter; } T operator-(const iterator iter) { return p->data - *iter; } }; class reverse_iterator{ private: _iterator p = nullptr; public: reverse_iterator() { } reverse_iterator(vector_base<T> *v_s) : p(v_s) { } void operator=(reverse_iterator v_s){ p = v_s.p; } bool operator!=(reverse_iterator v_s){ return p != v_s.p; } T operator*() { return p->data; } reverse_iterator operator++() { return p--; } reverse_iterator operator++(int) { return p--; } reverse_iterator operator--() { return p++; } reverse_iterator operator--(int){ return p++; } reverse_iterator operator+=(int s){ return p -= s; } reverse_iterator operator-=(int s){ return p += s; } bool operator>(const reverse_iterator iter) const { return p->data > *iter; } bool operator<(const reverse_iterator iter)const { return p->data < *iter; } T operator-(const reverse_iterator iter) { return p->data - *iter; } }; private: _iterator v_base = nullptr; // capacity의 크기보다 length가 커지면 재할당을 하기위해 have-a구조로 만들어놓음. allocator< vector_base<T> > alloc; // my allocator size_type len = 0; // 자료의 개수 pop_back할 시 데이터는 남겨놓고 length만 줄이면 접근 불가능. size_type capacity = 0; // 할당되는 공간 수 (capacity = len * 2 + 1) public: explicit vector(){ } explicit vector(size_type capacity_) : capacity(capacity_) { } explicit vector(size_type length, size_type capacity_) : len(length), capacity(capacity_) { } explicit vector(T *arr_, size_type length, size_type capacity_) : len(length), capacity(capacity_) { int i; for(i = 0; i < length; i++) push_back(arr_[i]); } ~vector(){ if(v_base != nullptr) delete []v_base; } void push_back(T data); void pop_back(); iterator begin(){ return v_base; } const iterator begin() const { return v_base; } iterator end(){ return v_base + len; } const iterator end() const { return v_base + len; } reverse_iterator rbegin(){ return v_base + len - 1; } reverse_iterator rend(){ return v_base - 1; } reference front(){ return v_base[0].data; } reference back(){ return v_base[len - 1].data; } T &at(unsigned int idx){ if(v_base != nullptr) return v_base[idx].data; } size_type size() const { return len; } size_type length() const { return size(); } size_type alloc_size() const { return capacity; } bool empty() const { if(v_base == nullptr){ return true; } else{ return false; } } void clear(){ len = 0, capacity = 0; } vector<T> *operator=(vector<T> &t); vector_base<T> &operator=(T t); bool operator!=(vector<T> &t); vector_base<T> &operator[](const unsigned int idx) const; }; template<typename T> void vector<T>::push_back(T data){ if(capacity <= len){ capacity = size() * 2 + 1; v_base = alloc.rebind(v_base, capacity); } v_base[len].data = data; len++; } template<typename T> void vector<T>::pop_back(){ len--; } template<typename T> vector<T> *vector<T>::operator=(vector<T> &t){ delete []v_base; len = 0, capacity = 0; v_base = new vector_base<T>[t.capacity]; int i; for(i = 0; i < t.alloc_size(); i++) v_base[i].data = t.v_base[i].data; len = t.len; capacity = t.alloc_size(); return this; } template<typename T> vector_base<T> &vector<T>::operator=(T t){ v_base->data = t; return v_base; } template<typename T> bool vector<T>::operator!=(vector<T> &t){ if(len != t.size()) return true; int i = 0; while(i <= len - 1 && i <= t.size() - 1){ if(v_base[i].data != t.v_base[i].data) return true; i++; } return false; } template<typename T> vector_base<T> &vector<T>::operator[](const unsigned int idx) const { if(v_base != nullptr && idx < size()) return v_base[idx]; } #endif
'자료' 카테고리의 다른 글
| [Tip] 해커스쿨 자료 얻기. (0) | 2016.03.25 |
|---|---|
| ARM Assembly 명령어 정리(펌) (0) | 2016.03.17 |
| Heap 기반 free() & malloc() Exploit 작성하기 (0) | 2015.12.26 |
| 비초기화 정적 변수의 오버플로우에 대한 Exploit의 제작기법(1) (0) | 2015.12.26 |
| [자료구조] Binary Search Tree(BST) (0) | 2015.12.12 |
KuroNeko_
KuroNeko