libstdc++
profile/list
Go to the documentation of this file.
1 // Profiling list implementation -*- C++ -*-
2 
3 // Copyright (C) 2009, 2010 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10 
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
15 
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19 
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
24 
25 /** @file profile/list
26  * This file is a GNU profile extension to the Standard C++ Library.
27  */
28 
29 #ifndef _GLIBCXX_PROFILE_LIST
30 #define _GLIBCXX_PROFILE_LIST 1
31 
32 #include <list>
33 #include <profile/base.h>
35 
36 namespace std _GLIBCXX_VISIBILITY(default)
37 {
38 namespace __profile
39 {
40  /** @brief List wrapper with performance instrumentation. */
41 template<typename _Tp, typename _Allocator = std::allocator<_Tp> >
42  class list
43  : public _GLIBCXX_STD_C::list<_Tp, _Allocator>
44  {
45  typedef _GLIBCXX_STD_C::list<_Tp, _Allocator> _Base;
46 
47  public:
48  typedef typename _Base::reference reference;
49  typedef typename _Base::const_reference const_reference;
50 
51  typedef __iterator_tracker<typename _Base::iterator, list>
52  iterator;
53  typedef __iterator_tracker<typename _Base::const_iterator, list>
54  const_iterator;
55 
56  typedef typename _Base::size_type size_type;
57  typedef typename _Base::difference_type difference_type;
58 
59  typedef _Tp value_type;
60  typedef _Allocator allocator_type;
61  typedef typename _Base::pointer pointer;
62  typedef typename _Base::const_pointer const_pointer;
65 
66  // 23.2.2.1 construct/copy/destroy:
67  explicit
68  list(const _Allocator& __a = _Allocator())
69  : _Base(__a)
70  {
71  __profcxx_list_construct(this); // list2slist
72  __profcxx_list_construct2(this); // list2vector
73  }
74 
75 #ifdef __GXX_EXPERIMENTAL_CXX0X__
76  explicit
77  list(size_type __n)
78  : _Base(__n)
79  {
80  __profcxx_list_construct(this);
81  __profcxx_list_construct2(this);
82  }
83 
84  list(size_type __n, const _Tp& __value,
85  const _Allocator& __a = _Allocator())
86  : _Base(__n, __value, __a)
87  {
88  __profcxx_list_construct(this);
89  __profcxx_list_construct2(this);
90  }
91 #else
92  explicit
93  list(size_type __n, const _Tp& __value = _Tp(),
94  const _Allocator& __a = _Allocator())
95  : _Base(__n, __value, __a)
96  {
97  __profcxx_list_construct(this);
98  __profcxx_list_construct2(this);
99  }
100 #endif
101 
102  template<class _InputIterator>
103  list(_InputIterator __first, _InputIterator __last,
104  const _Allocator& __a = _Allocator())
105  : _Base(__first, __last, __a)
106  {
107  __profcxx_list_construct(this);
108  __profcxx_list_construct2(this);
109  }
110 
111  list(const list& __x)
112  : _Base(__x)
113  {
114  __profcxx_list_construct(this);
115  __profcxx_list_construct2(this);
116  }
117 
118  list(const _Base& __x)
119  : _Base(__x)
120  {
121  __profcxx_list_construct(this);
122  __profcxx_list_construct2(this);
123  }
124 
125 #ifdef __GXX_EXPERIMENTAL_CXX0X__
126  list(list&& __x)
127  : _Base(std::move(__x))
128  {
129  __profcxx_list_construct(this);
130  __profcxx_list_construct2(this);
131  }
132 
134  const allocator_type& __a = allocator_type())
135  : _Base(__l, __a) { }
136 #endif
137 
138  ~list() {
139  __profcxx_list_destruct(this);
140  __profcxx_list_destruct2(this);
141  }
142 
143  list&
144  operator=(const list& __x)
145  {
146  static_cast<_Base&>(*this) = __x;
147  return *this;
148  }
149 
150 #ifdef __GXX_EXPERIMENTAL_CXX0X__
151  list&
152  operator=(list&& __x)
153  {
154  // NB: DR 1204.
155  // NB: DR 675.
156  this->clear();
157  this->swap(__x);
158  return *this;
159  }
160 
161  list&
162  operator=(initializer_list<value_type> __l)
163  {
164  static_cast<_Base&>(*this) = __l;
165  return *this;
166  }
167 
168  void
169  assign(initializer_list<value_type> __l)
170  { _Base::assign(__l); }
171 #endif
172 
173  template<class _InputIterator>
174  void
175  assign(_InputIterator __first, _InputIterator __last)
176  { _Base::assign(__first, __last); }
177 
178  void
179  assign(size_type __n, const _Tp& __t)
180  { _Base::assign(__n, __t); }
181 
182  using _Base::get_allocator;
183 
184  // iterators:
185  iterator
186  begin()
187  { return iterator(_Base::begin(), this); }
188 
189  const_iterator
190  begin() const
191  { return const_iterator(_Base::begin(), this); }
192 
193  iterator
194  end()
195  {
196  __profcxx_list_rewind(this);
197  return iterator(_Base::end(), this);
198  }
199 
200  const_iterator
201  end() const
202  {
203  __profcxx_list_rewind(this);
204  return const_iterator(_Base::end(), this);
205  }
206 
208  rbegin()
209  {
210  __profcxx_list_rewind(this);
211  return reverse_iterator(end());
212  }
213 
215  rbegin() const
216  {
217  __profcxx_list_rewind(this);
218  return const_reverse_iterator(end());
219  }
220 
222  rend()
223  { return reverse_iterator(begin()); }
224 
226  rend() const
227  { return const_reverse_iterator(begin()); }
228 
229 #ifdef __GXX_EXPERIMENTAL_CXX0X__
230  const_iterator
231  cbegin() const
232  { return const_iterator(_Base::begin(), this); }
233 
234  const_iterator
235  cend() const
236  { return const_iterator(_Base::end(), this); }
237 
239  crbegin() const
240  { return const_reverse_iterator(end()); }
241 
243  crend() const
244  { return const_reverse_iterator(begin()); }
245 #endif
246 
247  // 23.2.2.2 capacity:
248  using _Base::empty;
249  using _Base::size;
250  using _Base::max_size;
251 
252 #ifdef __GXX_EXPERIMENTAL_CXX0X__
253  void
254  resize(size_type __sz)
255  { _Base::resize(__sz); }
256 
257  void
258  resize(size_type __sz, const _Tp& __c)
259  { _Base::resize(__sz, __c); }
260 #else
261  void
262  resize(size_type __sz, _Tp __c = _Tp())
263  { _Base::resize(__sz, __c); }
264 #endif
265 
266  // element access:
267  reference
268  front()
269  { return _Base::front(); }
270 
271  const_reference
272  front() const
273  { return _Base::front(); }
274 
275  reference
276  back()
277  {
278  __profcxx_list_rewind(this);
279  return _Base::back();
280  }
281 
282  const_reference
283  back() const
284  {
285  __profcxx_list_rewind(this);
286  return _Base::back();
287  }
288 
289  // 23.2.2.3 modifiers:
290  void
291  push_front(const value_type& __x)
292  {
293  __profcxx_list_invalid_operator(this);
294  __profcxx_list_operation(this);
295  _Base::push_front(__x);
296  }
297 
298 #ifdef __GXX_EXPERIMENTAL_CXX0X__
299  using _Base::emplace_front;
300 #endif
301 
302  void
303  pop_front()
304  {
305  __profcxx_list_operation(this);
306  _Base::pop_front();
307  }
308 
309  using _Base::push_back;
310 
311 #ifdef __GXX_EXPERIMENTAL_CXX0X__
312  using _Base::emplace_back;
313 #endif
314 
315  void
316  pop_back()
317  {
318  iterator __victim = end();
319  --__victim;
320  _Base::pop_back();
321  __profcxx_list_rewind(this);
322  }
323 
324 #ifdef __GXX_EXPERIMENTAL_CXX0X__
325  template<typename... _Args>
326  iterator
327  emplace(iterator __position, _Args&&... __args)
328  {
329  return iterator(_Base::emplace(__position.base(),
330  std::forward<_Args>(__args)...));
331  }
332 #endif
333 
334  iterator
335  insert(iterator __position, const _Tp& __x)
336  {
337  _M_profile_insert(this, __position, size());
338  return iterator(_Base::insert(__position.base(), __x), this);
339  }
340 
341 #ifdef __GXX_EXPERIMENTAL_CXX0X__
342  iterator
343  insert(iterator __position, _Tp&& __x)
344  {
345  _M_profile_insert(this, __position, size());
346  return iterator(_Base::emplace(__position.base(), std::move(__x)),
347  this);
348  }
349 
350  void
351  insert(iterator __position, initializer_list<value_type> __l)
352  {
353  _M_profile_insert(this, __position, size());
354  _Base::insert(__position.base(), __l);
355  }
356 #endif
357 
358  void
359  insert(iterator __position, size_type __n, const _Tp& __x)
360  {
361  _M_profile_insert(this, __position, size());
362  _Base::insert(__position.base(), __n, __x);
363  }
364 
365  template<class _InputIterator>
366  void
367  insert(iterator __position, _InputIterator __first,
368  _InputIterator __last)
369  {
370  _M_profile_insert(this, __position, size());
371  _Base::insert(__position.base(), __first, __last);
372  }
373 
374  iterator
375  erase(iterator __position)
376  { return iterator(_Base::erase(__position.base()), this); }
377 
378  iterator
379  erase(iterator __position, iterator __last)
380  {
381  // _GLIBCXX_RESOLVE_LIB_DEFECTS
382  // 151. can't currently clear() empty container
383  return iterator(_Base::erase(__position.base(), __last.base()), this);
384  }
385 
386  void
387  swap(list& __x)
388  { _Base::swap(__x); }
389 
390  void
391  clear()
392  { _Base::clear(); }
393 
394  // 23.2.2.4 list operations:
395  void
396 #ifdef __GXX_EXPERIMENTAL_CXX0X__
397  splice(iterator __position, list&& __x)
398 #else
399  splice(iterator __position, list& __x)
400 #endif
401  { this->splice(__position, _GLIBCXX_MOVE(__x), __x.begin(), __x.end()); }
402 
403 #ifdef __GXX_EXPERIMENTAL_CXX0X__
404  void
405  splice(iterator __position, list& __x)
406  { this->splice(__position, std::move(__x)); }
407 #endif
408 
409 #ifdef __GXX_EXPERIMENTAL_CXX0X__
410  void
411  splice(iterator __position, list& __x, iterator __i)
412  { this->splice(__position, std::move(__x), __i); }
413 #endif
414 
415  void
416 #ifdef __GXX_EXPERIMENTAL_CXX0X__
417  splice(iterator __position, list&& __x, iterator __i)
418 #else
419  splice(iterator __position, list& __x, iterator __i)
420 #endif
421  {
422  // We used to perform the splice_alloc check: not anymore, redundant
423  // after implementing the relevant bits of N1599.
424 
425  // _GLIBCXX_RESOLVE_LIB_DEFECTS
426  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
427  __i.base());
428  }
429 
430  void
431 #ifdef __GXX_EXPERIMENTAL_CXX0X__
432  splice(iterator __position, list&& __x, iterator __first,
433  iterator __last)
434 #else
435  splice(iterator __position, list& __x, iterator __first,
436  iterator __last)
437 #endif
438  {
439  // We used to perform the splice_alloc check: not anymore, redundant
440  // after implementing the relevant bits of N1599.
441 
442  _Base::splice(__position.base(), _GLIBCXX_MOVE(__x._M_base()),
443  __first.base(), __last.base());
444  }
445 
446 #ifdef __GXX_EXPERIMENTAL_CXX0X__
447  void
448  splice(iterator __position, list& __x, iterator __first, iterator __last)
449  { this->splice(__position, std::move(__x), __first, __last); }
450 #endif
451 
452  void
453  remove(const _Tp& __value)
454  {
455  for (iterator __x = begin(); __x != end(); )
456  {
457  if (*__x == __value)
458  __x = erase(__x);
459  else
460  ++__x;
461  }
462  }
463 
464  template<class _Predicate>
465  void
466  remove_if(_Predicate __pred)
467  {
468  for (iterator __x = begin(); __x != end(); )
469  {
470  __profcxx_list_operation(this);
471  if (__pred(*__x))
472  __x = erase(__x);
473  else
474  ++__x;
475  }
476  }
477 
478  void
479  unique()
480  {
481  iterator __first = begin();
482  iterator __last = end();
483  if (__first == __last)
484  return;
485  iterator __next = __first;
486  while (++__next != __last)
487  {
488  __profcxx_list_operation(this);
489  if (*__first == *__next)
490  erase(__next);
491  else
492  __first = __next;
493  __next = __first;
494  }
495  }
496 
497  template<class _BinaryPredicate>
498  void
499  unique(_BinaryPredicate __binary_pred)
500  {
501  iterator __first = begin();
502  iterator __last = end();
503  if (__first == __last)
504  return;
505  iterator __next = __first;
506  while (++__next != __last)
507  {
508  __profcxx_list_operation(this);
509  if (__binary_pred(*__first, *__next))
510  erase(__next);
511  else
512  __first = __next;
513  __next = __first;
514  }
515  }
516 
517  void
518 #ifdef __GXX_EXPERIMENTAL_CXX0X__
519  merge(list&& __x)
520 #else
521  merge(list& __x)
522 #endif
523  {
524  // _GLIBCXX_RESOLVE_LIB_DEFECTS
525  // 300. list::merge() specification incomplete
526  if (this != &__x)
527  { _Base::merge(_GLIBCXX_MOVE(__x._M_base())); }
528  }
529 
530 #ifdef __GXX_EXPERIMENTAL_CXX0X__
531  void
532  merge(list& __x)
533  { this->merge(std::move(__x)); }
534 #endif
535 
536  template<class _Compare>
537  void
538 #ifdef __GXX_EXPERIMENTAL_CXX0X__
539  merge(list&& __x, _Compare __comp)
540 #else
541  merge(list& __x, _Compare __comp)
542 #endif
543  {
544  // _GLIBCXX_RESOLVE_LIB_DEFECTS
545  // 300. list::merge() specification incomplete
546  if (this != &__x)
547  { _Base::merge(_GLIBCXX_MOVE(__x._M_base()), __comp); }
548  }
549 
550 #ifdef __GXX_EXPERIMENTAL_CXX0X__
551  template<typename _Compare>
552  void
553  merge(list& __x, _Compare __comp)
554  { this->merge(std::move(__x), __comp); }
555 #endif
556 
557  void
558  sort() { _Base::sort(); }
559 
560  template<typename _StrictWeakOrdering>
561  void
562  sort(_StrictWeakOrdering __pred) { _Base::sort(__pred); }
563 
564  using _Base::reverse;
565 
566  _Base&
567  _M_base() { return *this; }
568 
569  const _Base&
570  _M_base() const { return *this; }
571 
572  inline void _M_profile_find() const
573  { }
574 
575  inline void _M_profile_iterate(int __rewind = 0) const
576  {
577  __profcxx_list_operation(this);
578  __profcxx_list_iterate(this);
579  if (__rewind)
580  __profcxx_list_rewind(this);
581  }
582 
583  private:
584  size_type _M_profile_insert(void* obj, iterator __pos, size_type __size)
585  {
586  size_type __shift = 0;
587  typename _Base::iterator __it = __pos.base();
588  for ( ; __it!=_Base::end(); __it++)
589  __shift++;
590  __profcxx_list_rewind(this);
591  __profcxx_list_operation(this);
592  __profcxx_list_insert(this, __shift, __size);
593  }
594  };
595 
596  template<typename _Tp, typename _Alloc>
597  inline bool
598  operator==(const list<_Tp, _Alloc>& __lhs,
599  const list<_Tp, _Alloc>& __rhs)
600  { return __lhs._M_base() == __rhs._M_base(); }
601 
602  template<typename _Tp, typename _Alloc>
603  inline bool
604  operator!=(const list<_Tp, _Alloc>& __lhs,
605  const list<_Tp, _Alloc>& __rhs)
606  { return __lhs._M_base() != __rhs._M_base(); }
607 
608  template<typename _Tp, typename _Alloc>
609  inline bool
610  operator<(const list<_Tp, _Alloc>& __lhs,
611  const list<_Tp, _Alloc>& __rhs)
612  { return __lhs._M_base() < __rhs._M_base(); }
613 
614  template<typename _Tp, typename _Alloc>
615  inline bool
616  operator<=(const list<_Tp, _Alloc>& __lhs,
617  const list<_Tp, _Alloc>& __rhs)
618  { return __lhs._M_base() <= __rhs._M_base(); }
619 
620  template<typename _Tp, typename _Alloc>
621  inline bool
622  operator>=(const list<_Tp, _Alloc>& __lhs,
623  const list<_Tp, _Alloc>& __rhs)
624  { return __lhs._M_base() >= __rhs._M_base(); }
625 
626  template<typename _Tp, typename _Alloc>
627  inline bool
628  operator>(const list<_Tp, _Alloc>& __lhs,
629  const list<_Tp, _Alloc>& __rhs)
630  { return __lhs._M_base() > __rhs._M_base(); }
631 
632  template<typename _Tp, typename _Alloc>
633  inline void
634  swap(list<_Tp, _Alloc>& __lhs, list<_Tp, _Alloc>& __rhs)
635  { __lhs.swap(__rhs); }
636 
637 } // namespace __profile
638 } // namespace std
639 
640 #endif
List wrapper with performance instrumentation.
Definition: profile/list:42
constexpr size_t size() const
Returns the total number of bits.
Definition: bitset:1275
initializer_list
Sequential helper functions. This file is a GNU profile extension to the Standard C++ Library...
A standard container with linear time access to elements, and fixed time insertion/deletion at any po...
Definition: stl_list.h:429