[STL-9]에서 vector 멤버함수들의 용도와 사용방법에 대하여 보았습니다.
이번에는 실제 vector를 만들어 보도록 하겠습니다.
처음은 이해하기 쉽게 teamplate array를 이용하여 vector를 만든 것이며
두 번째 예제는 Accelerated C++ chapter 11에 있는 vector 구현 내용을
그대로 copy한 것입니다.
몇 몇 함수가 빠지긴 하였지만 대부분 기능이 구현된 vector의 모습니다.
단, 두 예제 모두 상속에 대한 것은 배제한 design이란 것을 알아 두시기 바랍니다.
첫 번째 예는 매우 간단한 형태입니다. array를 이용하여 자료를 관리하고 생성/복사/대입 등에 의하여 new를 호출하게 되어있고 소멸자를 통하여 모든 메모리가 해제됩니다.
vector는 random access형태가 가능한 컨테이너이므로 배열을과 포인터를 이용하면 기능적인 부분 구현에는 별다른 문제는 없습니다.
그리고 STL container는 data 생성자체가 자유공간을 사용하게 되어 있으므로 굳이 vector 객체를 new로 선언할 필요는 없습니다.
myVec.h
1 #ifndef __MYVEC_H__
2 #define __MYVEC_H__
3
4 template <class T>
5 class myVec {
6 private:
7 int sz;
8 T *v;
9 public:
10 myVec();
11 explicit myVec(int n); // 명시적인 선언, 0으로 초기화
12 myVec(const T &a, int n); // 값으로 n 만큼의 크기를 만들고 초기화
13 myVec(const T *a, int n); // 포인터로 n 만큼의 크기를 만들고 초기화
14 myVec(const myVec &rhs); // 복사 생성자
15 myVec & operator=(const myVec &rhs); // 대입 연산자
16 myVec & operator=(const T &a); // 전체 요소를 a로 변경
17 inline T & operator[](const int i); // 인덱스 연산자 [i] 값 반환
18 inline const T & operator[](const int i) const;
19 inline int size() const;
20 ~myVec();
21 };
22
23 template <class T>
24 myVec<T>::myVec() : sz(0), v(0) {}
25
26 template <class T>
27 myVec<T>::myVec(int n) : sz(n), v(new T[n]) {}
28
29 template <class T>
30 myVec<T>::myVec(const T& a, int n) : sz(n), v(new T[n])
31 {
32 for(int i=0; i<n; i++)
33 v[i] = a;
34 }
35
36 template <class T>
37 myVec<T>::myVec(const T *a, int n) : sz(n), v(new T[n])
38 {
39 for(int i=0; i<n; i++)
40 v[i] = *a++;
41 }
42
43 template <class T>
44 myVec<T>::myVec(const myVec<T> &rhs) : sz(rhs.sz), v(new T[sz])
45 {
46 for(int i=0; i<sz; i++)
47 v[i] = rhs[i];
48 }
49
50 template <class T>
51 myVec<T> & myVec<T>::operator=(const myVec<T> &rhs)
52 {
53 if (this != &rhs)
54 {
55 if (sz != rhs.sz) {
56 if (v != 0) delete [] (v);
57 sz=rhs.sz;
58 v= new T[sz];
59 }
60 for (int i=0; i<sz; i++)
61 v[i]=rhs[i];
62 }
63 return *this;
64 }
65
66 template <class T>
67 myVec<T> & myVec<T>::operator=(const T &a)
68 {
69 for (int i=0; i<sz; i++)
70 v[i]=a;
71 return *this;
72 }
73
74 template <class T>
75 inline T & myVec<T>::operator[](const int i)
76 {
77 return v[i];
78 }
79
80 template <class T>
81 inline const T & myVec<T>::operator[](const int i) const
82 {
83 return v[i];
84 }
85
86 template <class T>
87 inline int myVec<T>::size() const
88 {
89 return sz;
90 }
91
92 template <class T>
93 myVec<T>::~myVec()
94 {
95 if (v != 0)
96 delete[] (v);
97 }
98
99 #endif //__MYVEC_H__
|
두 번째 예제는 Accelerated C++에서 소개한 Vec.h 내용입니다.
기본적인 메모리 관리는 <momory> 의 allocate를 이용합니다. 거의 완벽한 형태의 smart point로 사용할 수 있으므로 error에 대한 내용은 allocate가 알아서 처리하게 합니다.
잘 보실 부분이 push_back 함수인데 자료를 뒤쪽에 추가할 때 실제 입력가능한 메모리가 할당 되어 있는지를 확인 하고 만약 limit가 추가된 위치와 동이하게 되면 grow()를 이용하여 2배의 크기로 메모리를 재할당 하게 되어 있습니다.
이전에 vector에 대하여 설명할 때 메모리를 2배의 사이즈로 가지고 있다고 말한 부분이 있을겁니다. 이처럼 해서 자료가 추가될 때마다 메모리를 재설정하는 횟수를 줄이기 위함입니다. 그리고 사이즈를 늘리게 되면 메모리공간을 재할당하여 모든 자료를 재설정하는 것을 알 수 있습니다. 그리고 사이즈를 늘이는 경우 외에 자료를 중간에 넣거나 중간에서 삭제하거나 하게 되면 추가나 삭제 작업이 일어난 위치 뒤의 모든 자료는 메모리가 재설정된다는 사실도 아시는 것이 좋습니다.
clear와 소멸자 부분도 유심히 볼 필요가 있습니다. uncreate() 하게 되면 모든 자료를 alloc을 이용하여 하나씩 삭제하여 data=avail=limit=0 으로 empty 처리 해버립니다.
그리고 참고로 vector가 비었는지 확인할 때 vec.size()==0 보다는 vec.empty()를 호출하는 편이 효율적이라는 것도 알아 두세요.
Vec.h
1 #ifndef VEC_H
2 #define VEC_H
3
4 #include <algorithm>
5 #include <cstddef>
6 #include <memory>
7
8 #ifdef _MSC_VER
9 #include "../minmax.h"
10 #else
11 using std::max;
12 #endif
13
14 template <class T> class Vec {
15 public:
16 typedef T* iterator;
17 typedef const T* const_iterator;
18 typedef size_t size_type;
19 typedef T value_type;
20 typedef T& reference;
21 typedef const T& const_reference;
22
23 Vec() { create(); }
24 explicit Vec(size_type n, const T& t = T()) { create(n, t); }
25
26 Vec(const Vec& v) { create(v.begin(), v.end()); }
27 Vec& operator=(const Vec&);
28 ~Vec() { uncreate(); }
29
30 T& operator[](size_type i) { return data[i]; }
31 const T& operator[](size_type i) const { return data[i]; }
32
33 void push_back(const T& t) {
34 if (avail == limit)
35 grow();
36 unchecked_append(t);
37 }
38
39 size_type size() const { return avail - data; } // changed
40
41 iterator begin() { return data; }
42 const_iterator begin() const { return data; }
43
44 iterator end() { return avail; } // changed
45 const_iterator end() const { return avail; } // changed
46 void clear() { uncreate(); }
47 bool empty() const { return data == avail; }
48
49 private:
50 iterator data; // first element in the `Vec'
51 iterator avail; // (one past) the last element in the `Vec'
52 iterator limit; // (one past) the allocated memory
53
54 // facilities for memory allocation
55 std::allocator<T> alloc; // object to handle memory allocation
56
57 // allocate and initialize the underlying array
58 void create();
59 void create(size_type, const T&);
60 void create(const_iterator, const_iterator);
61
62 // destroy the elements in the array and free the memory
63 void uncreate();
64
65 // support functions for `push_back'
66 void grow();
67 void unchecked_append(const T&);
68 };
69
70 template <class T> void Vec<T>::create()
71 {
72 data = avail = limit = 0;
73 }
74
75 template <class T> void Vec<T>::create(size_type n, const T& val)
76 {
77 #ifdef _MSC_VER
78 data = alloc.allocate(n, 0);
79 #else
80 data = alloc.allocate(n);
81 #endif
82 limit = avail = data + n;
83 std::uninitialized_fill(data, limit, val);
84 }
85
86 template <class T>
87 void Vec<T>::create(const_iterator i, const_iterator j)
88 {
89 #ifdef _MSC_VER
90 data = alloc.allocate(j - i, 0);
91 #else
92 data = alloc.allocate(j - i);
93 #endif
94 limit = avail = std::uninitialized_copy(i, j, data);
95 }
96
97 template <class T> void Vec<T>::uncreate()
98 {
99 if (data) {
100 // destroy (in reverse order) the elements that were constructed
101 iterator it = avail;
102 while (it != data)
103 alloc.destroy(--it);
104
105 // return all the space that was allocated
106 alloc.deallocate(data, limit - data);
107 }
108 // reset pointers to indicate that the `Vec' is empty again
109 data = limit = avail = 0;
110
111 }
112
113 template <class T> void Vec<T>::grow()
114 {
115 // when growing, allocate twice as much space as currently in use
116 size_type new_size = max(2 * (limit - data), ptrdiff_t(1));
117
118 // allocate new space and copy existing elements to the new space
119 #ifdef _MSC_VER
120 iterator new_data = alloc.allocate(new_size, 0);
121 #else
122 iterator new_data = alloc.allocate(new_size);
123 #endif
124 iterator new_avail = std::uninitialized_copy(data, avail, new_data);
125
126 // return the old space
127 uncreate();
128
129 // reset pointers to point to the newly allocated space
130 data = new_data;
131 avail = new_avail;
132 limit = data + new_size;
133 }
134
135 // assumes `avail' points at allocated, but uninitialized space
136 template <class T> void Vec<T>::unchecked_append(const T& val)
137 {
138 alloc.construct(avail++, val);
139 }
140
141 template <class T>
142 Vec<T>& Vec<T>::operator=(const Vec& rhs)
143 {
144 // check for self-assignment
145 if (&rhs != this) {
146
147 // free the array in the left-hand side
148 uncreate();
149
150 // copy elements from the right-hand to the left-hand side
151 create(rhs.begin(), rhs.end());
152 }
153 return *this;
154 }
155
156 #endif
|
'C C++ - STL' 카테고리의 다른 글
| STL - 12 auto_ptr (0) | 2014.02.13 |
|---|---|
| STL - 11 Function Object (함수 - 객체) (0) | 2014.02.13 |
| STL - 9 find, find_if (0) | 2014.02.13 |
| STL - 8 Vector 라이브러리 (0) | 2014.02.13 |
| STL - 7 Sequence Container (0) | 2014.02.13 |