stlab.adobe.com Adobe Systems Incorporated
vector.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 
7 /*************************************************************************************************/
8 
9 #ifndef ADOBE_VECTOR_HPP
10 #define ADOBE_VECTOR_HPP
11 
12 /*************************************************************************************************/
13 
14 #include <adobe/config.hpp>
15 
16 #include <adobe/vector_fwd.hpp>
17 
18 #include <algorithm>
19 #include <cassert>
20 #include <cstddef>
21 #include <iterator>
22 #include <memory>
23 
24 #include <boost/operators.hpp>
25 #include <boost/static_assert.hpp>
26 #include <boost/type_traits/has_nothrow_constructor.hpp>
27 #include <boost/type_traits/is_integral.hpp>
28 #include <boost/utility/enable_if.hpp>
29 
30 #include <adobe/empty.hpp>
31 #include <adobe/typeinfo.hpp>
32 #include <adobe/memory.hpp>
34 
35 #include <adobe/move.hpp>
36 #include <adobe/implementation/swap.hpp>
37 
38 #ifdef ADOBE_STD_SERIALIZATION
39 #include <adobe/iomanip.hpp>
40 #endif
41 
42 /*************************************************************************************************/
43 
44 namespace adobe {
45 namespace version_1 {
46 
53 /*************************************************************************************************/
54 
56 template <typename T, // T models Regular
57  typename A> // A models Allocator(T)
58 class vector : boost::totally_ordered<vector<T, A>, vector<T, A> >
59 {
60  public:
61  typedef T& reference;
62  typedef const T& const_reference;
63  typedef T* iterator;
64  typedef const T* const_iterator;
65  typedef std::size_t size_type;
66  typedef std::ptrdiff_t difference_type;
67  typedef T value_type;
68  typedef A allocator_type;
69  typedef T* pointer;
70  typedef const T* const_pointer;
71  typedef std::reverse_iterator<T*> reverse_iterator;
72  typedef std::reverse_iterator<const T*> const_reverse_iterator;
73 
74  private:
75  struct header_t
76  {
78  {
79  boost::compressed_pair<A, T*> allocate_finish_m;
81  };
83  T storage_m[1];
84 
85  allocator_type& allocator() { return header_m.get().allocate_finish_m.first(); }
86  const allocator_type& allocator() const { return header_m.get().allocate_finish_m.first(); }
87 
88  pointer& finish() { return header_m.get().allocate_finish_m.second(); }
89  const pointer& finish() const { return header_m.get().allocate_finish_m.second(); }
90 
91  pointer& end_of_storage() { return header_m.get().end_of_storage_m; }
92  const pointer& end_of_storage() const { return header_m.get().end_of_storage_m; }
93  };
94 
95  header_t* header_m;
96 
97  void set_finish(T* x)
98  {
99  assert(header_m != 0 || x == 0);
100  if (header_m) header_m->finish() = x;
101  }
102 
103  const T* end_of_storage() const { return header_m ? header_m->end_of_storage() : 0; }
104 
105  static header_t* allocate(allocator_type, std::size_t);
106 
107  size_type remaining() const { return end_of_storage() - end(); }
108 
109  template <typename I> // I models InputIterator
110  void append(I f, I l) { append(f, l, typename std::iterator_traits<I>::iterator_category()); }
111 
112  template <typename I> // I models InputIterator
113  void append(I f, I l, std::input_iterator_tag);
114 
115  template <typename I> // I models ForwardIterator
116  void append(I f, I l, std::forward_iterator_tag);
117 
118  template <typename I> // I models InputIterator
119  void append_move(I f, I l)
120  { append_move(f, l, typename std::iterator_traits<I>::iterator_category()); }
121 
122  template <typename I> // I models InputIterator
123  void append_move(I f, I l, std::input_iterator_tag);
124 
125  template <typename I> // I models ForwardIterator
126  void append_move(I f, I l, std::forward_iterator_tag);
127 
128  template <typename I> // I models InputIterator
129  iterator insert(iterator p, I f, I l, std::input_iterator_tag);
130 
131  template <typename I> // I models ForwardIterator
132  iterator insert(iterator p, I f, I l, std::forward_iterator_tag);
133 
134  public:
135  // 23.2.4.1 construct/copy/destroy
136 
137  explicit vector(const allocator_type& a) : header_m(allocate(a, 0)) { }
138  vector() : header_m(0) { }
139 
140  explicit vector(size_type n) : header_m(allocate(allocator_type(), n))
141  {
142  std::uninitialized_fill_n(end(), n, value_type());
143  set_finish(end() + n);
144  }
145 
146  vector(size_type n, const value_type& x) : header_m(allocate(allocator_type(), n))
147  {
148  std::uninitialized_fill_n(end(), n, x);
149  set_finish(end() + n);
150  }
151 
152  vector(size_type n, const value_type& x, const allocator_type& a) : header_m(allocate(a, n))
153  {
154  std::uninitialized_fill_n(end(), n, x);
155  set_finish(end() + n);
156  }
157 
158  vector(const vector& x) : header_m(allocate(x.get_allocator(), x.size()))
159  {
160 #ifndef NDEBUG
161  /* REVISIT (sparent) : MS stupid "safety check" doesn't known about empty ranges. */
162  set_finish(x.begin() == x.end() ? end() : std::uninitialized_copy(x.begin(), x.end(), end()));
163 #else
164  set_finish(std::uninitialized_copy(x.begin(), x.end(), end()));
165 #endif
166  }
167 
168  template <typename I> // I models InputIterator
169  vector(I f, I l, typename boost::disable_if<boost::is_integral<I> >::type* = 0) : header_m(0)
170  { append(f, l); }
171 
172  template <typename I> // I models InputIterator
173  vector(I f, I l, const allocator_type& a,
174  typename boost::disable_if<boost::is_integral<I> >::type* = 0) : header_m(allocate(a), 0)
175  { append(f, l); }
176 
178  if (header_m) {
179  clear();
180 
181  typename allocator_type::template rebind<char>::other alloc(get_allocator());
182  alloc.deallocate(reinterpret_cast<char*>(header_m),
183  (end_of_storage() - begin()) * sizeof(T) + (sizeof(header_t) - sizeof(T)));
184  }
185  }
186 
187  // adobe addition
188 
189  vector(move_from<vector> x) : header_m(x.source.header_m) { x.source.header_m = 0; }
190 
191  allocator_type get_allocator() const
192  { return header_m ? header_m->allocator() : allocator_type(); }
193 
194  iterator begin() { return header_m ? &header_m->storage_m[0] : 0; }
195  iterator end() { return header_m ? header_m->finish() : 0; }
196 
197  const_iterator begin() const { return header_m ? &header_m->storage_m[0] : 0; }
198  const_iterator end() const { return header_m ? header_m->finish() : 0; }
199 
200  reverse_iterator rbegin() { return reverse_iterator(end()); }
201  reverse_iterator rend() { return reverse_iterator(begin()); }
202 
203  const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
204  const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
205 
206  size_type size() const { return size_type(end() - begin()); }
207  size_type max_size() const { return size_type(-1) / sizeof(value_type); }
208 
209  size_type capacity() const { return size_type(end_of_storage() - begin()); }
210  bool empty() const { return begin() == end(); }
211 
212  reference operator[](size_type n) { assert(n < size()); return *(begin() + n); }
213  const_reference operator[](size_type n) const { assert(n < size()); return *(begin() + n); }
214 
215  /*
216  REVISIT (sparent@adobe.com): at() explicitly omitted because it pulls in out_of_range
217  which inherits from logic_error and uses std::string.
218  */
219 
220  vector& operator=(vector x) { swap(x); return *this; }
221 
222  void reserve(size_type n);
223 
224  reference front() { assert(!empty()); return *begin(); }
225  const_reference front() const { assert(!empty()); return *begin(); }
226 
227  reference back() { assert(!empty()); return *(end() - 1); }
228  const_reference back() const { assert(!empty()); return *(end() - 1); }
229 
230  void push_back(value_type x)
231  { append_move(&x, &x + 1); }
232 
233  void pop_back() { assert(!empty()); resize(size() - 1); }
234 
235  void swap(vector& x) { std::swap(header_m, x.header_m); }
236 
237  iterator insert(iterator p, value_type x)
238  { return insert_move(p, &x, &x + 1); }
239 
240  template <typename I> // I models InputIterator
241  iterator insert(iterator p, I f, I l, typename boost::disable_if<boost::is_integral<I> >::type* = 0)
242  { return insert(p, f, l, typename std::iterator_traits<I>::iterator_category()); }
243 
244  template <typename I> // I models ForwardIterator
245  iterator insert_move(iterator p, I f, I l);
246 
247  iterator insert(iterator p, size_type n, const T& x);
248 
249  iterator erase(iterator pos) { assert(pos != end()); return erase(pos, pos + 1); }
250 
251  iterator erase(iterator f, iterator l);
252 
253  void clear() { erase(begin(), end()); }
254 
255  void resize(size_type n);
256 
257  void resize(size_type n, const value_type& x);
258 
259  friend inline bool operator==(const vector& x, const vector& y)
260  {
261 #if defined(_MSC_VER) && _MSC_VER == 1600 && _ITERATOR_DEBUG_LEVEL != 0
262  return (x.size() == y.size()) && std::_Equal1(x.begin(), x.end(),
263  y.begin(), std::tr1::false_type());
264 #else
265  return (x.size() == y.size()) && std::equal(x.begin(), x.end(), y.begin());
266 #endif
267  }
268 
269  friend inline bool operator<(const vector& x, const vector& y)
270  {
271  return std::lexicographical_compare(x.begin(), x.end(), y.begin(), y.end());
272  }
273 
274  friend inline void swap(vector& x, vector& y) { x.swap(y); }
275 };
276 
277 template <typename T, typename A>
278 typename vector<T, A>::header_t* vector<T, A>::allocate(allocator_type a, std::size_t n)
279 {
280  if (n == 0) {
281  if (a == allocator_type()) return 0;
282  n = 1;
283  }
284 
285  typename allocator_type::template rebind<char>::other alloc(a);
286 
287  header_t* result = reinterpret_cast<header_t*>(alloc.allocate(sizeof(header_t) - sizeof(T)
288  + n * sizeof(T)));
289  construct(&result->allocator(), a);
290  result->finish() = &result->storage_m[0];
291  result->end_of_storage() = result->finish() + n;
292 
293  return result;
294 }
295 
296 template <typename T, typename A>
297 template <typename I> // I models InputIterator
298 void vector<T, A>::append(I f, I l, std::input_iterator_tag) { while (f != l) { push_back(*f); ++f; } }
299 
300 template <typename T, typename A>
301 template <typename I> // I models InputIterator
302 void vector<T, A>::append_move(I f, I l, std::input_iterator_tag)
303 { while (f != l) { push_back(adobe::move(*f)); ++f; } }
304 
305 template <typename T, typename A>
306 template <typename I> // I models ForwardIterator
307 void vector<T, A>::append(I f, I l, std::forward_iterator_tag)
308 {
309  size_type n(std::distance(f, l));
310 
311  if (remaining() < n) reserve((adobe::max)(size() + n, 2 * size()));
312  set_finish(std::uninitialized_copy(f, l, end()));
313 }
314 
315 template <typename T, typename A>
316 template <typename I> // I models ForwardIterator
317 void vector<T, A>::append_move(I f, I l, std::forward_iterator_tag)
318 {
319  size_type n(std::distance(f, l));
320 
321  if (remaining() < n) reserve((adobe::max)(size() + n, 2 * size()));
322  set_finish(adobe::uninitialized_move(f, l, end()));
323 }
324 
325 template <typename T, typename A>
326 template <typename I> // I models InputIterator
327 typename vector<T, A>::iterator vector<T, A>::insert(iterator p, I f, I l, std::input_iterator_tag)
328 {
329  size_type o(p - begin());
330  size_type s = size();
331  append(f, l);
332  // REVISIT (sparent) : This could be a move based rotate
333  std::rotate(begin() + o, begin() + s, end());
334  return end() - s + o;
335 }
336 
337 template <typename T, typename A>
338 template <typename I> // I models ForwardIterator
339 typename vector<T, A>::iterator vector<T, A>::insert(iterator p, I f, I l, std::forward_iterator_tag)
340 {
341  size_type n(std::distance(f, l));
342  iterator last = end();
343  size_type before = p - begin();
344 
345  if (remaining() < n) {
346  vector tmp;
347  tmp.reserve((adobe::max)(size() + n, 2 * size()));
348  tmp.append_move(begin(), p);
349  tmp.append(f, l);
350  tmp.append_move(p, last);
351  swap(tmp);
352  } else {
353  size_type after(last - p);
354 
355  if (n < after) {
356  append_move(last - n, last);
357  adobe::move_backward(p, last - n, last);
358  std::copy(f, l, p);
359  } else {
360  I m = f;
361  std::advance(m, after);
362  append(m, l);
363  append_move(p, last);
364  std::copy(f, m, p);
365  }
366  }
367  return begin() + before + n;
368 }
369 
370 template <typename T, typename A>
371 template <typename I> // I models ForwardIterator
372 typename vector<T, A>::iterator vector<T, A>::insert_move(iterator p, I f, I l)
373 {
374  size_type n(std::distance(f, l));
375  iterator last = end();
376  size_type before = p - begin();
377 
378  if (remaining() < n) {
379  vector tmp;
380  tmp.reserve((adobe::max)(size() + n, 2 * size()));
381  tmp.append_move(begin(), p);
382  tmp.append_move(f, l);
383  tmp.append_move(p, last);
384  swap(tmp);
385  } else {
386  size_type after(last - p);
387 
388  if (n < after) {
389  append_move(last - n, last);
390  adobe::move_backward(p, last - n, last);
391  adobe::move(f, l, p);
392  } else {
393  I m = f;
394  std::advance(m, after);
395  append_move(m, l);
396  append_move(p, last);
397  adobe::move(f, m, p);
398  }
399  }
400  return begin() + before + n;
401 }
402 
403 template <typename T, typename A>
404 void vector<T, A>::reserve(size_type n)
405 {
406  if (capacity() < n) {
407  vector tmp;
408  tmp.header_m = allocate(get_allocator(), n);
409  tmp.header_m->finish() = adobe::uninitialized_move(begin(), end(), tmp.end());
410  swap(tmp);
411  }
412 }
413 
414 template <typename T, typename A>
415 typename vector<T, A>::iterator vector<T, A>::insert(iterator p, size_type n, const T& x)
416 {
417  iterator last = end();
418  size_type before = p - begin();
419 
420  if (remaining() < n) {
421  vector tmp;
422  tmp.reserve((adobe::max)(size() + n, 2 * size()));
423  tmp.append_move(begin(), p);
424  std::uninitialized_fill_n(tmp.end(), n, x);
425  tmp.set_finish(tmp.end() + n);
426  tmp.append_move(p, last);
427  swap(tmp);
428  } else {
429  size_type after(last - p);
430 
431  if (n < after) {
432  append_move(last - n, last);
433  adobe::move_backward(p, last - n, last);
434  std::fill_n(p, n, x);
435  } else {
436  std::uninitialized_fill_n(last, n - after, x);
437  set_finish(last + (n - after));
438  append_move(p, last);
439  std::fill_n(p, after, x);
440  }
441  }
442  return begin() + before + n;
443 }
444 
445 template <typename T, typename A>
446 typename vector<T, A>::iterator vector<T, A>::erase(iterator f, iterator l)
447 {
448  iterator i = adobe::move(l, end(), f);
449  for (iterator b(i), e(end()); b != e; ++b) {
450  b->~value_type();
451  }
452  set_finish(i);
453  return f;
454 }
455 
456 template <typename T, typename A>
457 void vector<T, A>::resize(size_type n)
458 {
459  if (n < size()) erase(begin() + n, end());
460  else insert(end(), n - size(), value_type());
461 }
462 
463 template <typename T, typename A>
464 void vector<T, A>::resize(size_type n, const value_type& x)
465 {
466  if (n < size()) erase(begin() + n, end());
467  else insert(end(), n - size(), x);
468 }
469 
470 /*************************************************************************************************/
471 
472 #ifdef ADOBE_STD_SERIALIZATION
473 
474 template <typename T, typename A>
475 std::ostream& operator<<(std::ostream& out, const vector<T, A>& x)
476 {
477  out << begin_sequence;
478 
479  for (typename vector<T, A>::const_iterator first(x.begin()), last(x.end()); first != last; ++first)
480  {
481  out << format(*first);
482  }
483 
484  out << end_sequence;
485 
486  return out;
487 }
488 
489 #endif
490 
491 /*************************************************************************************************/
492 
493 BOOST_STATIC_ASSERT(sizeof(vector<int>) == sizeof(void*));
494 
495 /*************************************************************************************************/
496 
497 } // namespace version_1
498 } // namespace adobe
499 
500 /*************************************************************************************************/
501 
502 ADOBE_NAME_TYPE_1("vector:version_1:adobe", adobe::version_1::vector<T0,
504 ADOBE_NAME_TYPE_2("vector:version_1:adobe", adobe::version_1::vector<T0, T1>)
505 
506 /*************************************************************************************************/
507 
508 namespace boost {
509 
510 template <typename T, typename A>
511 struct has_nothrow_constructor<adobe::version_1::vector<T, A> > : boost::mpl::true_ { };
512 
513 } // namespace boost
514 
518 /*************************************************************************************************/
519 
520 #endif
std::pair< I, I > rotate(I f, I m, I l, std::bidirectional_iterator_tag)
Definition: rotate.hpp:39
friend bool operator<(const vector &x, const vector &y)
Definition: vector.hpp:269
const_iterator end() const
Definition: vector.hpp:198
const T * const_pointer
Definition: vector.hpp:70
BOOST_STATIC_ASSERT(sizeof(string_t)==sizeof(vector< char >))
void resize(size_type n)
Definition: vector.hpp:457
basic_format< T > format(const T &t)
Definition: iomanip.hpp:407
friend void swap(vector &x, vector &y)
Definition: vector.hpp:274
bool equal(InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, BinaryPredicate pred)
Definition: equal.hpp:38
std::size_t size_type
Definition: vector.hpp:65
vector(size_type n)
Definition: vector.hpp:140
std::reverse_iterator< T * > reverse_iterator
Definition: vector.hpp:71
move_from is used for move_ctors.
Definition: move.hpp:306
void swap(adobe::lex_stream_t &, adobe::lex_stream_t &)
Definition: lex_stream.hpp:68
size_type size() const
Definition: vector.hpp:206
const_reference front() const
Definition: vector.hpp:225
reverse_iterator rbegin()
Definition: vector.hpp:200
vector(I f, I l, const allocator_type &a, typename boost::disable_if< boost::is_integral< I > >::type *=0)
Definition: vector.hpp:173
boost::difference_type< I >::type distance(I &range)
Definition: distance.hpp:29
boost::compressed_pair< A, T * > allocate_finish_m
Definition: vector.hpp:79
OutputIterator copy(const InputRange &range, OutputIterator result)
copy implementation
Definition: copy.hpp:43
iterator insert(iterator p, I f, I l, typename boost::disable_if< boost::is_integral< I > >::type *=0)
Definition: vector.hpp:241
const_reverse_iterator rend() const
Definition: vector.hpp:204
format_base::stream_type & end_sequence(format_base::stream_type &os)
std::ptrdiff_t difference_type
Definition: vector.hpp:66
const_reverse_iterator rbegin() const
Definition: vector.hpp:203
iterator insert_move(iterator p, I f, I l)
Definition: vector.hpp:372
const T &() max(const T &a, const T &b)
minmax implementation
Definition: minmax.hpp:86
vector(move_from< vector > x)
Definition: vector.hpp:189
vector & operator=(vector x)
Definition: vector.hpp:220
iterator insert(iterator p, value_type x)
Definition: vector.hpp:237
format_base::stream_type & begin_sequence(format_base::stream_type &os)
vector(size_type n, const value_type &x)
Definition: vector.hpp:146
bool empty() const
Definition: vector.hpp:210
F uninitialized_move(I f, I l, F r)
Similar to std::uninitialized_copy but with move semantics.
Definition: memory.hpp:650
size_type max_size() const
Definition: vector.hpp:207
vector(const vector &x)
Definition: vector.hpp:158
reference operator[](size_type n)
Definition: vector.hpp:212
void reserve(size_type n)
Definition: vector.hpp:404
vector(const allocator_type &a)
Definition: vector.hpp:137
size_type capacity() const
Definition: vector.hpp:209
const_reference operator[](size_type n) const
Definition: vector.hpp:213
void push_back(array_t &v, T x)
Definition: array.hpp:28
const T & const_reference
Definition: vector.hpp:62
allocator_type get_allocator() const
Definition: vector.hpp:191
ADOBE_NAME_TYPE_1("vector:version_1:adobe", adobe::version_1::vector< T0, adobe::capture_allocator< T0 > >) namespace boost
Definition: vector.hpp:502
void swap(vector &x)
Definition: vector.hpp:235
void swap(circular_queue< T > &, circular_queue< T > &)
iterator erase(iterator pos)
Definition: vector.hpp:249
bool lexicographical_compare(const InputRange1 &range1, const InputRange2 &range2)
lexicographical_compare implementation
const T * const_iterator
Definition: vector.hpp:64
const_iterator begin() const
Definition: vector.hpp:197
T::iterator erase(T &x, typename T::iterator f, typename T::iterator l)
Definition: erase_if.hpp:63
vector(size_type n, const value_type &x, const allocator_type &a)
Definition: vector.hpp:152
std::reverse_iterator< const T * > const_reverse_iterator
Definition: vector.hpp:72
vector(I f, I l, typename boost::disable_if< boost::is_integral< I > >::type *=0)
Definition: vector.hpp:169
void construct(T *p)
Definition: memory.hpp:629
void push_back(value_type x)
Definition: vector.hpp:230
reverse_iterator rend()
Definition: vector.hpp:201
ADOBE_NAME_TYPE_2("closed_hash_map:version_1:adobe", adobe::version_1::closed_hash_map< T0, T1, boost::hash< T0 >, std::equal_to< T0 >, adobe::capture_allocator< adobe::pair< T0, T1 > > >)
boost::range_size< Selection >::type size(const Selection &x)
const_reference back() const
Definition: vector.hpp:228
friend bool operator==(const vector &x, const vector &y)
Definition: vector.hpp:259

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google