nlib
ReallocVec.h
[詳解]
1 
2 #pragma once
3 #ifndef INCLUDE_NN_NLIB_REALLOCVEC_H_
4 #define INCLUDE_NN_NLIB_REALLOCVEC_H_
5 
6 #include <stdlib.h>
7 #include <string.h>
8 #include <algorithm>
9 #include <iterator>
10 
11 #include "nn/nlib/Config.h"
12 #include "nn/nlib/UniquePtr.h"
13 #include "nn/nlib/TypeTraits.h"
14 
15 NLIB_NAMESPACE_BEGIN
16 
17 template <class T>
18 class ReallocVec {
19  public:
20  typedef void* (*ReallocFunc)(void*, size_t);
21  typedef T value_type;
22  typedef size_t size_type;
23  typedef ptrdiff_t difference_type;
24  typedef T& reference;
25  typedef const T& const_reference;
26  typedef T* pointer;
27  typedef const T* const_pointer;
28  typedef T* iterator;
29  typedef const T* const_iterator;
30  typedef std::reverse_iterator<iterator> reverse_iterator;
31  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
33  m_Cur(0),
34  m_Size(0),
35  m_Realloc(::nlib_realloc) {}
36  NLIB_CEXPR explicit ReallocVec(ReallocFunc func) NLIB_NOEXCEPT NLIB_NONNULL;
38  if (m_Vec) {
39  m_Realloc(m_Vec, 0);
40  }
41  NLIB_STATIC_ASSERT(IsPod<T>::value);
42  }
43  NLIB_MOVE_MEMBER_HELPER_4(ReallocVec, m_Vec, m_Cur, m_Size, m_Realloc)
44 
45  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return m_Realloc; }
46  bool push_back(const T& v) NLIB_NOEXCEPT {
47  if (m_Cur == m_Size) {
48  size_t newSize = (m_Size == 0) ? 1 : m_Size * 2;
49  if (newSize < m_Size) return false;
50  if (!this->Expand(newSize)) return false;
51  }
52  m_Vec[m_Cur++] = v;
53  return true;
54  }
56  if (m_Cur == 0) return false;
57  --m_Cur;
58  return true;
59  }
60  T& operator[](size_t idx) { return m_Vec[idx]; }
61  const T& operator[](size_t idx) const { return m_Vec[idx]; }
62  T& front() { return *begin(); }
63  const T& front() const { return *begin(); }
64  T& back() { return *(begin() + m_Cur - 1); }
65  const T& back() const { return *(begin() + m_Cur - 1); }
66 
67  iterator begin() NLIB_NOEXCEPT { return m_Vec; }
68  const_iterator begin() const NLIB_NOEXCEPT { return m_Vec; }
69  const_iterator cbegin() const NLIB_NOEXCEPT { return m_Vec; }
70  iterator end() NLIB_NOEXCEPT { return begin() + m_Cur; }
71  const_iterator end() const NLIB_NOEXCEPT { return begin() + m_Cur; }
72  const_iterator cend() const NLIB_NOEXCEPT { return begin() + m_Cur; }
73  reverse_iterator rbegin() NLIB_NOEXCEPT { return reverse_iterator(end()); }
74  const_reverse_iterator rbegin() const NLIB_NOEXCEPT {
75  return const_reverse_iterator(end());
76  }
77  reverse_iterator rend() NLIB_NOEXCEPT { return reverse_iterator(begin()); }
78  const_reverse_iterator rend() const NLIB_NOEXCEPT {
79  return const_reverse_iterator(begin());
80  }
81  const_reverse_iterator crbegin() const NLIB_NOEXCEPT {
82  return const_reverse_iterator(end());
83  }
84  const_reverse_iterator crend() const NLIB_NOEXCEPT {
85  return const_reverse_iterator(begin());
86  }
88  using std::swap;
89  swap(m_Vec, rhs.m_Vec);
90  swap(m_Cur, rhs.m_Cur);
91  swap(m_Size, rhs.m_Size);
92  swap(m_Realloc, rhs.m_Realloc);
93  }
94  size_t size() const NLIB_NOEXCEPT { return m_Cur; }
95  size_t capacity() const NLIB_NOEXCEPT { return m_Size; }
96  bool empty() const NLIB_NOEXCEPT { return m_Cur == 0; }
97  bool reserve(size_t n) NLIB_NOEXCEPT {
98  return (n > m_Size) ? this->Expand(n) : true;
99  }
100  bool resize(size_t n) NLIB_NOEXCEPT {
101  if (!this->reserve(n)) return false;
102  m_Cur = n;
103  return true;
104  }
105  void clear() NLIB_NOEXCEPT { m_Cur = 0; }
107  if (m_Cur != m_Size) {
108  if (m_Cur > 0) {
109  this->Expand(m_Cur);
110  } else {
111  m_Realloc(m_Vec, 0);
112  m_Vec = NULL;
113  m_Size = 0;
114  }
115  }
116  }
117  iterator insert(iterator pos, const T& val) {
118  ptrdiff_t idx = pos - begin();
119  if (!this->push_back(val)) return NULL;
120  std::rotate(begin() + idx, &back(), end());
121  return begin() + idx;
122  }
123 
124  private:
125  bool Expand(size_t newSize) NLIB_NOEXCEPT;
126 
127  T* m_Vec;
128  size_t m_Cur;
129  size_t m_Size;
130  ReallocFunc m_Realloc;
132 };
133 
134 template <class T>
135 inline NLIB_CEXPR ReallocVec<T>::ReallocVec(ReallocFunc func) NLIB_NOEXCEPT : m_Vec(NULL),
136  m_Cur(0),
137  m_Size(0),
138  m_Realloc(func) {}
139 
140 template <class T>
141 bool ReallocVec<T>::Expand(size_t newSize) NLIB_NOEXCEPT {
142  T* ptr = m_Vec;
143  void* newPtr = m_Realloc(ptr, newSize * sizeof(T));
144  if (!newPtr) return false;
145  m_Vec = reinterpret_cast<T*>(newPtr);
146  m_Size = newSize;
147  return true;
148 }
149 
150 template <class T>
152  public:
154  ReallocQueue() NLIB_NOEXCEPT : m_FrontIdx(0) {}
155  explicit ReallocQueue(ReallocFunc func) NLIB_NOEXCEPT : m_FrontIdx(0),
156  m_FrontVec(func),
157  m_BackVec(func) {}
159  NLIB_MOVE_MEMBER_HELPER_3(ReallocQueue, m_FrontIdx, m_FrontVec, m_BackVec)
160  ReallocFunc GetRealloc() const NLIB_NOEXCEPT {
161  return m_FrontVec.GetRealloc();
162  }
163  size_t size() const NLIB_NOEXCEPT {
164  return m_FrontVec.size() - m_FrontIdx + m_BackVec.size();
165  }
166  bool empty() const NLIB_NOEXCEPT {
167  return m_FrontIdx == m_FrontVec.size() && m_BackVec.empty();
168  }
169  bool push(const T& val) NLIB_NOEXCEPT { return m_BackVec.push_back(val); }
171  if (m_FrontIdx == m_FrontVec.size()) {
172  if (m_BackVec.empty()) return false;
173  m_FrontVec.clear();
174  m_FrontVec.swap(m_BackVec);
175  m_FrontIdx = 0;
176  }
177  ++m_FrontIdx;
178  return true;
179  }
180  T& front() {
181  if (m_FrontIdx == m_FrontVec.size()) {
182  NLIB_ASSERT(!m_BackVec.empty());
183  m_FrontVec.clear();
184  m_FrontVec.swap(m_BackVec);
185  m_FrontIdx = 0;
186  }
187  return m_FrontVec[m_FrontIdx];
188  }
189  bool pop(T* v) NLIB_NOEXCEPT {
190  if (m_FrontIdx == m_FrontVec.size()) {
191  if (m_BackVec.empty()) return false;
192  m_FrontVec.clear();
193  m_FrontVec.swap(m_BackVec);
194  m_FrontIdx = 0;
195  }
196  if (v) *v = m_FrontVec[m_FrontIdx];
197  ++m_FrontIdx;
198  return true;
199  }
201  using std::swap;
202  swap(m_FrontIdx, rhs.m_FrontIdx);
203  m_FrontVec.swap(rhs.m_FrontVec);
204  m_BackVec.swap(rhs.m_BackVec);
205  }
206 
207  private:
208  size_t m_FrontIdx;
209  ReallocVec<T> m_FrontVec;
210  ReallocVec<T> m_BackVec;
212 };
213 
215  typedef ReallocVec<char*> VecType;
216  typedef VecType::ReallocFunc ReallocFunc;
217 
218  public:
220  explicit ReallocCstringVec(ReallocFunc func) NLIB_NOEXCEPT : m_Vec(func) {}
221  ~ReallocCstringVec() NLIB_NOEXCEPT { this->clear(); }
222  NLIB_MOVE_MEMBER_HELPER_1(ReallocCstringVec, m_Vec)
223  ReallocFunc GetRealloc() const NLIB_NOEXCEPT { return m_Vec.GetRealloc(); }
224  bool push_back(const char* str) NLIB_NOEXCEPT {
225  return this->push_back(str, str + nlib_strlen(str));
226  }
227  bool push_back(const char* startCharPtr,
228  const char* endCharPtr) NLIB_NOEXCEPT {
229  size_t n = endCharPtr - startCharPtr;
230  char* p = reinterpret_cast<char*>(m_Vec.GetRealloc()(NULL, n + 1));
231  if (!p) return false;
232  nlib_memcpy(p, n, startCharPtr, n);
233  p[n] = '\0';
234  if (!m_Vec.push_back(p)) return false;
235  return true;
236  }
238  if (m_Vec.empty()) return false;
239  m_Vec.GetRealloc()(m_Vec.back(), 0);
240  m_Vec.pop_back();
241  return true;
242  }
243  char* operator[](size_t idx)NLIB_NOEXCEPT { return m_Vec[idx]; }
244  const char* operator[](size_t idx) const NLIB_NOEXCEPT {
245  return m_Vec[idx];
246  }
247  char* front() NLIB_NOEXCEPT { return m_Vec.front(); }
248  const char* front() const NLIB_NOEXCEPT { return m_Vec.front(); }
249  char* back() NLIB_NOEXCEPT { return m_Vec.back(); }
250  const char* back() const NLIB_NOEXCEPT { return m_Vec.back(); }
251  void swap(ReallocCstringVec& rhs) NLIB_NOEXCEPT { m_Vec.swap(rhs.m_Vec); }
252  size_t size() const NLIB_NOEXCEPT { return m_Vec.size(); }
253  size_t capacity() const NLIB_NOEXCEPT { return m_Vec.capacity(); }
254  bool empty() const NLIB_NOEXCEPT { return m_Vec.empty(); }
255  bool reserve(size_t n) NLIB_NOEXCEPT { return m_Vec.reserve(n); }
256  void clear() NLIB_NOEXCEPT {
257  VecType::iterator it = m_Vec.begin();
258  VecType::iterator end = m_Vec.end();
259  for (; it != end; ++it) {
260  m_Vec.GetRealloc()(*it, 0);
261  }
262  m_Vec.clear();
263  }
264 
265  private:
266  VecType m_Vec;
267  NLIB_DISALLOW_COPY_AND_ASSIGN(ReallocCstringVec);
268 };
269 
270 NLIB_NAMESPACE_END
271 
272 NLIB_DEFINE_STD_SWAP(NLIB_NS::ReallocCstringVec)
273 #ifndef NLIB_STD_SWAP_WORKAROUND
274 NLIB_NAMESPACE_BEGIN
275 #else
276 NLIB_DEFINE_STD_SWAP_T_BEGIN1(std) // NOLINT
277 #endif
278 
279 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::ReallocVec) // NOLINT
280 NLIB_DEFINE_STD_SWAP_T1(AL, NLIB_NS::ReallocQueue) // NOLINT
281 
282 #ifndef NLIB_STD_SWAP_WORKAROUND
283 NLIB_NAMESPACE_END
284 #else
285 NLIB_DEFINE_STD_SWAP_T_END1(std) // NOLINT
286 #endif
287 
288 #endif // INCLUDE_NN_NLIB_REALLOCVEC_H_
#define NLIB_NOEXCEPT
環境に合わせてnoexcept 又は同等の定義がされます。
Definition: Platform.h:2151
T * iterator
ランダムアクセスイテレータ
Definition: ReallocVec.h:28
bool empty() const noexcept
キューが空かどうかを判定する
Definition: ReallocVec.h:166
ReallocQueue(ReallocFunc func) noexcept
コンストラクタで、realloc関数をユーザーが指定できます。
Definition: ReallocVec.h:155
size_t capacity() const noexcept
ベクタの拡張をせずに格納できる最大の要素数を取得する
Definition: ReallocVec.h:253
ReallocVec< T >::ReallocFunc ReallocFunc
reallocに相当する関数の型です。
Definition: ReallocVec.h:153
T value_type
要素型 T
Definition: ReallocVec.h:21
bool push_back(const T &v) noexcept
ベクタに要素を追加します。
Definition: ReallocVec.h:46
C++11の標準ヘッダとなるtype_traitsの代用定義です。 コンパイラや標準ライブラリによってサポートされてい...
const_reverse_iterator crend() const noexcept
先頭の前を指す読み取り専用逆イテレータを取得する。
Definition: ReallocVec.h:84
size_t size_type
符号なし整数型(size_t)
Definition: ReallocVec.h:22
bool empty() const noexcept
ベクタが空かどうかを判定する
Definition: ReallocVec.h:254
#define NLIB_NONNULL
全ての引数にNULLを指定することができないことを示します。
Definition: Platform_unix.h:66
char * front() noexcept
最初の文字列を取得します。
Definition: ReallocVec.h:247
#define NLIB_DISALLOW_COPY_AND_ASSIGN(TypeName)
TypeName で指定されたクラスのコピーコンストラクタと代入演算子を禁止します。
Definition: Config.h:126
bool pop_back() noexcept
ベクタの末尾から文字列を削除します。
Definition: ReallocVec.h:237
size_t size() const noexcept
ベクタのサイズを取得する
Definition: ReallocVec.h:252
const_reverse_iterator rend() const noexcept
rend()を御覧ください。
Definition: ReallocVec.h:78
C文字列のベクタをreallocベースで実装しています。
Definition: ReallocVec.h:214
PODを要素に持つキューをreallocベースで実装しています。
Definition: ReallocVec.h:151
STL namespace.
const_iterator begin() const noexcept
begin()を御覧ください。
Definition: ReallocVec.h:68
const T * const_pointer
const T*
Definition: ReallocVec.h:27
bool reserve(size_t n) noexcept
n 個の要素までをベクタの拡張をせずに格納できるようにする。
Definition: ReallocVec.h:255
iterator insert(iterator pos, const T &val)
要素をposの場所に挿入します。
Definition: ReallocVec.h:117
const_iterator cend() const noexcept
末尾の次を指す読み取り専用イテレータを取得する。
Definition: ReallocVec.h:72
const_iterator end() const noexcept
end()を御覧ください。
Definition: ReallocVec.h:71
char * back() noexcept
最後の文字列を取得します。
Definition: ReallocVec.h:249
size_t capacity() const noexcept
メモリを再確保せずに格納できる最大の要素数を取得する
Definition: ReallocVec.h:95
bool pop() noexcept
キューの先頭要素を削除する。
Definition: ReallocVec.h:170
std::unique_ptrに相当するクラスが定義されています。
const_iterator cbegin() const noexcept
先頭要素を指す読み取り専用イテレータを取得する。
Definition: ReallocVec.h:69
const T & const_reference
const T&
Definition: ReallocVec.h:25
const T * const_iterator
読み取り専用ランダムアクセスイテレータ
Definition: ReallocVec.h:29
T & front()
最初の要素を取得します。
Definition: ReallocVec.h:62
size_t size() const noexcept
キューのサイズを取得する
Definition: ReallocVec.h:163
void swap(ReallocCstringVec &rhs) noexcept
ベクタを交換する
Definition: ReallocVec.h:251
bool resize(size_t n) noexcept
要素数を変更する
Definition: ReallocVec.h:100
bool reserve(size_t n) noexcept
n 個の要素までをメモリを最確保せずに格納できるようにする。
Definition: ReallocVec.h:97
T & back()
最後の要素を取得します。
Definition: ReallocVec.h:64
bool pop(T *v) noexcept
キューの先頭要素を取得し、その後削除する。
Definition: ReallocVec.h:189
bool pop_back() noexcept
ベクタの末尾から要素を削除します。
Definition: ReallocVec.h:55
void swap(ReallocQueue &rhs) noexcept
キューを交換する
Definition: ReallocVec.h:200
const T & front() const
front()をご覧ください。
Definition: ReallocVec.h:63
#define NLIB_CEXPR
利用可能であればconstexprが定義されます。そうでない場合は空文字列です。
std::reverse_iterator< const_iterator > const_reverse_iterator
std::reverse_iterator
Definition: ReallocVec.h:31
ReallocCstringVec() noexcept
デフォルトコンストラクタで、std::reallocを利用します。
Definition: ReallocVec.h:219
T & operator[](size_t idx)
idx 番目の要素を取得します。
Definition: ReallocVec.h:60
reverse_iterator rend() noexcept
先頭の前を指す逆イテレータを取得する。
Definition: ReallocVec.h:77
bool push_back(const char *str) noexcept
C文字列を末尾に追加します。
Definition: ReallocVec.h:224
bool push_back(const char *startCharPtr, const char *endCharPtr) noexcept
(部分)文字列を末尾に追加します。
Definition: ReallocVec.h:227
constexpr ReallocVec() noexcept
デフォルトコンストラクタで、std::reallocを利用します。
Definition: ReallocVec.h:32
size_t size() const noexcept
ベクタのサイズを取得する
Definition: ReallocVec.h:94
ReallocCstringVec(ReallocFunc func) noexcept
コンストラクタで、realloc関数をユーザーが指定できます。
Definition: ReallocVec.h:220
const_reverse_iterator rbegin() const noexcept
rbegin()を御覧ください。
Definition: ReallocVec.h:74
void clear() noexcept
ベクタを空にします。メモリは確保されたままであることに注意してください。
Definition: ReallocVec.h:105
const T & back() const
back()を御覧ください。
Definition: ReallocVec.h:65
iterator end() noexcept
末尾の次を指すイテレータを取得する。
Definition: ReallocVec.h:70
開発環境別の設定が書かれるファイルです。
const_reverse_iterator crbegin() const noexcept
末尾要素を指す読み取り専用逆イテレータを取得する。
Definition: ReallocVec.h:81
reverse_iterator rbegin() noexcept
末尾要素を指す逆イテレータを取得する。
Definition: ReallocVec.h:73
bool push(const T &val) noexcept
キューに要素を追加する。
Definition: ReallocVec.h:169
std::reverse_iterator< iterator > reverse_iterator
std::reverse_iterator
Definition: ReallocVec.h:30
NLIB_CHECK_RESULT void * nlib_realloc(void *ptr, size_t size)
C標準関数のrealloc()を呼び出すweak関数です。nlibはこの関数を経由してrealloc()を呼び出します。 ...
char * operator[](size_t idx) noexcept
idx番目の文字列を取得します。
Definition: ReallocVec.h:243
size_t nlib_strlen(const char *s)
内部でstrlen()を呼び出します。独自の実装が動作する場合もあります。
void shrink_to_fit() noexcept
確保されたメモリを現在の要素数を丁度格納できるサイズにフィッティングします。
Definition: ReallocVec.h:106
iterator begin() noexcept
先頭要素を指すイテレータを取得する。
Definition: ReallocVec.h:67
#define NLIB_STATIC_ASSERT(exp)
静的アサートが定義されます。利用可能であればstatic_assertを利用します。
Definition: Config.h:117
ReallocQueue() noexcept
デフォルトコンストラクタで、std::reallocを利用します。
Definition: ReallocVec.h:154
ptrdiff_t difference_type
符号つき整数型(ptrdiff_t)
Definition: ReallocVec.h:23
bool empty() const noexcept
ベクタが空かどうかを判定する
Definition: ReallocVec.h:96
T & front()
キューの先頭要素を取得する。
Definition: ReallocVec.h:180
PODを要素に持つベクタをreallocベースで実装しています。
Definition: ReallocVec.h:18
const T & operator[](size_t idx) const
operator[](size_t idx) を御覧ください。
Definition: ReallocVec.h:61
errno_t nlib_memcpy(void *s1, size_t s1max, const void *s2, size_t n)
N1078のmemcpy_sに相当する実装です。
Definition: Platform.h:2095
void swap(ReallocVec &rhs) noexcept
ベクタを交換する
Definition: ReallocVec.h:87