Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
iterators.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2017-2019 Intel Corporation
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 
16 
17 
18 
19 */
20 
21 #ifndef __TBB_iterators_H
22 #define __TBB_iterators_H
23 
24 #include <iterator>
25 #include <limits>
26 
27 #include "tbb_config.h"
28 #include "tbb_stddef.h"
29 
30 #if __TBB_CPP11_PRESENT
31 
32 #include <type_traits>
33 
34 namespace tbb {
35 
36 template <typename IntType>
37 class counting_iterator {
38  __TBB_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer, "Cannot instantiate counting_iterator with a non-integer type");
39 public:
40  typedef typename std::make_signed<IntType>::type difference_type;
41  typedef IntType value_type;
42  typedef const IntType* pointer;
43  typedef const IntType& reference;
44  typedef std::random_access_iterator_tag iterator_category;
45 
46  counting_iterator() : my_counter() {}
47  explicit counting_iterator(IntType init) : my_counter(init) {}
48 
49  reference operator*() const { return my_counter; }
50  value_type operator[](difference_type i) const { return *(*this + i); }
51 
52  difference_type operator-(const counting_iterator& it) const { return my_counter - it.my_counter; }
53 
54  counting_iterator& operator+=(difference_type forward) { my_counter += forward; return *this; }
55  counting_iterator& operator-=(difference_type backward) { return *this += -backward; }
56  counting_iterator& operator++() { return *this += 1; }
57  counting_iterator& operator--() { return *this -= 1; }
58 
59  counting_iterator operator++(int) {
60  counting_iterator it(*this);
61  ++(*this);
62  return it;
63  }
64  counting_iterator operator--(int) {
65  counting_iterator it(*this);
66  --(*this);
67  return it;
68  }
69 
70  counting_iterator operator-(difference_type backward) const { return counting_iterator(my_counter - backward); }
71  counting_iterator operator+(difference_type forward) const { return counting_iterator(my_counter + forward); }
72  friend counting_iterator operator+(difference_type forward, const counting_iterator it) { return it + forward; }
73 
74  bool operator==(const counting_iterator& it) const { return *this - it == 0; }
75  bool operator!=(const counting_iterator& it) const { return !(*this == it); }
76  bool operator<(const counting_iterator& it) const {return *this - it < 0; }
77  bool operator>(const counting_iterator& it) const { return it < *this; }
78  bool operator<=(const counting_iterator& it) const { return !(*this > it); }
79  bool operator>=(const counting_iterator& it) const { return !(*this < it); }
80 
81 private:
82  IntType my_counter;
83 };
84 } //namespace tbb
85 
86 
87 #include <tuple>
88 
89 #include "internal/_template_helpers.h" // index_sequence, make_index_sequence
90 
91 namespace tbb {
92 namespace internal {
93 
94 template<size_t N>
95 struct tuple_util {
96  template<typename TupleType, typename DifferenceType>
97  static void increment(TupleType& it, DifferenceType forward) {
98  std::get<N-1>(it) += forward;
99  tuple_util<N-1>::increment(it, forward);
100  }
101  template<typename TupleType, typename DifferenceType>
102  static bool check_sync(const TupleType& it1, const TupleType& it2, DifferenceType val) {
103  if(std::get<N-1>(it1) - std::get<N-1>(it2) != val)
104  return false;
105  return tuple_util<N-1>::check_sync(it1, it2, val);
106  }
107 };
108 
109 template<>
110 struct tuple_util<0> {
111  template<typename TupleType, typename DifferenceType>
112  static void increment(TupleType&, DifferenceType) {}
113  template<typename TupleType, typename DifferenceType>
114  static bool check_sync(const TupleType&, const TupleType&, DifferenceType) { return true;}
115 };
116 
117 template <typename TupleReturnType>
118 struct make_references {
119  template <typename TupleType, std::size_t... Is>
120  TupleReturnType operator()(const TupleType& t, tbb::internal::index_sequence<Is...>) {
121  return std::tie( *std::get<Is>(t)... );
122  }
123 };
124 
125 // A simple wrapper over a tuple of references.
126 // The class is designed to hold a temporary tuple of reference
127 // after dereferencing a zip_iterator; in particular, it is needed
128 // to swap these rvalue tuples. Any other usage is not supported.
129 template<typename... T>
130 struct tuplewrapper : public std::tuple<typename std::enable_if<std::is_reference<T>::value, T&&>::type...> {
131  // In the context of this class, T is a reference, so T&& is a "forwarding reference"
132  typedef std::tuple<T&&...> base_type;
133  // Construct from the result of std::tie
134  tuplewrapper(const base_type& in) : base_type(in) {}
135 #if __INTEL_COMPILER
136  // ICC cannot generate copy ctor & assignment
137  tuplewrapper(const tuplewrapper& rhs) : base_type(rhs) {}
138  tuplewrapper& operator=(const tuplewrapper& rhs) {
139  *this = base_type(rhs);
140  return *this;
141  }
142 #endif
143  // Assign any tuple convertible to std::tuple<T&&...>: *it = a_tuple;
144  template<typename... U>
145  tuplewrapper& operator=(const std::tuple<U...>& other) {
146  base_type::operator=(other);
147  return *this;
148  }
149 #if _LIBCPP_VERSION
150  // (Necessary for libc++ tuples) Convert to a tuple of values: v = *it;
151  operator std::tuple<typename std::remove_reference<T>::type...>() { return base_type(*this); }
152 #endif
153  // Swap rvalue tuples: swap(*it1,*it2);
154  friend void swap(tuplewrapper&& a, tuplewrapper&& b) {
155  std::swap<T&&...>(a,b);
156  }
157 };
158 
159 } //namespace internal
160 
161 template <typename... Types>
162 class zip_iterator {
163  __TBB_STATIC_ASSERT(sizeof...(Types), "Cannot instantiate zip_iterator with empty template parameter pack");
164  static const std::size_t num_types = sizeof...(Types);
165  typedef std::tuple<Types...> it_types;
166 public:
167  typedef typename std::make_signed<std::size_t>::type difference_type;
168  typedef std::tuple<typename std::iterator_traits<Types>::value_type...> value_type;
169 #if __INTEL_COMPILER && __INTEL_COMPILER < 1800 && _MSC_VER
170  typedef std::tuple<typename std::iterator_traits<Types>::reference...> reference;
171 #else
172  typedef tbb::internal::tuplewrapper<typename std::iterator_traits<Types>::reference...> reference;
173 #endif
174  typedef std::tuple<typename std::iterator_traits<Types>::pointer...> pointer;
175  typedef std::random_access_iterator_tag iterator_category;
176 
177  zip_iterator() : my_it() {}
178  explicit zip_iterator(Types... args) : my_it(std::make_tuple(args...)) {}
179  zip_iterator(const zip_iterator& input) : my_it(input.my_it) {}
180  zip_iterator& operator=(const zip_iterator& input) {
181  my_it = input.my_it;
182  return *this;
183  }
184 
185  reference operator*() const {
186  return tbb::internal::make_references<reference>()(my_it, tbb::internal::make_index_sequence<num_types>());
187  }
188  reference operator[](difference_type i) const { return *(*this + i); }
189 
190  difference_type operator-(const zip_iterator& it) const {
191  __TBB_ASSERT(internal::tuple_util<num_types>::check_sync(my_it, it.my_it, std::get<0>(my_it) - std::get<0>(it.my_it)),
192  "Components of zip_iterator are not synchronous");
193  return std::get<0>(my_it) - std::get<0>(it.my_it);
194  }
195 
196  zip_iterator& operator+=(difference_type forward) {
197  internal::tuple_util<num_types>::increment(my_it, forward);
198  return *this;
199  }
200  zip_iterator& operator-=(difference_type backward) { return *this += -backward; }
201  zip_iterator& operator++() { return *this += 1; }
202  zip_iterator& operator--() { return *this -= 1; }
203 
204  zip_iterator operator++(int) {
205  zip_iterator it(*this);
206  ++(*this);
207  return it;
208  }
209  zip_iterator operator--(int) {
210  zip_iterator it(*this);
211  --(*this);
212  return it;
213  }
214 
215  zip_iterator operator-(difference_type backward) const {
216  zip_iterator it(*this);
217  return it -= backward;
218  }
219  zip_iterator operator+(difference_type forward) const {
220  zip_iterator it(*this);
221  return it += forward;
222  }
223  friend zip_iterator operator+(difference_type forward, const zip_iterator& it) { return it + forward; }
224 
225  bool operator==(const zip_iterator& it) const {
226  return *this - it == 0;
227  }
228  bool operator!=(const zip_iterator& it) const { return !(*this == it); }
229  bool operator<(const zip_iterator& it) const { return *this - it < 0; }
230  bool operator>(const zip_iterator& it) const { return it < *this; }
231  bool operator<=(const zip_iterator& it) const { return !(*this > it); }
232  bool operator>=(const zip_iterator& it) const { return !(*this < it); }
233 private:
234  it_types my_it;
235 };
236 
237 template<typename... T>
238 zip_iterator<T...> make_zip_iterator(T... args) { return zip_iterator<T...>(args...); }
239 
240 template <typename UnaryFunc, typename Iter>
241 class transform_iterator {
242 public:
243  typedef typename std::iterator_traits<Iter>::value_type value_type;
244  typedef typename std::iterator_traits<Iter>::difference_type difference_type;
245 #if __TBB_CPP17_INVOKE_RESULT_PRESENT
246  typedef typename std::invoke_result<UnaryFunc, typename std::iterator_traits<Iter>::reference>::type reference;
247 #else
248  typedef typename std::result_of<UnaryFunc(typename std::iterator_traits<Iter>::reference)>::type reference;
249 #endif
250  typedef typename std::iterator_traits<Iter>::pointer pointer;
251  typedef typename std::random_access_iterator_tag iterator_category;
252 
253  transform_iterator(Iter it, UnaryFunc unary_func) : my_it(it), my_unary_func(unary_func) {
254  __TBB_STATIC_ASSERT((std::is_same<typename std::iterator_traits<Iter>::iterator_category,
255  std::random_access_iterator_tag>::value), "Random access iterator required.");
256  }
257  transform_iterator(const transform_iterator& input) : my_it(input.my_it), my_unary_func(input.my_unary_func) { }
258  transform_iterator& operator=(const transform_iterator& input) {
259  my_it = input.my_it;
260  return *this;
261  }
262  reference operator*() const {
263  return my_unary_func(*my_it);
264  }
265  reference operator[](difference_type i) const {
266  return *(*this + i);
267  }
268  transform_iterator& operator++() {
269  ++my_it;
270  return *this;
271  }
272  transform_iterator& operator--() {
273  --my_it;
274  return *this;
275  }
276  transform_iterator operator++(int) {
277  transform_iterator it(*this);
278  ++(*this);
279  return it;
280  }
281  transform_iterator operator--(int) {
282  transform_iterator it(*this);
283  --(*this);
284  return it;
285  }
286  transform_iterator operator+(difference_type forward) const {
287  return { my_it + forward, my_unary_func };
288  }
289  transform_iterator operator-(difference_type backward) const {
290  return { my_it - backward, my_unary_func };
291  }
292  transform_iterator& operator+=(difference_type forward) {
293  my_it += forward;
294  return *this;
295  }
296  transform_iterator& operator-=(difference_type backward) {
297  my_it -= backward;
298  return *this;
299  }
300  friend transform_iterator operator+(difference_type forward, const transform_iterator& it) {
301  return it + forward;
302  }
303  difference_type operator-(const transform_iterator& it) const {
304  return my_it - it.my_it;
305  }
306  bool operator==(const transform_iterator& it) const { return *this - it == 0; }
307  bool operator!=(const transform_iterator& it) const { return !(*this == it); }
308  bool operator<(const transform_iterator& it) const { return *this - it < 0; }
309  bool operator>(const transform_iterator& it) const { return it < *this; }
310  bool operator<=(const transform_iterator& it) const { return !(*this > it); }
311  bool operator>=(const transform_iterator& it) const { return !(*this < it); }
312 
313  Iter base() const { return my_it; }
314 private:
315  Iter my_it;
316  const UnaryFunc my_unary_func;
317 };
318 
319 template<typename UnaryFunc, typename Iter>
320 transform_iterator<UnaryFunc, Iter> make_transform_iterator(Iter it, UnaryFunc unary_func) {
321  return transform_iterator<UnaryFunc, Iter>(it, unary_func);
322 }
323 
324 } //namespace tbb
325 
326 #endif //__TBB_CPP11_PRESENT
327 
328 #endif /* __TBB_iterators_H */
bool operator<=(const concurrent_vector< T, A1 > &a, const concurrent_vector< T, A2 > &b)
bool operator==(const cache_aligned_allocator< T > &, const cache_aligned_allocator< U > &)
bool operator>=(const concurrent_vector< T, A1 > &a, const concurrent_vector< T, A2 > &b)
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:536
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
bool operator<(const concurrent_vector< T, A1 > &a, const concurrent_vector< T, A2 > &b)
tick_count::interval_t operator-(const tick_count &t1, const tick_count &t0)
Definition: tick_count.h:130
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
bool operator>(const concurrent_vector< T, A1 > &a, const concurrent_vector< T, A2 > &b)
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:539
vector_iterator< Container, T > operator+(ptrdiff_t offset, const vector_iterator< Container, T > &v)
The graph class.
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
bool operator!=(const cache_aligned_allocator< T > &, const cache_aligned_allocator< U > &)
typename tbb::internal::make_index_sequence_impl< N >::type make_index_sequence

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.