AcceleratedC++/Chapter10 | AcceleratedC++/Chapter12 |
1. Chapter 11 Defining abstract data types ¶
3 Student_info 복, 대, 멸 떤 는 명 .
를 는 , 복, 대, 멸 .
는 STL vector 만들 보면 료 만는 방 .
를 는 , 복, 대, 멸 .
는 STL vector 만들 보면 료 만는 방 .
1.1. 11.1 The Vec class ¶
를 는 를 . 는 를 램 보는 .
~cpp //vector vector<Student_info> vs; vector<double> v(100); //vector 는 르 는. vector<Student_info>::const_iterator b, e; vector<Student_info>::size_type i = 0; //vector 를 보 , size 및 index 를 for(i = 0; i != vs.size(); ++1) cout<<vs[i].name(); //번 마막 대 복 리 b=vs.begin(); e=vs.end();들 vector clone Vec 를 메들.
1.2.1. 11.2.1 메모리 ¶
는 떤 방 Vec를 를 는 .
는 template class를 .
릿 뿐만 는 능.
size는 begin, end 를 를 는 능므 는 , 마막 를 를 는 .
따 떤 Vec 는는 부 instiation 는 .
는 template class를 .
릿 뿐만 는 능.
~cpp template <class T> class Vec { public: //interface private: //implementation };begin, end, size 를 므 러 , 마막 를 , 들 를 .
size는 begin, end 를 를 는 능므 는 , 마막 를 를 는 .
~cpp template <class T> class Vec { public: //interface private: T* data; // 번 T* limit; // 마막 를 };릿 뿐며, type parameter 따 를 .
따 떤 Vec 는는 부 instiation 는 .
1.2.2. 11.2.2 (Constructor) ¶
명 2를 능 문 2는 .
본 면 2 문 리.
explicit
를 받는 . 대 능 문 명 만 는 방. (12.2 논)
~cpp Vec<Student_info> vs; // default constructor Vec<Student_info> vs(100); // Vec 를 는 // vector 는 를 받는 .
~cpp template <class T> class Vec { public: Vec() { create(); } // 느 부 문 를 만들 . explicit Vec(size_type n, const T& val = T()) { create(n, val); } private: T* data; // 번 T* limit; // 마막 를 };2번 는 메 T 를 .
본 면 2 문 리.
explicit
를 받는 . 대 능 문 명 만 는 방. (12.2 논)
~cpp Vec<int> vi(100); // Working. int 를 명 Vec<int> vi = 100; // not working. 묵 Vec를 vi 복. refer 11.3.3
1.2.3. 11.2.3 ¶
const_iterator, iterator를 .
back_inserter(T)를 동 를 변 value_type, push_back . (value_type 떤 를 )
list 복를 는 면 ++ 노 노를 리는 를 딩, 는 배 를 리므 를 리는 만 리는 복를 는 능.
value_type T 는 . 배 를 는 size_type cstddef 는 size_t 는 .
back_inserter(T)를 동 를 변 value_type, push_back . (value_type 떤 를 )
list 복를 는 면 ++ 노 노를 리는 를 딩, 는 배 를 리므 를 리는 만 리는 복를 는 능.
value_type T 는 . 배 를 는 size_type cstddef 는 size_t 는 .
~cpp template <class T> class Vec { public: typedef T* iterator; typedef const T* const_iterator; typedef size_t size_type; typedef T value_type; Vec() { create(); } // 느 부 문 를 만들 . explicit Vect(size_type n, const T& val = T()) { create(n, val); } private: iterator data; // 번 iterator limit; // 마막 를 };typedef를 , 멤 데 맞 변.
1.2.4. 11.2.4 덱 및 size ¶
~cpp for (i = 0; i != vs.size(); ++) cout<<vs[i].name();능 는 operator[], size() 를 .
딩(operator overload)
명 operatorop .
~cpp []
는 ~cpp operator[]
낼 .만 멤 면(friend ) 는 번 , 는 번 낼 .
만 멤 면 는 를 는 만 .
~cpp []
size_type , 리 value_type 런를 .~cpp template <class T> class Vec { public: typedef T* iterator; typedef const T* const_iterator; typedef size_t size_type; typedef T value_type; Vec() { create(); } // 느 부 문 를 만들 . explicit Vect(size_type n, const T& val = T()) { create(n, val); } size_type size() const { return limit - data; } T& operator[](size_type i) { return data[i]; } const T& operator[](size_type i) const { return data[i]; }; // 런를 는 는 능 문. private: iterator data; // 번 iterator limit; // 마막 를 };operator[] 2 딩 는
모 멤는 묵 를 더 받는. 를 데, const const 2 는 능 문 parameter specification 동만 딩 능.
1.2.5. 11.2.5 복를 리는 ¶
~cpp template <class T> class Vec { public: typedef T* iterator; typedef const T* const_iterator; typedef size_t size_type; typedef T value_type; Vec() { create(); } // 느 부 문 를 만들 . explicit Vect(size_type n, const T& val = T()) { create(n, val); } size_type size() const { return limit - data; } T& operator[](size_type i) { return data[i]; } const T& operator[](size_type i) const { return data[i]; }; // 런를 는 는 능 문. //복들 리는 들 iterator begin() { return data; } const_iterator begin() const { return data; } iterator end() { return limit; } const_iterator end() const { return limit; } private: iterator data; // 번 iterator limit; // 마막 를 };
1.3.1. 11.3.1 Copy ¶
implicit copy constructor
explicit copy constructor
복 는 는 를 미.
를 복는 , 복본 만는 미를 문 매변를 런 는 .
보 디 복 는 멤 변들 복만 됩. 만 멤 변 면 문 .
멸면 를 복 받 문.
따 받 대 는 복 런 문 는.
른 마 create() 를 복를 만.
~cpp vector<int> vi; double d; d = median (vi); // copy constructor work string line; vector<string> words = split(words); // copy constructor work
explicit copy constructor
~cpp vector<Student_info> vs; vector<Student_info> v2 = vs; // copy constructor work (from vs to v2)복
복 는 는 를 미.
를 복는 , 복본 만는 미를 문 매변를 런 는 .
~cpp template <class T> class Vec { public: Vec(const Vec& v); // copy constructor // };
보 디 복 는 멤 변들 복만 됩. 만 멤 변 면 문 .
멸면 를 복 받 문.
따 받 대 는 복 런 문 는.
른 마 create() 를 복를 만.
~cpp template <class T> class Vec { public: Vec(const Vec& v) { create(v.begin(), v.end() ); } // copy constructor // };
1.3.2. 11.3.2 대(Assignment) ¶
대 (assignment operator)
operator=() 러 대 const 런를 는 를 대 .
리 C++ 본 대 를 (left-hand side)대 런를 .
대 는 복 리 대. 복 는 만들 문 대 만, 대 는 데 는 대 문 복 .
대 (self-assignment) .
operator=() 러 대 const 런를 는 를 대 .
리 C++ 본 대 를 (left-hand side)대 런를 .
~cpp template <class T> class Vec { public: Vec& operator=(const Vec&); // copy constructor // };대 딩
대 는 복 리 대. 복 는 만들 문 대 만, 대 는 데 는 대 문 복 .
대 (self-assignment) .
~cpp template<class T> Vec<T>& Vec<T>::operator=(const Vec& rhs) { // self-assignment check if (&rhs != this) { //lhs memory deallocation uncreate(); create(rhs.begin(), rhs.end()); { return *this; }
- 더 리 Vec&
- this
this는 멤 . this는 멤를 를 리.
만 this 대 를 는 른 를 뒤 대 므 문 .
- *this 리
대 리 는 . 를 리면 scope를 벗 문 바른 동 보 못.
1.3.3. 11.3.3 대 ¶
C++ = , 복 동 문 복 , 대 .
= 면 복 , 면 대 .
2
리 복 , 대
= 면 복 , 면 대 .
* 변 * , 매변 * 리 * |
2
~cpp string url_ch = "~;/?:@=&$-_.+!*'(),"; string spaces(url_ch.size(), ' ');
리 복 , 대
~cpp vector<string> split(const string&); vector<string> v; v = split(line); // 료 를 복 // 를 대 v 대
1.3.4. 11.3.4 멸(Destructor) ¶
멸(destructor)
동 는 delete 는 메모리 는데, 멤변 동 변 면 메모리 .
멸 는 마 며 명 동 명 는 대 ~를 .
동 는 delete 는 메모리 는데, 멤변 동 변 면 메모리 .
멸 는 마 며 명 동 명 는 대 ~를 .
~cpp template <class T> class Vec { public: ~Vec() { uncreate; } // copy constructor // };
1.3.5. 11.3.5 디 (Default operation) ¶
, 멸, 복 , 대를 는 러 방 런 본 만.
멤 (has-a) 는 런 디 며, 본(primitive type) 는 방 런 들 . 러 른 며, 리 는.
default constructor 를 는 멤들 디 를 만 동 보 .
는 명 디 를 만는 .
멤 (has-a) 는 런 디 며, 본(primitive type) 는 방 런 들 . 러 른 며, 리 는.
default constructor 를 는 멤들 디 를 만 동 보 .
는 명 디 를 만는 .
1.3.6. 11.3.6 (rule of three) ¶
복 미 | 본 복본 데 동. |
멸 미 | 는 memory leak |
대 모 복본 대 동면 들 |
T::T() T::~T() T::T(const T&) T::operator=(const T&) |
Rule of three : 복 , 멸, 대 밀 를 는 는 말.
1.4. 11.4 Dynamic Vecs ¶
push_back 방
push_back 배 를 는데 는 보 많 배 변를 더 만들 능 리는데 .
push_back 배 를 는데 는 보 많 배 변를 더 만들 능 리는데 .
~cpp template<class T> class Vec { public: size_type size() const { return avail - data; } iterator end() { return avail; } const_iterator end() const { return avail; } void push_back(const T& val) { if (avail == limit) grwo(0; unchecked_append(val); } private: iterator data; iterator avail; iterator limit; }
1.5. 11.5 Flexible memory management ¶
Vec new, delete 를 는. 배 new 면 본 는 디 문. 는 리 는 른 방 동.
따 리는 더 브러리 는 리를 .
따 리는 더 브러리 는 리를 .
<memory> allocate<> STL 메
allocate 멤 부
~cpp template<class T> class allocator { pubilc: T* allocate(size_t); void deallocate(T*, size_t); void construct(T*, T); void destroy(T*); };
allocate, deallocate | 메모리 , . 러 는 는. |
construct, destroy | 메모리 데 . ( allocate를 미 .) |
allocate 멤 부
~cpp template<class In, class For> For uninitialized_copy(In, In, For); tempalte<class for, class T> void uninitialized_fill(For, For, const T&);
uninitialized_copy | 번 번 만 3번 복. |
uninitialized_fill | 번 번 T . |
1.5.1. 11.5.1 Vec ¶
~cpp //vec.h #ifndef VEC_H #define VEC_H #include <algorithm> #include <cstddef> #include <memory> using std::max; template <class T> class Vec { public: typedef T* iterator; typedef const T* const_iterator; typedef size_t size_type; typedef T value_type; typedef T& reference; typedef const T& const_reference; Vec() { create(); } explicit Vec(size_type n, const T& t = T()) { create(n, t); } Vec(const Vec& v) { create(v.begin(), v.end()); } Vec& operator=(const Vec&); // as defined in 11.3.2/196 ~Vec() { uncreate(); } T& operator[](size_type i) { return data[i]; } const T& operator[](size_type i) const { return data[i]; } void push_back(const T& t) { if (avail == limit) grow(); unchecked_append(t); } size_type size() const { return avail - data; } // changed iterator begin() { return data; } const_iterator begin() const { return data; } iterator end() { return avail; } // changed const_iterator end() const { return avail; } // changed void clear() { uncreate(); } bool empty() const { return data == avail; } private: iterator data; // first element in the `Vec' iterator avail; // (one past) the last element in the `Vec' iterator limit; // (one past) the allocated memory // facilities for memory allocation std::allocator<T> alloc; // object to handle memory allocation // allocate and initialize the underlying array void create(); void create(size_type, const T&); void create(const_iterator, const_iterator); // destroy the elements in the array and free the memory void uncreate(); // support functions for `push_back' void grow(); void unchecked_append(const T&); }; template <class T> void Vec<T>::create() { data = avail = limit = 0; } template <class T> void Vec<T>::create(size_type n, const T& val) { data = alloc.allocate(n); limit = avail = data + n; std::uninitialized_fill(data, limit, val); } template <class T> void Vec<T>::create(const_iterator i, const_iterator j) { data = alloc.allocate(j - i); limit = avail = std::uninitialized_copy(i, j, data); } template <class T> void Vec<T>::uncreate() { if (data) { // destroy (in reverse order) the elements that were constructed iterator it = avail; while (it != data) alloc.destroy(--it); // return all the space that was allocated alloc.deallocate(data, limit - data); } // reset pointers to indicate that the `Vec' is empty again data = limit = avail = 0; } template <class T> void Vec<T>::grow() { // when growing, allocate twice as much space as currently in use size_type new_size = max(2 * (limit - data), ptrdiff_t(1)); // allocate new space and copy existing elements to the new space iterator new_data = alloc.allocate(new_size); iterator new_avail = std::uninitialized_copy(data, avail, new_data); // return the old space uncreate(); // reset pointers to point to the newly allocated space data = new_data; avail = new_avail; limit = data + new_size; } // assumes `avail' points at allocated, but uninitialized space template <class T> void Vec<T>::unchecked_append(const T& val) { alloc.construct(avail++, val); } template <class T> Vec<T>& Vec<T>::operator=(const Vec& rhs) { // check for self-assignment if (&rhs != this) { // free the array in the left-hand side uncreate(); // copy elements from the right-hand to the left-hand side create(rhs.begin(), rhs.end()); } return *this; } #endif불변(class invariant)
- data는 번 , 면 0 .
- data<=avail<=limit
- 는 [data, avail) 범
- 는 [avail, limit) 범
~cpp template <class T> void Vec<T>::create() { data = avail = limit = 0; // 디 문 를 빈 낸. } template <class T> void Vec<T>::create(size_type n, const T& val) { data = alloc.allocate(n); // 받 만 . limit = avail = data + n; // 리. 는 n 문 avail = limit . std::uninitialized_fill(data, limit, val); // 러 를 문 멤를 . } template <class T> void Vec<T>::create(const_iterator i, const_iterator j) { data = alloc.allocate(j - i); limit = avail = std::uninitialized_copy(i, j, data); }
바람.
~cpp template <class T> void Vec<T>::uncreate() { if (data) { // destroy (in reverse order) the elements that were constructed iterator it = avail; while (it != data) alloc.destroy(--it); // return all the space that was allocated alloc.deallocate(data, limit - data); } // reset pointers to indicate that the `Vec' is empty again data = limit = avail = 0; }
는 내부 들 destroy를 멸.
deallocate 를 메모리 .
는 빈 백 내 data, limit, avail .
~cpp template <class T> void Vec<T>::grow() { // when growing, allocate twice as much space as currently in use size_type new_size = max(2 * (limit - data), ptrdiff_t(1)); // 는 벡 는 1만 . // allocate new space and copy existing elements to the new space iterator new_data = alloc.allocate(new_size); iterator new_avail = std::uninitialized_copy(data, avail, new_data); // return the old space uncreate(); // reset pointers to point to the newly allocated space data = new_data; avail = new_avail; limit = data + new_size; } // assumes `avail' points at allocated, but uninitialized space template <class T> void Vec<T>::unchecked_append(const T& val) { alloc.construct(avail++, val); }
grow 는 번 미 2배를 문 push_back 메모리 를 .
unchecked_append()는 grow() 바 뒤만 동 문 동 보 . (물 문 남 른 머 듯)