1// Licensed to the .NET Foundation under one or more agreements.
2// The .NET Foundation licenses this file to you under the MIT license.
3// See the LICENSE file in the project root for more information.
4
5// ==++==
6//
7
8//
9
10//
11// ==--==
12
13/*XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
14XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
15XX XX
16XX vector<T> XX
17XX XX
18XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
19XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
20*/
21
22#pragma once
23
24#include "allocator.h"
25#include "iterator.h"
26
27namespace jitstd
28{
29
30template <typename T, typename Allocator = allocator<T> >
31class vector
32{
33public:
34 typedef Allocator allocator_type;
35 typedef T* pointer;
36 typedef T& reference;
37 typedef const T* const_pointer;
38 typedef const T& const_reference;
39
40 typedef size_t size_type;
41 typedef ptrdiff_t difference_type;
42 typedef T value_type;
43
44 // nested classes
45 class iterator : public jitstd::iterator<random_access_iterator_tag, T>
46 {
47 iterator(T* ptr);
48 public:
49 iterator();
50 iterator(const iterator& it);
51
52 iterator& operator++();
53 iterator& operator++(int);
54 iterator& operator--();
55 iterator& operator--(int);
56 iterator operator+(difference_type n);
57 iterator operator-(difference_type n);
58 size_type operator-(const iterator& that);
59 bool operator==(const iterator& it);
60 bool operator!=(const iterator& it);
61 T& operator*();
62 T* operator&();
63 operator T*();
64
65 private:
66 friend class vector<T, Allocator>;
67 pointer m_pElem;
68 };
69
70 class const_iterator : public jitstd::iterator<random_access_iterator_tag, T>
71 {
72 private:
73 const_iterator(T* ptr);
74 const_iterator();
75 public:
76 const_iterator(const const_iterator& it);
77
78 const_iterator& operator++();
79 const_iterator& operator++(int);
80 const_iterator& operator--();
81 const_iterator& operator--(int);
82 const_iterator operator+(difference_type n);
83 const_iterator operator-(difference_type n);
84 size_type operator-(const const_iterator& that);
85 bool operator==(const const_iterator& it) const;
86 bool operator!=(const const_iterator& it) const;
87 const T& operator*() const;
88 const T* operator&() const;
89 operator const T*() const;
90
91 private:
92 friend class vector<T, Allocator>;
93 pointer m_pElem;
94 };
95
96 class reverse_iterator : public jitstd::iterator<random_access_iterator_tag, T>
97 {
98 private:
99 reverse_iterator(T* ptr);
100 public:
101 reverse_iterator();
102 reverse_iterator(const reverse_iterator& it);
103
104 reverse_iterator& operator++();
105 reverse_iterator& operator++(int);
106 reverse_iterator& operator--();
107 reverse_iterator& operator--(int);
108 reverse_iterator operator+(difference_type n);
109 reverse_iterator operator-(difference_type n);
110 size_type operator-(const reverse_iterator& that);
111 bool operator==(const reverse_iterator& it);
112 bool operator!=(const reverse_iterator& it);
113 T& operator*();
114 T* operator&();
115 operator T*();
116
117 private:
118 friend class vector<T, Allocator>;
119 pointer m_pElem;
120 };
121
122 class const_reverse_iterator : public jitstd::iterator<random_access_iterator_tag, T>
123 {
124 private:
125 const_reverse_iterator(T* ptr);
126 public:
127 const_reverse_iterator();
128 const_reverse_iterator(const const_reverse_iterator& it);
129
130 const_reverse_iterator& operator++();
131 const_reverse_iterator& operator++(int);
132 const_reverse_iterator& operator--();
133 const_reverse_iterator& operator--(int);
134 const_reverse_iterator operator+(difference_type n);
135 const_reverse_iterator operator-(difference_type n);
136 size_type operator-(const const_reverse_iterator& that);
137 bool operator==(const const_reverse_iterator& it) const;
138 bool operator!=(const const_reverse_iterator& it) const;
139 const T& operator*() const;
140 const T* operator&() const;
141 operator const T*() const;
142
143 private:
144 friend class vector<T, Allocator>;
145 pointer m_pElem;
146 };
147
148 // ctors
149 explicit vector(const Allocator& allocator);
150 explicit vector(size_type n, const T& value, const Allocator& allocator);
151
152 template <typename InputIterator>
153 vector(InputIterator first, InputIterator last, const Allocator& allocator);
154
155 // cctors
156 vector(const vector& vec);
157
158 template <typename Alt, typename AltAllocator>
159 explicit vector(const vector<Alt, AltAllocator>& vec);
160
161 // dtor
162 ~vector();
163
164 template <class InputIterator>
165 void assign(InputIterator first, InputIterator last);
166 void assign(size_type size, const T& value);
167
168 const_reference at(size_type n) const;
169 reference at(size_type n);
170
171 reference back();
172 const_reference back() const;
173
174 iterator begin();
175 const_iterator begin() const;
176 const_iterator cbegin() const;
177
178 size_type capacity() const;
179
180 void clear();
181 bool empty() const;
182
183 iterator end();
184 const_iterator end() const;
185 const_iterator cend() const;
186
187 iterator erase(iterator position);
188 iterator erase(iterator first, iterator last);
189
190 reference front();
191 const_reference front() const;
192
193 allocator_type get_allocator() const;
194
195 iterator insert(iterator position, const T& value);
196 void insert(iterator position, size_type size, const T& value);
197
198 template <typename InputIterator>
199 void insert(iterator position, InputIterator first, InputIterator last);
200
201 size_type max_size() const;
202
203 vector& operator=(const vector& vec);
204 template <typename Alt, typename AltAllocator>
205 vector<T, Allocator>& operator=(const vector<Alt, AltAllocator>& vec);
206
207 reference operator[](size_type n);
208 const_reference operator[](size_type n) const;
209
210 void pop_back();
211 void push_back(const T& value);
212
213 reverse_iterator rbegin();
214 const_reverse_iterator rbegin() const;
215
216 reverse_iterator rend();
217 const_reverse_iterator rend() const;
218
219 void reserve(size_type n);
220
221 void resize(size_type sz, const T&);
222
223 size_type size() const;
224
225 void swap(vector<T, Allocator>& vec);
226
227private:
228
229 typename Allocator::template rebind<T>::allocator m_allocator;
230 T* m_pArray;
231 size_type m_nSize;
232 size_type m_nCapacity;
233
234 inline
235 bool ensure_capacity(size_type capacity);
236
237 template <typename InputIterator>
238 void construct_helper(InputIterator first, InputIterator last, forward_iterator_tag);
239 template <typename InputIterator>
240 void construct_helper(InputIterator first, InputIterator last, int_not_an_iterator_tag);
241 void construct_helper(size_type size, const T& value);
242
243 template <typename InputIterator>
244 void insert_helper(iterator iter, InputIterator first, InputIterator last, forward_iterator_tag);
245 template <typename InputIterator>
246 void insert_helper(iterator iter, InputIterator first, InputIterator last, int_not_an_iterator_tag);
247 void insert_elements_helper(iterator iter, size_type size, const T& value);
248
249 template <typename InputIterator>
250 void assign_helper(InputIterator first, InputIterator last, forward_iterator_tag);
251 template <typename InputIterator>
252 void assign_helper(InputIterator first, InputIterator last, int_not_an_iterator_tag);
253
254 template <typename Alt, typename AltAllocator>
255 friend class vector;
256};
257
258}// namespace jit_std
259
260
261
262// Implementation of vector.
263
264namespace jitstd
265{
266
267namespace
268{
269
270template <typename InputIterator>
271size_t iterator_difference(InputIterator first, const InputIterator& last)
272{
273 size_t size = 0;
274 for (; first != last; ++first, ++size);
275 return size;
276}
277
278}
279
280
281template <typename T, typename Allocator>
282vector<T, Allocator>::vector(const Allocator& allocator)
283 : m_allocator(allocator)
284 , m_pArray(nullptr)
285 , m_nSize(0)
286 , m_nCapacity(0)
287{
288}
289
290template <typename T, typename Allocator>
291vector<T, Allocator>::vector(size_type size, const T& value, const Allocator& allocator)
292 : m_allocator(allocator)
293 , m_pArray(NULL)
294 , m_nSize(0)
295 , m_nCapacity(0)
296{
297 construct_helper(size, value);
298}
299
300template <typename T, typename Allocator>
301template <typename InputIterator>
302vector<T, Allocator>::vector(InputIterator first, InputIterator last, const Allocator& allocator)
303 : m_allocator(allocator)
304 , m_pArray(NULL)
305 , m_nSize(0)
306 , m_nCapacity(0)
307{
308 construct_helper(first, last, iterator_traits<InputIterator>::iterator_category());
309}
310
311template <typename T, typename Allocator>
312template <typename Alt, typename AltAllocator>
313vector<T, Allocator>::vector(const vector<Alt, AltAllocator>& vec)
314 : m_allocator(vec.m_allocator)
315 , m_pArray(NULL)
316 , m_nSize(0)
317 , m_nCapacity(0)
318{
319 ensure_capacity(vec.m_nSize);
320 for (size_type i = 0, j = 0; i < vec.m_nSize; ++i, ++j)
321 {
322 new (m_pArray + i, placement_t()) T((T) vec.m_pArray[j]);
323 }
324
325 m_nSize = vec.m_nSize;
326}
327
328template <typename T, typename Allocator>
329vector<T, Allocator>::vector(const vector<T, Allocator>& vec)
330 : m_allocator(vec.m_allocator)
331 , m_pArray(NULL)
332 , m_nSize(0)
333 , m_nCapacity(0)
334{
335 ensure_capacity(vec.m_nSize);
336 for (size_type i = 0, j = 0; i < vec.m_nSize; ++i, ++j)
337 {
338 new (m_pArray + i, placement_t()) T(vec.m_pArray[j]);
339 }
340
341 m_nSize = vec.m_nSize;
342}
343
344
345template <typename T, typename Allocator>
346vector<T, Allocator>::~vector()
347{
348 for (size_type i = 0; i < m_nSize; ++i)
349 {
350 m_pArray[i].~T();
351 }
352 m_allocator.deallocate(m_pArray, m_nCapacity);
353 m_nSize = 0;
354 m_nCapacity = 0;
355}
356
357
358// public methods
359
360template <typename T, typename Allocator>
361template <typename InputIterator>
362void vector<T, Allocator>::assign(InputIterator first, InputIterator last)
363{
364 construct_helper(first, last, iterator_traits<InputIterator>::iterator_category());
365}
366
367template <typename T, typename Allocator>
368void vector<T, Allocator>::assign(size_type size, const T& value)
369{
370 ensure_capacity(size);
371 for (int i = 0; i < size; ++i)
372 {
373 m_pArray[i] = value;
374 }
375 m_nSize = size;
376}
377
378template <typename T, typename Allocator>
379typename vector<T, Allocator>::const_reference
380 vector<T, Allocator>::at(size_type i) const
381{
382 return operator[](i);
383}
384
385template <typename T, typename Allocator>
386typename vector<T, Allocator>::reference
387 vector<T, Allocator>::at(size_type i)
388{
389 return operator[](i);
390}
391
392template <typename T, typename Allocator>
393typename vector<T, Allocator>::reference
394 vector<T, Allocator>::back()
395{
396 return operator[](m_nSize - 1);
397}
398
399template <typename T, typename Allocator>
400typename vector<T, Allocator>::const_reference
401 vector<T, Allocator>::back() const
402{
403 return operator[](m_nSize - 1);
404}
405
406template <typename T, typename Allocator>
407typename vector<T, Allocator>::iterator
408 vector<T, Allocator>::begin()
409{
410 return iterator(m_pArray);
411}
412
413template <typename T, typename Allocator>
414typename vector<T, Allocator>::const_iterator
415 vector<T, Allocator>::begin() const
416{
417 return const_iterator(m_pArray);
418}
419
420template <typename T, typename Allocator>
421typename vector<T, Allocator>::const_iterator
422 vector<T, Allocator>::cbegin() const
423{
424 return const_iterator(m_pArray);
425}
426
427template <typename T, typename Allocator>
428typename vector<T, Allocator>::size_type
429 vector<T, Allocator>::capacity() const
430{
431 return m_nCapacity;
432}
433
434
435template <typename T, typename Allocator>
436void vector<T, Allocator>::clear()
437{
438 for (size_type i = 0; i < m_nSize; ++i)
439 {
440 m_pArray[i].~T();
441 }
442 m_nSize = 0;
443}
444
445template <typename T, typename Allocator>
446bool vector<T, Allocator>::empty() const
447{
448 return m_nSize == 0;
449}
450
451template <typename T, typename Allocator>
452typename vector<T, Allocator>::iterator vector<T, Allocator>::end()
453{
454 return iterator(m_pArray + m_nSize);
455}
456
457template <typename T, typename Allocator>
458typename vector<T, Allocator>::const_iterator
459 vector<T, Allocator>::end() const
460{
461 return const_iterator(m_pArray + m_nSize);
462}
463
464template <typename T, typename Allocator>
465typename vector<T, Allocator>::const_iterator vector<T, Allocator>::cend() const
466{
467 return const_iterator(m_pArray + m_nSize);
468}
469
470template <typename T, typename Allocator>
471typename vector<T, Allocator>::iterator
472 vector<T, Allocator>::erase(
473 typename vector<T, Allocator>::iterator position)
474{
475 return erase(position, position + 1);
476}
477
478template <typename T, typename Allocator>
479typename vector<T, Allocator>::iterator
480 vector<T, Allocator>::erase(
481 typename vector<T, Allocator>::iterator first,
482 typename vector<T, Allocator>::iterator last)
483{
484 assert(m_nSize > 0);
485 assert(first.m_pElem >= m_pArray);
486 assert(last.m_pElem >= m_pArray);
487 assert(first.m_pElem <= m_pArray + m_nSize);
488 assert(last.m_pElem <= m_pArray + m_nSize);
489 assert(last.m_pElem > first.m_pElem);
490
491 pointer fptr = first.m_pElem;
492 pointer lptr = last.m_pElem;
493 pointer eptr = m_pArray + m_nSize;
494 for (; lptr != eptr; ++lptr, fptr++)
495 {
496 (*fptr).~T();
497 *fptr = *lptr;
498 }
499 m_nSize -= (size_type)(lptr - fptr);
500 return first;
501}
502
503template <typename T, typename Allocator>
504typename vector<T, Allocator>::reference
505 vector<T, Allocator>::front()
506{
507 return operator[](0);
508}
509
510template <typename T, typename Allocator>
511typename vector<T, Allocator>::const_reference
512 vector<T, Allocator>::front() const
513{
514 return operator[](0);
515}
516
517template <typename T, typename Allocator>
518typename vector<T, Allocator>::allocator_type
519 vector<T, Allocator>::get_allocator() const
520{
521 return m_allocator;
522}
523
524template <typename T, typename Allocator>
525typename vector<T, Allocator>::iterator
526 vector<T, Allocator>::insert(
527 typename vector<T, Allocator>::iterator iter,
528 const T& value)
529{
530 size_type pos = (size_type) (iter.m_pElem - m_pArray);
531 insert_elements_helper(iter, 1, value);
532 return iterator(m_pArray + pos);
533}
534
535template <typename T, typename Allocator>
536void vector<T, Allocator>::insert(
537 iterator iter,
538 size_type size,
539 const T& value)
540{
541 insert_elements_helper(iter, size, value);
542}
543
544template <typename T, typename Allocator>
545template <typename InputIterator>
546void vector<T, Allocator>::insert(
547 iterator iter,
548 InputIterator first,
549 InputIterator last)
550{
551 insert_helper(iter, first, last, iterator_traits<InputIterator>::iterator_category());
552}
553
554template <typename T, typename Allocator>
555typename vector<T, Allocator>::size_type
556 vector<T, Allocator>::max_size() const
557{
558 return ((size_type) -1) >> 1;
559}
560
561template <typename T, typename Allocator>
562template <typename Alt, typename AltAllocator>
563vector<T, Allocator>& vector<T, Allocator>::operator=(const vector<Alt, AltAllocator>& vec)
564{
565 // We'll not observe copy-on-write for now.
566 m_allocator = vec.m_allocator;
567 ensure_capacity(vec.m_nSize);
568 m_nSize = vec.m_nSize;
569 for (size_type i = 0; i < m_nSize; ++i)
570 {
571 m_pArray[i] = (T) vec.m_pArray[i];
572 }
573 return *this;
574}
575
576template <typename T, typename Allocator>
577vector<T, Allocator>& vector<T, Allocator>::operator=(const vector<T, Allocator>& vec)
578{
579 // We'll not observe copy-on-write for now.
580 m_allocator = vec.m_allocator;
581 ensure_capacity(vec.m_nSize);
582 m_nSize = vec.m_nSize;
583 for (size_type i = 0; i < m_nSize; ++i)
584 {
585 new (m_pArray + i, placement_t()) T(vec.m_pArray[i]);
586 }
587 return *this;
588}
589
590
591template <typename T, typename Allocator>
592typename vector<T, Allocator>::reference vector<T, Allocator>::operator[](size_type n)
593{
594 return m_pArray[n];
595}
596
597template <typename T, typename Allocator>
598typename vector<T, Allocator>::const_reference
599 vector<T, Allocator>::operator[](size_type n) const
600{
601 return m_pArray[n];
602}
603
604template <typename T, typename Allocator>
605void vector<T, Allocator>::pop_back()
606{
607 m_pArray[m_nSize - 1].~T();
608 --m_nSize;
609}
610
611template <typename T, typename Allocator>
612void vector<T, Allocator>::push_back(const T& value)
613{
614 ensure_capacity(m_nSize + 1);
615 new (m_pArray + m_nSize, placement_t()) T(value);
616 ++m_nSize;
617}
618
619template <typename T, typename Allocator>
620typename vector<T, Allocator>::reverse_iterator vector<T, Allocator>::rbegin()
621{
622 return reverse_iterator(m_pArray + m_nSize - 1);
623}
624
625template <typename T, typename Allocator>
626typename vector<T, Allocator>::const_reverse_iterator
627 vector<T, Allocator>::rbegin() const
628{
629 return const_reverse_iterator(m_pArray + m_nSize - 1);
630}
631
632template <typename T, typename Allocator>
633typename vector<T, Allocator>::reverse_iterator
634 vector<T, Allocator>::rend()
635{
636 return reverse_iterator(m_pArray - 1);
637}
638
639template <typename T, typename Allocator>
640typename vector<T, Allocator>::const_reverse_iterator
641 vector<T, Allocator>::rend() const
642{
643 return const_reverse_iterator(m_pArray - 1);
644}
645
646template <typename T, typename Allocator>
647void vector<T, Allocator>::reserve(size_type n)
648{
649 ensure_capacity(n);
650}
651
652template <typename T, typename Allocator>
653void vector<T, Allocator>::resize(
654 size_type sz,
655 const T& c)
656{
657 for (; m_nSize > sz; m_nSize--)
658 {
659 m_pArray[m_nSize - 1].~T();
660 }
661 ensure_capacity(sz);
662 for (; m_nSize < sz; m_nSize++)
663 {
664 new (m_pArray + m_nSize, placement_t()) T(c);
665 }
666}
667
668template <typename T, typename Allocator>
669typename vector<T, Allocator>::size_type vector<T, Allocator>::size() const
670{
671 return m_nSize;
672}
673
674template <typename T, typename Allocator>
675void vector<T, Allocator>::swap(vector<T, Allocator>& vec)
676{
677 jitstd::swap(m_pArray, vec.m_pArray);
678 jitstd::swap(m_nSize, vec.m_nSize);
679 jitstd::swap(m_nCapacity, vec.m_nCapacity);
680 jitstd::swap(m_nCapacity, vec.m_nCapacity);
681 jitstd::swap(m_allocator, vec.m_allocator);
682}
683
684// =======================================================================================
685
686template <typename T, typename Allocator>
687void vector<T, Allocator>::construct_helper(size_type size, const T& value)
688{
689 ensure_capacity(size);
690
691 for (size_type i = 0; i < size; ++i)
692 {
693 new (m_pArray + i, placement_t()) T(value);
694 }
695
696 m_nSize = size;
697}
698
699
700template <typename T, typename Allocator>
701template <typename InputIterator>
702void vector<T, Allocator>::construct_helper(InputIterator first, InputIterator last, int_not_an_iterator_tag)
703{
704 construct_helper(first, last);
705}
706
707template <typename T, typename Allocator>
708template <typename InputIterator>
709void vector<T, Allocator>::construct_helper(InputIterator first, InputIterator last, forward_iterator_tag)
710{
711 size_type size = iterator_difference(first, last);
712
713 ensure_capacity(size);
714 for (size_type i = 0; i < size; ++i)
715 {
716 new (m_pArray + i, placement_t()) T(*first);
717 first++;
718 }
719
720 m_nSize = size;
721}
722
723// =======================================================================================
724
725template <typename T, typename Allocator>
726void vector<T, Allocator>::insert_elements_helper(iterator iter, size_type size, const T& value)
727{
728 assert(size < max_size());
729
730 // m_pElem could be NULL then m_pArray would be NULL too.
731 size_type pos = iter.m_pElem - m_pArray;
732
733 assert(pos <= m_nSize); // <= could insert at end.
734 assert(pos >= 0);
735
736 ensure_capacity(m_nSize + size);
737
738 for (int src = m_nSize - 1, dst = m_nSize + size - 1; src >= (int) pos; --src, --dst)
739 {
740 m_pArray[dst] = m_pArray[src];
741 }
742
743 for (size_type i = 0; i < size; ++i)
744 {
745 new (m_pArray + pos + i, placement_t()) T(value);
746 }
747
748 m_nSize += size;
749}
750
751template <typename T, typename Allocator>
752template <typename InputIterator>
753void vector<T, Allocator>::insert_helper(iterator iter, InputIterator first, InputIterator last, int_not_an_iterator_tag)
754{
755 insert_elements_helper(iter, first, last);
756}
757
758template <typename T, typename Allocator>
759template <typename InputIterator>
760void vector<T, Allocator>::insert_helper(iterator iter, InputIterator first, InputIterator last, forward_iterator_tag)
761{
762 // m_pElem could be NULL then m_pArray would be NULL too.
763 size_type pos = iter.m_pElem - m_pArray;
764
765 assert(pos <= m_nSize); // <= could insert at end.
766 assert(pos >= 0);
767
768 size_type size = iterator_difference(first, last);
769 assert(size < max_size());
770
771 ensure_capacity(m_nSize + size);
772
773 pointer lst = m_pArray + m_nSize + size - 1;
774 for (size_type i = pos; i < m_nSize; ++i)
775 {
776 *lst-- = m_pArray[i];
777 }
778 for (size_type i = 0; i < size; ++i, ++first)
779 {
780 m_pArray[pos + i] = *first;
781 }
782
783 m_nSize += size;
784}
785
786// =======================================================================================
787
788template <typename T, typename Allocator>
789template <typename InputIterator>
790void vector<T, Allocator>::assign_helper(InputIterator first, InputIterator last, forward_iterator_tag)
791{
792 size_type size = iterator_difference(first, last);
793
794 ensure_capacity(size);
795 for (size_type i = 0; i < size; ++i)
796 {
797 m_pArray[i] = *first;
798 first++;
799 }
800
801 m_nSize = size;
802}
803
804template <typename T, typename Allocator>
805template <typename InputIterator>
806void vector<T, Allocator>::assign_helper(InputIterator first, InputIterator last, int_not_an_iterator_tag)
807{
808 assign_helper(first, last);
809}
810
811// =======================================================================================
812
813template <typename T, typename Allocator>
814bool vector<T, Allocator>::ensure_capacity(size_type newCap)
815{
816 if (newCap <= m_nCapacity)
817 {
818 return false;
819 }
820
821 // Double the alloc capacity based on size.
822 size_type allocCap = m_nSize * 2;
823
824 // Is it still not sufficient?
825 if (allocCap < newCap)
826 {
827 allocCap = newCap;
828 }
829
830 // Allocate space.
831 pointer ptr = m_allocator.allocate(allocCap);
832
833 // Copy over.
834 for (size_type i = 0; i < m_nSize; ++i)
835 {
836 new (ptr + i, placement_t()) T(m_pArray[i]);
837 }
838
839 // Deallocate currently allocated space.
840 m_allocator.deallocate(m_pArray, m_nCapacity);
841
842 // Update the pointers and capacity;
843 m_pArray = ptr;
844 m_nCapacity = allocCap;
845 return true;
846}
847
848} // end of namespace jitstd.
849
850
851
852// Implementation of vector iterators
853
854namespace jitstd
855{
856
857// iterator
858template <typename T, typename Allocator>
859vector<T, Allocator>::iterator::iterator()
860 : m_pElem(NULL)
861{
862}
863
864template <typename T, typename Allocator>
865vector<T, Allocator>::iterator::iterator(T* ptr)
866 : m_pElem(ptr)
867{
868}
869
870template <typename T, typename Allocator>
871vector<T, Allocator>::iterator::iterator(const iterator& it)
872 : m_pElem(it.m_pElem)
873{
874}
875
876
877template <typename T, typename Allocator>
878typename vector<T, Allocator>::iterator& vector<T, Allocator>::iterator::operator++()
879{
880 ++m_pElem;
881 return *this;
882}
883
884template <typename T, typename Allocator>
885typename vector<T, Allocator>::iterator& vector<T, Allocator>::iterator::operator++(int)
886{
887 ++m_pElem;
888 return *this;
889}
890
891template <typename T, typename Allocator>
892typename vector<T, Allocator>::iterator& vector<T, Allocator>::iterator::operator--()
893{
894 --m_pElem;
895 return *this;
896}
897
898template <typename T, typename Allocator>
899typename vector<T, Allocator>::iterator& vector<T, Allocator>::iterator::operator--(int)
900{
901 --m_pElem;
902 return *this;
903}
904
905template <typename T, typename Allocator>
906typename vector<T, Allocator>::iterator vector<T, Allocator>::iterator::operator+(difference_type n)
907{
908 return iterator(m_pElem + n);
909}
910
911template <typename T, typename Allocator>
912typename vector<T, Allocator>::iterator vector<T, Allocator>::iterator::operator-(difference_type n)
913{
914 return iterator(m_pElem - n);
915}
916
917template <typename T, typename Allocator>
918typename vector<T, Allocator>::size_type
919 vector<T, Allocator>::iterator::operator-(
920 const typename vector<T, Allocator>::iterator& that)
921{
922 return m_pElem - that.m_pElem;
923}
924
925template <typename T, typename Allocator>
926bool vector<T, Allocator>::iterator::operator==(const iterator& it)
927{
928 return (m_pElem == it.m_pElem);
929}
930
931template <typename T, typename Allocator>
932bool vector<T, Allocator>::iterator::operator!=(const iterator& it)
933{
934 return !operator==(it);
935}
936
937template <typename T, typename Allocator>
938T& vector<T, Allocator>::iterator::operator*()
939{
940 return *m_pElem;
941}
942
943template <typename T, typename Allocator>
944T* vector<T, Allocator>::iterator::operator&()
945{
946 return &m_pElem;
947}
948
949template <typename T, typename Allocator>
950vector<T, Allocator>::iterator::operator T*()
951{
952 return &m_pElem;
953}
954
955// const_iterator
956template <typename T, typename Allocator>
957vector<T, Allocator>::const_iterator::const_iterator()
958 : m_pElem(NULL)
959{
960}
961
962template <typename T, typename Allocator>
963vector<T, Allocator>::const_iterator::const_iterator(T* ptr)
964 : m_pElem(ptr)
965{
966}
967
968template <typename T, typename Allocator>
969vector<T, Allocator>::const_iterator::const_iterator(const const_iterator& it)
970 : m_pElem(it.m_pElem)
971{
972}
973
974
975template <typename T, typename Allocator>
976typename vector<T, Allocator>::const_iterator& vector<T, Allocator>::const_iterator::operator++()
977{
978 ++m_pElem;
979 return *this;
980}
981
982template <typename T, typename Allocator>
983typename vector<T, Allocator>::const_iterator& vector<T, Allocator>::const_iterator::operator++(int)
984{
985 ++m_pElem;
986 return *this;
987}
988
989template <typename T, typename Allocator>
990typename vector<T, Allocator>::const_iterator& vector<T, Allocator>::const_iterator::operator--()
991{
992 --m_pElem;
993 return *this;
994}
995
996template <typename T, typename Allocator>
997typename vector<T, Allocator>::const_iterator& vector<T, Allocator>::const_iterator::operator--(int)
998{
999 --m_pElem;
1000 return *this;
1001}
1002
1003template <typename T, typename Allocator>
1004typename vector<T, Allocator>::const_iterator vector<T, Allocator>::const_iterator::operator+(difference_type n)
1005{
1006 return const_iterator(m_pElem + n);
1007}
1008
1009template <typename T, typename Allocator>
1010typename vector<T, Allocator>::const_iterator vector<T, Allocator>::const_iterator::operator-(difference_type n)
1011{
1012 return const_iterator(m_pElem - n);
1013}
1014
1015template <typename T, typename Allocator>
1016typename vector<T, Allocator>::size_type
1017 vector<T, Allocator>::const_iterator::operator-(
1018 const typename vector<T, Allocator>::const_iterator& that)
1019{
1020 return m_pElem - that.m_pElem;
1021}
1022
1023template <typename T, typename Allocator>
1024bool vector<T, Allocator>::const_iterator::operator==(const const_iterator& it) const
1025{
1026 return (m_pElem == it.m_pElem);
1027}
1028
1029template <typename T, typename Allocator>
1030bool vector<T, Allocator>::const_iterator::operator!=(const const_iterator& it) const
1031{
1032 return !operator==(it);
1033}
1034
1035template <typename T, typename Allocator>
1036const T& vector<T, Allocator>::const_iterator::operator*() const
1037{
1038 return *m_pElem;
1039}
1040
1041
1042template <typename T, typename Allocator>
1043const T* vector<T, Allocator>::const_iterator::operator&() const
1044{
1045 return &m_pElem;
1046}
1047
1048template <typename T, typename Allocator>
1049vector<T, Allocator>::const_iterator::operator const T*() const
1050{
1051 return &m_pElem;
1052}
1053
1054
1055// reverse_iterator
1056template <typename T, typename Allocator>
1057vector<T, Allocator>::reverse_iterator::reverse_iterator()
1058 : m_pElem(NULL)
1059{
1060}
1061
1062template <typename T, typename Allocator>
1063vector<T, Allocator>::reverse_iterator::reverse_iterator(T* ptr)
1064 : m_pElem(ptr)
1065{
1066}
1067
1068template <typename T, typename Allocator>
1069vector<T, Allocator>::reverse_iterator::reverse_iterator(const reverse_iterator& it)
1070 : m_pElem(it.m_pElem)
1071{
1072}
1073
1074
1075template <typename T, typename Allocator>
1076typename vector<T, Allocator>::reverse_iterator& vector<T, Allocator>::reverse_iterator::operator++()
1077{
1078 --m_pElem;
1079 return *this;
1080}
1081
1082template <typename T, typename Allocator>
1083typename vector<T, Allocator>::reverse_iterator& vector<T, Allocator>::reverse_iterator::operator++(int)
1084{
1085 --m_pElem;
1086 return *this;
1087}
1088
1089template <typename T, typename Allocator>
1090typename vector<T, Allocator>::reverse_iterator& vector<T, Allocator>::reverse_iterator::operator--()
1091{
1092 ++m_pElem;
1093 return *this;
1094}
1095
1096template <typename T, typename Allocator>
1097typename vector<T, Allocator>::reverse_iterator& vector<T, Allocator>::reverse_iterator::operator--(int)
1098{
1099 ++m_pElem;
1100 return *this;
1101}
1102
1103template <typename T, typename Allocator>
1104typename vector<T, Allocator>::reverse_iterator vector<T, Allocator>::reverse_iterator::operator+(difference_type n)
1105{
1106 return reverse_iterator(m_pElem + n);
1107}
1108
1109template <typename T, typename Allocator>
1110typename vector<T, Allocator>::reverse_iterator vector<T, Allocator>::reverse_iterator::operator-(difference_type n)
1111{
1112 return reverse_iterator(m_pElem - n);
1113}
1114
1115template <typename T, typename Allocator>
1116typename vector<T, Allocator>::size_type
1117 vector<T, Allocator>::reverse_iterator::operator-(
1118 const typename vector<T, Allocator>::reverse_iterator& that)
1119{
1120 return m_pElem - that.m_pElem;
1121}
1122
1123template <typename T, typename Allocator>
1124bool vector<T, Allocator>::reverse_iterator::operator==(const reverse_iterator& it)
1125{
1126 return (m_pElem == it.m_pElem);
1127}
1128
1129template <typename T, typename Allocator>
1130bool vector<T, Allocator>::reverse_iterator::operator!=(const reverse_iterator& it)
1131{
1132 return !operator==(it);
1133}
1134
1135template <typename T, typename Allocator>
1136T& vector<T, Allocator>::reverse_iterator::operator*()
1137{
1138 return *m_pElem;
1139}
1140
1141template <typename T, typename Allocator>
1142T* vector<T, Allocator>::reverse_iterator::operator&()
1143{
1144 return &m_pElem;
1145}
1146
1147template <typename T, typename Allocator>
1148vector<T, Allocator>::reverse_iterator::operator T*()
1149{
1150 return &m_pElem;
1151}
1152
1153// const_reverse_iterator
1154template <typename T, typename Allocator>
1155vector<T, Allocator>::const_reverse_iterator::const_reverse_iterator()
1156 : m_pElem(NULL)
1157{
1158}
1159
1160template <typename T, typename Allocator>
1161vector<T, Allocator>::const_reverse_iterator::const_reverse_iterator(T* ptr)
1162 : m_pElem(ptr)
1163{
1164}
1165
1166template <typename T, typename Allocator>
1167vector<T, Allocator>::const_reverse_iterator::const_reverse_iterator(const const_reverse_iterator& it)
1168 : m_pElem(it.m_pElem)
1169{
1170}
1171
1172
1173template <typename T, typename Allocator>
1174typename vector<T, Allocator>::const_reverse_iterator& vector<T, Allocator>::const_reverse_iterator::operator++()
1175{
1176 --m_pElem;
1177 return *this;
1178}
1179
1180template <typename T, typename Allocator>
1181typename vector<T, Allocator>::const_reverse_iterator& vector<T, Allocator>::const_reverse_iterator::operator++(int)
1182{
1183 --m_pElem;
1184 return *this;
1185}
1186
1187template <typename T, typename Allocator>
1188typename vector<T, Allocator>::const_reverse_iterator& vector<T, Allocator>::const_reverse_iterator::operator--()
1189{
1190 ++m_pElem;
1191 return *this;
1192}
1193
1194template <typename T, typename Allocator>
1195typename vector<T, Allocator>::const_reverse_iterator& vector<T, Allocator>::const_reverse_iterator::operator--(int)
1196{
1197 ++m_pElem;
1198 return *this;
1199}
1200
1201template <typename T, typename Allocator>
1202typename vector<T, Allocator>::const_reverse_iterator vector<T, Allocator>::const_reverse_iterator::operator+(difference_type n)
1203{
1204 return const_reverse_iterator(m_pElem + n);
1205}
1206
1207template <typename T, typename Allocator>
1208typename vector<T, Allocator>::const_reverse_iterator vector<T, Allocator>::const_reverse_iterator::operator-(difference_type n)
1209{
1210 return const_reverse_iterator(m_pElem - n);
1211}
1212
1213template <typename T, typename Allocator>
1214typename vector<T, Allocator>::size_type
1215 vector<T, Allocator>::const_reverse_iterator::operator-(
1216 const typename vector<T, Allocator>::const_reverse_iterator& that)
1217{
1218 return m_pElem - that.m_pElem;
1219}
1220
1221template <typename T, typename Allocator>
1222bool vector<T, Allocator>::const_reverse_iterator::operator==(const const_reverse_iterator& it) const
1223{
1224 return (m_pElem == it.m_pElem);
1225}
1226
1227template <typename T, typename Allocator>
1228bool vector<T, Allocator>::const_reverse_iterator::operator!=(const const_reverse_iterator& it) const
1229{
1230 return !operator==(it);
1231}
1232
1233template <typename T, typename Allocator>
1234const T& vector<T, Allocator>::const_reverse_iterator::operator*() const
1235{
1236 return *m_pElem;
1237}
1238
1239template <typename T, typename Allocator>
1240const T* vector<T, Allocator>::const_reverse_iterator::operator&() const
1241{
1242 return &m_pElem;
1243}
1244
1245template <typename T, typename Allocator>
1246vector<T, Allocator>::const_reverse_iterator::operator const T*() const
1247{
1248 return &m_pElem;
1249}
1250
1251}
1252