42 #ifndef PB_DS_TAG_AND_TRAIT_HPP
43 #define PB_DS_TAG_AND_TRAIT_HPP
55 struct trivial_iterator_tag
59 typedef void trivial_iterator_difference_type;
65 struct basic_invalidation_guarantee
73 struct point_invalidation_guarantee :
public basic_invalidation_guarantee
82 struct range_invalidation_guarantee :
public point_invalidation_guarantee
157 template<
typename Tag>
158 struct container_traits_base;
164 typedef point_invalidation_guarantee invalidation_guarantee;
168 order_preserving =
false,
169 erase_can_throw =
false,
170 split_join_can_throw =
false,
171 reverse_iteration =
false
176 struct container_traits_base<gp_hash_tag>
178 typedef gp_hash_tag container_category;
179 typedef basic_invalidation_guarantee invalidation_guarantee;
183 order_preserving =
false,
184 erase_can_throw =
false,
185 split_join_can_throw =
false,
186 reverse_iteration =
false
191 struct container_traits_base<rb_tree_tag>
193 typedef rb_tree_tag container_category;
194 typedef range_invalidation_guarantee invalidation_guarantee;
198 order_preserving =
true,
199 erase_can_throw =
false,
200 split_join_can_throw =
false,
201 reverse_iteration =
true
206 struct container_traits_base<splay_tree_tag>
208 typedef splay_tree_tag container_category;
209 typedef range_invalidation_guarantee invalidation_guarantee;
213 order_preserving =
true,
214 erase_can_throw =
false,
215 split_join_can_throw =
false,
216 reverse_iteration =
true
221 struct container_traits_base<ov_tree_tag>
223 typedef ov_tree_tag container_category;
224 typedef basic_invalidation_guarantee invalidation_guarantee;
228 order_preserving =
true,
229 erase_can_throw =
true,
230 split_join_can_throw =
true,
231 reverse_iteration =
false
236 struct container_traits_base<pat_trie_tag>
238 typedef pat_trie_tag container_category;
239 typedef range_invalidation_guarantee invalidation_guarantee;
243 order_preserving =
true,
244 erase_can_throw =
false,
245 split_join_can_throw =
true,
246 reverse_iteration =
true
251 struct container_traits_base<list_update_tag>
253 typedef list_update_tag container_category;
254 typedef point_invalidation_guarantee invalidation_guarantee;
258 order_preserving =
false,
259 erase_can_throw =
false,
260 split_join_can_throw =
false,
261 reverse_iteration =
false
267 struct container_traits_base<pairing_heap_tag>
269 typedef pairing_heap_tag container_category;
270 typedef point_invalidation_guarantee invalidation_guarantee;
274 order_preserving =
false,
275 erase_can_throw =
false,
276 split_join_can_throw =
false,
277 reverse_iteration =
false
282 struct container_traits_base<thin_heap_tag>
284 typedef thin_heap_tag container_category;
285 typedef point_invalidation_guarantee invalidation_guarantee;
289 order_preserving =
false,
290 erase_can_throw =
false,
291 split_join_can_throw =
false,
292 reverse_iteration =
false
297 struct container_traits_base<binomial_heap_tag>
299 typedef binomial_heap_tag container_category;
300 typedef point_invalidation_guarantee invalidation_guarantee;
304 order_preserving =
false,
305 erase_can_throw =
false,
306 split_join_can_throw =
false,
307 reverse_iteration =
false
312 struct container_traits_base<rc_binomial_heap_tag>
314 typedef rc_binomial_heap_tag container_category;
315 typedef point_invalidation_guarantee invalidation_guarantee;
319 order_preserving =
false,
320 erase_can_throw =
false,
321 split_join_can_throw =
false,
322 reverse_iteration =
false
327 struct container_traits_base<binary_heap_tag>
329 typedef binary_heap_tag container_category;
330 typedef basic_invalidation_guarantee invalidation_guarantee;
334 order_preserving =
false,
335 erase_can_throw =
false,
336 split_join_can_throw =
true,
337 reverse_iteration =
false
344 template<
typename Cntnr>
346 :
public container_traits_base<typename Cntnr::container_category>
348 typedef Cntnr container_type;
349 typedef typename Cntnr::container_category container_category;
350 typedef container_traits_base<container_category> base_type;
351 typedef typename base_type::invalidation_guarantee invalidation_guarantee;
355 order_preserving = base_type::order_preserving,
356 erase_can_throw = base_type::erase_can_throw,
357 split_join_can_throw = base_type::split_join_can_throw,
358 reverse_iteration = base_type::reverse_iteration