_deque.h 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414
  1. /*
  2. *
  3. * Copyright (c) 1994
  4. * Hewlett-Packard Company
  5. *
  6. * Copyright (c) 1996,1997
  7. * Silicon Graphics Computer Systems, Inc.
  8. *
  9. * Copyright (c) 1997
  10. * Moscow Center for SPARC Technology
  11. *
  12. * Copyright (c) 1999
  13. * Boris Fomitchev
  14. *
  15. * This material is provided "as is", with absolutely no warranty expressed
  16. * or implied. Any use is at your own risk.
  17. *
  18. * Permission to use or copy this software for any purpose is hereby granted
  19. * without fee, provided the above notices are retained on all copies.
  20. * Permission to modify the code and to distribute modified code is granted,
  21. * provided the above notices are retained, and a notice that the code was
  22. * modified is included with the above copyright notice.
  23. *
  24. */
  25. /* NOTE: This is an internal header file, included by other STL headers.
  26. * You should not attempt to use it directly.
  27. */
  28. #ifndef _STLP_INTERNAL_DBG_DEQUE_H
  29. #define _STLP_INTERNAL_DBG_DEQUE_H
  30. #ifndef _STLP_DBG_ITERATOR_H
  31. # include <stl/debug/_iterator.h>
  32. #endif
  33. #define _STLP_NON_DBG_DEQUE _STLP_PRIV _STLP_NON_DBG_NAME(deque) <_Tp,_Alloc>
  34. _STLP_BEGIN_NAMESPACE
  35. #if defined (_STLP_DEBUG_USE_DISTINCT_VALUE_TYPE_HELPERS)
  36. template <class _Tp, class _Alloc>
  37. inline _Tp* value_type(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_DEQUE >&)
  38. { return (_Tp*)0; }
  39. template <class _Tp, class _Alloc>
  40. inline random_access_iterator_tag iterator_category(const _STLP_PRIV _DBG_iter_base< _STLP_NON_DBG_DEQUE >&)
  41. { return random_access_iterator_tag(); }
  42. #endif
  43. template <class _Tp, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_Tp>) >
  44. class deque :
  45. #if !defined (__DMC__)
  46. private
  47. #endif
  48. _STLP_PRIV __construct_checker<_STLP_NON_DBG_DEQUE >
  49. #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND)
  50. , public __stlport_class<deque<_Tp, _Alloc> >
  51. #endif
  52. {
  53. typedef deque<_Tp,_Alloc> _Self;
  54. typedef _STLP_NON_DBG_DEQUE _Base;
  55. typedef _STLP_PRIV __construct_checker<_STLP_NON_DBG_DEQUE > _ConstructCheck;
  56. public:
  57. // Basic types
  58. __IMPORT_CONTAINER_TYPEDEFS(_Base)
  59. // Iterators
  60. typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_Nonconst_traits<value_type> > > iterator;
  61. typedef _STLP_PRIV _DBG_iter<_Base, _STLP_PRIV _DbgTraits<_Const_traits<value_type> > > const_iterator;
  62. _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
  63. protected:
  64. _Base _M_non_dbg_impl;
  65. _STLP_PRIV __owned_list _M_iter_list;
  66. void _Invalidate_all()
  67. { _M_iter_list._Invalidate_all(); }
  68. void _Invalidate_iterator(const iterator& __it)
  69. { _STLP_PRIV __invalidate_iterator(&_M_iter_list,__it); }
  70. void _Invalidate_iterators(const iterator& __first, const iterator& __last)
  71. { _STLP_PRIV __invalidate_range(&_M_iter_list, __first, __last); }
  72. public:
  73. // Basic accessors
  74. allocator_type get_allocator() const { return _M_non_dbg_impl.get_allocator(); }
  75. iterator begin() { return iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
  76. iterator end() { return iterator(&_M_iter_list, _M_non_dbg_impl.end()); }
  77. const_iterator begin() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.begin()); }
  78. const_iterator end() const { return const_iterator(&_M_iter_list, _M_non_dbg_impl.end()); }
  79. reverse_iterator rbegin() { return reverse_iterator(end()); }
  80. reverse_iterator rend() { return reverse_iterator(begin()); }
  81. const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
  82. const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
  83. reference operator[](size_type __n) {
  84. _STLP_VERBOSE_ASSERT(__n < size(), _StlMsg_OUT_OF_BOUNDS)
  85. return _M_non_dbg_impl[__n];
  86. }
  87. const_reference operator[](size_type __n) const {
  88. _STLP_VERBOSE_ASSERT(__n < size(), _StlMsg_OUT_OF_BOUNDS)
  89. return _M_non_dbg_impl[__n];
  90. }
  91. reference at(size_type __n) { return _M_non_dbg_impl.at(__n); }
  92. const_reference at(size_type __n) const { return _M_non_dbg_impl.at(__n); }
  93. reference front() {
  94. _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
  95. return *begin();
  96. }
  97. const_reference front() const {
  98. _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
  99. return *begin();
  100. }
  101. reference back() {
  102. _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
  103. return *(--end());
  104. }
  105. const_reference back() const {
  106. _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
  107. return *(--end());
  108. }
  109. // Constructor, destructor.
  110. explicit deque(const allocator_type& __a = allocator_type()) :
  111. _M_non_dbg_impl(__a), _M_iter_list(&_M_non_dbg_impl) {}
  112. deque(const _Self& __x) :
  113. _ConstructCheck(__x), _M_non_dbg_impl(__x._M_non_dbg_impl),
  114. _M_iter_list(&_M_non_dbg_impl) {}
  115. #if !defined(_STLP_DONT_SUP_DFLT_PARAM)
  116. explicit deque(size_type __n, const value_type& __x = _Tp(),
  117. #else
  118. deque(size_type __n, const value_type& __x,
  119. #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
  120. const allocator_type& __a = allocator_type()) :
  121. _M_non_dbg_impl(__n, __x, __a), _M_iter_list(&_M_non_dbg_impl) {}
  122. #if defined (_STLP_DONT_SUP_DFLT_PARAM)
  123. explicit deque(size_type __n) :
  124. _M_non_dbg_impl(__n), _M_iter_list(&_M_non_dbg_impl) {}
  125. #endif /*_STLP_DONT_SUP_DFLT_PARAM*/
  126. #if !defined (_STLP_NO_MOVE_SEMANTIC)
  127. deque(__move_source<_Self> src)
  128. : _M_non_dbg_impl(__move_source<_Base>(src.get()._M_non_dbg_impl)),
  129. _M_iter_list(&_M_non_dbg_impl) {
  130. # if defined (_STLP_NO_EXTENSIONS) || (_STLP_DEBUG_LEVEL == _STLP_STANDARD_DBG_LEVEL)
  131. src.get()._M_iter_list._Invalidate_all();
  132. # else
  133. src.get()._M_iter_list._Set_owner(_M_iter_list);
  134. # endif
  135. }
  136. #endif
  137. #if defined (_STLP_MEMBER_TEMPLATES)
  138. template <class _InputIterator>
  139. deque(_InputIterator __first, _InputIterator __last,
  140. const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
  141. : _ConstructCheck(__first, __last),
  142. _M_non_dbg_impl(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last), __a),
  143. _M_iter_list(&_M_non_dbg_impl) {
  144. }
  145. # if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
  146. template <class _InputIterator>
  147. deque(_InputIterator __first, _InputIterator __last)
  148. : _ConstructCheck(__first, __last),
  149. _M_non_dbg_impl(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last)),
  150. _M_iter_list(&_M_non_dbg_impl) {
  151. }
  152. # endif
  153. #else
  154. deque(const value_type* __first, const value_type* __last,
  155. const allocator_type& __a = allocator_type())
  156. : _ConstructCheck(__first, __last),
  157. _M_non_dbg_impl(__first, __last, __a),
  158. _M_iter_list(&_M_non_dbg_impl) {
  159. }
  160. deque(const_iterator __first, const_iterator __last,
  161. const allocator_type& __a = allocator_type())
  162. : _ConstructCheck(__first, __last),
  163. _M_non_dbg_impl(__first._M_iterator, __last._M_iterator, __a),
  164. _M_iter_list(&_M_non_dbg_impl) {
  165. }
  166. #endif
  167. _Self& operator=(const _Self& __x) {
  168. if (this != &__x) {
  169. _Invalidate_all();
  170. _M_non_dbg_impl = __x._M_non_dbg_impl;
  171. }
  172. return *this;
  173. }
  174. bool empty() const { return _M_non_dbg_impl.empty(); }
  175. size_type size() const { return _M_non_dbg_impl.size(); }
  176. size_type max_size() const { return _M_non_dbg_impl.max_size(); }
  177. void swap(_Self& __x) {
  178. _M_iter_list._Swap_owners(__x._M_iter_list);
  179. _M_non_dbg_impl.swap(__x._M_non_dbg_impl);
  180. }
  181. #if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (_STLP_FUNCTION_TMPL_PARTIAL_ORDER)
  182. void _M_swap_workaround(_Self& __x) { swap(__x); }
  183. #endif
  184. public:
  185. void assign(size_type __n, const _Tp& __val) {
  186. _Invalidate_all();
  187. _M_non_dbg_impl.assign(__n, __val);
  188. }
  189. #if defined (_STLP_MEMBER_TEMPLATES)
  190. template <class _InputIterator>
  191. void assign(_InputIterator __first, _InputIterator __last) {
  192. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  193. _Invalidate_all();
  194. _M_non_dbg_impl.assign(_STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last));
  195. }
  196. #else
  197. void assign(const_iterator __first, const_iterator __last) {
  198. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  199. _Invalidate_all();
  200. _M_non_dbg_impl.assign(__first._M_iterator, __last._M_iterator);
  201. }
  202. void assign(const value_type *__first, const value_type *__last) {
  203. _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last))
  204. _Invalidate_all();
  205. _M_non_dbg_impl.assign(__first, __last);
  206. }
  207. #endif
  208. public: // push_* and pop_*
  209. #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
  210. void push_back(const value_type& __t = _Tp()) {
  211. #else
  212. void push_back(const value_type& __t) {
  213. #endif
  214. _Invalidate_all();
  215. _M_non_dbg_impl.push_back(__t);
  216. }
  217. #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
  218. void push_back() {
  219. _Invalidate_all();
  220. _M_non_dbg_impl.push_back();
  221. }
  222. #endif
  223. #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
  224. void push_front(const value_type& __t = _Tp()) {
  225. #else
  226. void push_front(const value_type& __t) {
  227. #endif
  228. _Invalidate_all();
  229. _M_non_dbg_impl.push_front(__t);
  230. }
  231. #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
  232. void push_front() {
  233. _Invalidate_all();
  234. _M_non_dbg_impl.push_front();
  235. }
  236. #endif
  237. void pop_back() {
  238. _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
  239. _Invalidate_iterator(end());
  240. _M_non_dbg_impl.pop_back();
  241. }
  242. void pop_front() {
  243. _STLP_VERBOSE_ASSERT(!empty(), _StlMsg_EMPTY_CONTAINER)
  244. _Invalidate_iterator(begin());
  245. _M_non_dbg_impl.pop_front();
  246. }
  247. public: // Insert
  248. #if !defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
  249. iterator insert(iterator __pos, const value_type& __x = _Tp()) {
  250. #else
  251. iterator insert(iterator __pos, const value_type& __x) {
  252. #endif
  253. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
  254. _Invalidate_all();
  255. return iterator(&_M_iter_list, _M_non_dbg_impl.insert(__pos._M_iterator, __x));
  256. }
  257. #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
  258. iterator insert(iterator __pos) {
  259. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
  260. _Invalidate_all();
  261. return iterator(&_M_iter_list, _M_non_dbg_impl.insert(__pos._M_iterator));
  262. }
  263. #endif
  264. void insert(iterator __pos, size_type __n, const value_type& __x) {
  265. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
  266. if (__n != 0) _Invalidate_all();
  267. _M_non_dbg_impl.insert(__pos._M_iterator, __n, __x);
  268. }
  269. #if defined (_STLP_MEMBER_TEMPLATES)
  270. template <class _InputIterator>
  271. void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
  272. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
  273. // We perform invalidate first to detect self referencing in __check_range as __first and __last
  274. // will have been invalidated.
  275. if (__first != __last) _Invalidate_all();
  276. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  277. _M_non_dbg_impl.insert(__pos._M_iterator,
  278. _STLP_PRIV _Non_Dbg_iter(__first), _STLP_PRIV _Non_Dbg_iter(__last));
  279. }
  280. #endif
  281. #if !defined (_STLP_MEMBER_TEMPLATES)
  282. void insert(iterator __pos,
  283. const value_type* __first, const value_type* __last) {
  284. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
  285. _STLP_DEBUG_CHECK(_STLP_PRIV __check_ptr_range(__first, __last))
  286. if (__first != __last) _Invalidate_all();
  287. _M_non_dbg_impl.insert(__pos._M_iterator, __first, __last);
  288. }
  289. #endif
  290. #if !defined (_STLP_MEMBER_TEMPLATES) || !defined (_STLP_NO_METHOD_SPECIALIZATION)
  291. void insert(iterator __pos,
  292. const_iterator __first, const_iterator __last) {
  293. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
  294. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  295. //Sequence requirements 23.1.1 Table 67:
  296. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_not_owner(&_M_iter_list, __first));
  297. if (__first != __last) _Invalidate_all();
  298. _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator);
  299. }
  300. void insert(iterator __pos,
  301. iterator __first, iterator __last) {
  302. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
  303. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last))
  304. //Sequence requirements 23.1.1 Table 67:
  305. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_not_owner(&_M_iter_list, __first));
  306. if (__first != __last) _Invalidate_all();
  307. _M_non_dbg_impl.insert(__pos._M_iterator, __first._M_iterator, __last._M_iterator);
  308. }
  309. #endif
  310. #if !defined (_STLP_DONT_SUP_DFLT_PARAM)
  311. void resize(size_type __new_size, const value_type& __x = _Tp()) {
  312. #else
  313. void resize(size_type __new_size, const value_type& __x) {
  314. #endif
  315. if (__new_size != size()) {
  316. if ((__new_size > size()) || (__new_size < size() - 1))
  317. _Invalidate_all();
  318. else
  319. _Invalidate_iterator(end());
  320. }
  321. _M_non_dbg_impl.resize(__new_size, __x);
  322. }
  323. #if defined (_STLP_DONT_SUP_DFLT_PARAM)
  324. void resize(size_type new_size) { resize(new_size, _STLP_DEFAULT_CONSTRUCTED(_Tp)); }
  325. #endif
  326. // Erase
  327. iterator erase(iterator __pos) {
  328. _STLP_DEBUG_CHECK(_STLP_PRIV __check_if_owner(&_M_iter_list, __pos))
  329. _STLP_DEBUG_CHECK(_STLP_PRIV _Dereferenceable(__pos))
  330. if (__pos._M_iterator == _M_non_dbg_impl.begin()) {
  331. _Invalidate_iterator(__pos);
  332. } else {
  333. typename _Base::iterator tmp = --(_M_non_dbg_impl.end());
  334. if (__pos._M_iterator == tmp)
  335. _Invalidate_iterator(__pos);
  336. else
  337. _Invalidate_all();
  338. }
  339. return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__pos._M_iterator));
  340. }
  341. iterator erase(iterator __first, iterator __last) {
  342. _STLP_DEBUG_CHECK(_STLP_PRIV __check_range(__first, __last, begin(), end()))
  343. if (!empty()) {
  344. if (__first._M_iterator == _M_non_dbg_impl.begin() ||
  345. __last._M_iterator == _M_non_dbg_impl.end())
  346. _Invalidate_iterators(__first, __last);
  347. else
  348. _Invalidate_all();
  349. }
  350. return iterator (&_M_iter_list, _M_non_dbg_impl.erase(__first._M_iterator, __last._M_iterator));
  351. }
  352. void clear() {
  353. _Invalidate_all();
  354. _M_non_dbg_impl.clear();
  355. }
  356. };
  357. _STLP_END_NAMESPACE
  358. #undef _STLP_NON_DBG_DEQUE
  359. #endif /* _STLP_INTERNAL_DEQUE_H */
  360. // Local Variables:
  361. // mode:C++
  362. // End: