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. 11.3 Copy control ¶
리가 복, 대, 멸 는 대 명로 면 러는 만 방법로 런 는 를 만들 동게 된다.
렇게 객 동 규 는 로는 C++ 다. (그만 래를 때 많 것들 고려되다.)
렇게 객 동 규 는 로는 C++ 다. (그만 래를 때 많 것들 고려되다.)
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& 로 되
릿 는 매개변를 략는 더 다.
Vec::operator= 라, Vec<T>::operator= 가 래 다. 그러나 단 operator=가 Vec<T> 멤라는 밝면 더 릿 를 반복 가 다.
- 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() 바로 뒤만 동록 구기 때문 동 보 다. (물론 문로 남겨 래 다른 로그래머가 록 듯)