|
111
|
1 // { dg-do compile }
|
|
|
2 // { dg-options "-O -fstrict-aliasing -ftree-pre -fno-tree-fre -fno-tree-sra" }
|
|
131
|
3 // { dg-additional-options "-Wno-return-type" }
|
|
111
|
4
|
|
|
5 typedef __SIZE_TYPE__ size_t;
|
|
|
6 namespace std
|
|
|
7 {
|
|
|
8 template < class _T1, class > struct pair
|
|
|
9 {
|
|
|
10 _T1 first;
|
|
|
11 };
|
|
|
12 }
|
|
|
13 namespace __gnu_cxx
|
|
|
14 {
|
|
|
15 template < typename _Tp > class new_allocator
|
|
|
16 {
|
|
|
17 public:
|
|
|
18 typedef size_t size_type;
|
|
|
19 typedef _Tp * pointer;
|
|
|
20 typedef _Tp const_pointer;
|
|
|
21 typedef _Tp & reference;
|
|
|
22 typedef const _Tp & const_reference;
|
|
|
23 template < typename _Tp1 > struct rebind
|
|
|
24 {
|
|
|
25 typedef new_allocator < _Tp1 > other;
|
|
|
26 };
|
|
|
27 };
|
|
|
28 }
|
|
|
29 namespace std
|
|
|
30 {
|
|
|
31 template < typename _Tp > class allocator:
|
|
|
32 public __gnu_cxx::new_allocator < _Tp >
|
|
|
33 {};
|
|
|
34 template < typename, typename, typename > struct binary_function;
|
|
|
35 template < typename _Tp > struct less:binary_function < _Tp, _Tp, bool >
|
|
|
36 {};
|
|
|
37 }
|
|
|
38 namespace __gnu_cxx
|
|
|
39 {
|
|
|
40 namespace typelist
|
|
|
41 {
|
|
|
42 struct null_type;
|
|
|
43 template < typename Root > struct node
|
|
|
44 {
|
|
|
45 typedef Root root;
|
|
|
46 };
|
|
|
47 template < typename, typename > struct chain;
|
|
|
48 namespace detail
|
|
|
49 {
|
|
|
50 template < typename, int >struct chain_at_index_;
|
|
|
51 template
|
|
|
52 <
|
|
|
53 typename
|
|
|
54 Hd, typename Tl > struct chain_at_index_ <chain < Hd, Tl >, 0 >
|
|
|
55 {
|
|
|
56 typedef Hd type;
|
|
|
57 };
|
|
|
58 template
|
|
|
59 <
|
|
|
60 typename
|
|
|
61 Hd, typename Tl, int i > struct chain_at_index_ <chain < Hd, Tl >, i >
|
|
|
62 {
|
|
|
63 typedef typename chain_at_index_ < Tl, i - 1 >::type type;
|
|
|
64 };
|
|
|
65 }
|
|
|
66 template < typename Typelist, int i > struct at_index
|
|
|
67 {
|
|
|
68 typedef typename Typelist::root root_type;
|
|
|
69 typedef detail::chain_at_index_ < root_type, i > index_type;
|
|
|
70 typedef typename index_type::type type;
|
|
|
71 };
|
|
|
72 template < typename T1, typename T2 > struct create2
|
|
|
73 {
|
|
|
74 typedef node < chain < T1, chain < T2, null_type > > >type;
|
|
|
75 };
|
|
|
76 }
|
|
|
77 }
|
|
|
78 namespace std
|
|
|
79 {
|
|
|
80 namespace tr1
|
|
|
81 {
|
|
|
82 template < typename _Tp, _Tp __v > struct integral_constant
|
|
|
83 {
|
|
|
84 static const _Tp value = __v;
|
|
|
85 };
|
|
|
86 typedef integral_constant < bool, false > false_type;
|
|
|
87 template < typename, typename > struct is_same:false_type
|
|
|
88 {};
|
|
|
89 }
|
|
|
90 }
|
|
|
91 using std::tr1::is_same;
|
|
|
92 namespace __gnu_pbds
|
|
|
93 {
|
|
|
94 struct null_mapped_type;
|
|
|
95 struct rb_tree_tag;
|
|
|
96 namespace detail
|
|
|
97 {
|
|
|
98 template < typename, typename, typename > struct basic_tree_policy_base;
|
|
|
99 template
|
|
|
100 <
|
|
|
101 typename
|
|
|
102 Const_Node_Iterator,
|
|
|
103 typename
|
|
|
104 Allocator
|
|
|
105 >
|
|
|
106 struct
|
|
|
107 basic_tree_policy_base
|
|
|
108 <Const_Node_Iterator, Const_Node_Iterator, Allocator >
|
|
|
109 {};
|
|
|
110 }
|
|
|
111 template
|
|
|
112 < typename, typename, typename, typename > struct null_tree_node_update;
|
|
|
113 template < typename Const_Node_Iterator, typename Node_Iterator, typename, typename Allocator > class tree_order_statistics_node_update:
|
|
|
114 detail::basic_tree_policy_base
|
|
|
115 < Const_Node_Iterator, Node_Iterator, Allocator >
|
|
|
116 {
|
|
|
117 public:
|
|
|
118 typedef Allocator allocator_type;
|
|
|
119 typedef typename allocator_type::size_type size_type;
|
|
|
120 typedef size_type metadata_type;
|
|
|
121 typedef Const_Node_Iterator const_node_iterator;
|
|
|
122 typedef Node_Iterator node_iterator;
|
|
|
123 typedef
|
|
|
124 typename
|
|
|
125 allocator_type::template
|
|
|
126 rebind < metadata_type >::other::reference metadata_reference;
|
|
|
127 void operator () (node_iterator, const_node_iterator) const;
|
|
|
128 };
|
|
|
129 template
|
|
|
130 <
|
|
|
131 typename
|
|
|
132 Const_Node_Iterator,
|
|
|
133 class
|
|
|
134 Node_Iterator,
|
|
|
135 class
|
|
|
136 Cmp_Fn,
|
|
|
137 class
|
|
|
138 Allocator
|
|
|
139 >
|
|
|
140 inline
|
|
|
141 void
|
|
|
142 tree_order_statistics_node_update
|
|
|
143 <
|
|
|
144 Const_Node_Iterator,
|
|
|
145 Node_Iterator,
|
|
|
146 Cmp_Fn,
|
|
|
147 Allocator
|
|
|
148 >::operator
|
|
|
149 () (node_iterator node_it, const_node_iterator end_nd_it) const
|
|
|
150 {
|
|
|
151 node_iterator l_child_it;
|
|
|
152 size_type
|
|
|
153 l_rank = (l_child_it == end_nd_it) ? : l_child_it.get_metadata ();
|
|
|
154 node_iterator r_child_it = node_it.get_r_child ();
|
|
|
155 size_type
|
|
|
156 r_rank = (r_child_it == end_nd_it) ? : r_child_it.get_metadata ();
|
|
|
157 const_cast
|
|
|
158 < metadata_reference > (node_it.get_metadata ()) = l_rank + r_rank;
|
|
|
159 }
|
|
|
160 namespace
|
|
|
161 {
|
|
|
162 template < typename, typename, typename, bool > struct value_type_base;
|
|
|
163 template
|
|
|
164 <
|
|
|
165 typename
|
|
|
166 Key,
|
|
|
167 typename
|
|
|
168 Allocator
|
|
|
169 > struct value_type_base <Key, null_mapped_type, Allocator, false >
|
|
|
170 {
|
|
|
171 typedef Key value_type;
|
|
|
172 typedef
|
|
|
173 typename
|
|
|
174 Allocator::template rebind < value_type >::other value_type_allocator;
|
|
|
175 typedef typename value_type_allocator::pointer pointer;
|
|
|
176 typedef typename value_type_allocator::const_pointer const_pointer;
|
|
|
177 typedef typename value_type_allocator::reference reference;
|
|
|
178 typedef typename value_type_allocator::const_reference const_reference;
|
|
|
179 };
|
|
|
180 template
|
|
|
181 <
|
|
|
182 typename
|
|
|
183 Key,
|
|
|
184 typename
|
|
|
185 Mapped, typename Alloc, bool Store_Extra > struct vt_base_selector
|
|
|
186 {
|
|
|
187 typedef value_type_base < Key, Mapped, Alloc, Store_Extra > type;
|
|
|
188 };
|
|
|
189 template
|
|
|
190 <
|
|
|
191 typename
|
|
|
192 Key,
|
|
|
193 typename
|
|
|
194 Mapped,
|
|
|
195 typename
|
|
|
196 Alloc,
|
|
|
197 bool
|
|
|
198 Store_Extra
|
|
|
199 >
|
|
|
200 struct
|
|
|
201 types_traits:vt_base_selector < Key, Mapped, Alloc, Store_Extra >::type
|
|
|
202 {};
|
|
|
203 template < typename, class, class > struct dumconst_node_iterator;
|
|
|
204 template
|
|
|
205 <
|
|
|
206 typename
|
|
|
207 Key,
|
|
|
208 typename
|
|
|
209 Mapped,
|
|
|
210 class,
|
|
|
211 class
|
|
|
212 Node_And_It_Traits, class Allocator > class bin_search_tree_no_data_
|
|
|
213 {
|
|
|
214 protected:
|
|
|
215 typedef
|
|
|
216 typename
|
|
|
217 Allocator::template
|
|
|
218 rebind
|
|
|
219 < typename Node_And_It_Traits::node >::other::pointer node_pointer;
|
|
|
220 typedef
|
|
|
221 typename
|
|
|
222 types_traits
|
|
|
223 < Key, Mapped, Allocator, false >::const_reference const_reference;
|
|
|
224 typedef typename Node_And_It_Traits::point_iterator point_iterator;
|
|
|
225 typedef typename Node_And_It_Traits::node_update node_update;
|
|
|
226 void rotate_right (node_pointer);
|
|
|
227 template
|
|
|
228 <
|
|
|
229 typename
|
|
|
230 Node_Update_ > void apply_update (node_pointer, Node_Update_ *);
|
|
|
231 };
|
|
|
232 template
|
|
|
233 <
|
|
|
234 typename
|
|
|
235 Key,
|
|
|
236 typename
|
|
|
237 Mapped,
|
|
|
238 class
|
|
|
239 Cmp_Fn,
|
|
|
240 class
|
|
|
241 Node_And_It_Traits,
|
|
|
242 class
|
|
|
243 Allocator
|
|
|
244 >
|
|
|
245 void
|
|
|
246 bin_search_tree_no_data_
|
|
|
247 <
|
|
|
248 Key,
|
|
|
249 Mapped,
|
|
|
250 Cmp_Fn, Node_And_It_Traits, Allocator >::rotate_right (node_pointer p_x)
|
|
|
251 {
|
|
|
252 node_pointer p_y = p_x->m_p_parent;
|
|
|
253 p_y->m_p_right = p_x;
|
|
|
254 apply_update (p_x, this);
|
|
|
255 apply_update (p_x->m_p_parent, (node_update *) this);
|
|
|
256 }
|
|
|
257 template
|
|
|
258 <
|
|
|
259 typename
|
|
|
260 Key,
|
|
|
261 typename
|
|
|
262 Mapped,
|
|
|
263 class
|
|
|
264 Cmp_Fn,
|
|
|
265 class
|
|
|
266 Node_And_It_Traits,
|
|
|
267 class
|
|
|
268 Allocator
|
|
|
269 >
|
|
|
270 template
|
|
|
271 <
|
|
|
272 typename
|
|
|
273 Node_Update_
|
|
|
274 >
|
|
|
275 void
|
|
|
276 bin_search_tree_no_data_
|
|
|
277 <
|
|
|
278 Key,
|
|
|
279 Mapped,
|
|
|
280 Cmp_Fn,
|
|
|
281 Node_And_It_Traits,
|
|
|
282 Allocator >::apply_update (node_pointer p_nd, Node_Update_ *)
|
|
|
283 {
|
|
|
284 node_update ()((p_nd), ((0)));
|
|
|
285 }
|
|
|
286 }
|
|
|
287 namespace detail
|
|
|
288 {
|
|
|
289 template < typename Key, typename Mapped, typename Cmp_Fn, typename Node_And_It_Traits, typename Allocator > class rb_tree_no_data_:
|
|
|
290 bin_search_tree_no_data_
|
|
|
291 < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator >
|
|
|
292 {
|
|
|
293 typedef
|
|
|
294 bin_search_tree_no_data_
|
|
|
295 < Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator > base_type;
|
|
|
296 typedef typename base_type::node_pointer node_pointer;
|
|
|
297 public:
|
|
|
298 typedef typename base_type::const_reference const_reference;
|
|
|
299 typedef typename base_type::point_iterator point_iterator;
|
|
|
300 std::pair < point_iterator, bool > insert (const_reference);
|
|
|
301 void insert_fixup (node_pointer);
|
|
|
302 };
|
|
|
303 template
|
|
|
304 <
|
|
|
305 typename
|
|
|
306 Key,
|
|
|
307 typename
|
|
|
308 Mapped,
|
|
|
309 typename
|
|
|
310 Cmp_Fn,
|
|
|
311 typename
|
|
|
312 Node_And_It_Traits,
|
|
|
313 typename
|
|
|
314 Allocator
|
|
|
315 >
|
|
|
316 std::pair
|
|
|
317 <
|
|
|
318 typename
|
|
|
319 rb_tree_no_data_
|
|
|
320 <
|
|
|
321 Key,
|
|
|
322 Mapped,
|
|
|
323 Cmp_Fn,
|
|
|
324 Node_And_It_Traits,
|
|
|
325 Allocator
|
|
|
326 >::point_iterator,
|
|
|
327 bool
|
|
|
328 >
|
|
|
329 rb_tree_no_data_
|
|
|
330 <
|
|
|
331 Key,
|
|
|
332 Mapped,
|
|
|
333 Cmp_Fn, Node_And_It_Traits, Allocator >::insert (const_reference)
|
|
|
334 {
|
|
|
335 std::pair < point_iterator, bool > ins_pair;
|
|
|
336 {
|
|
|
337 insert_fixup (ins_pair.first.m_p_nd);
|
|
|
338 }
|
|
|
339 }
|
|
|
340 template
|
|
|
341 <
|
|
|
342 typename
|
|
|
343 Key,
|
|
|
344 typename
|
|
|
345 Mapped,
|
|
|
346 typename
|
|
|
347 Cmp_Fn,
|
|
|
348 typename
|
|
|
349 Node_And_It_Traits,
|
|
|
350 typename
|
|
|
351 Allocator
|
|
|
352 >
|
|
|
353 void
|
|
|
354 rb_tree_no_data_
|
|
|
355 <
|
|
|
356 Key,
|
|
|
357 Mapped,
|
|
|
358 Cmp_Fn,
|
|
|
359 Node_And_It_Traits, Allocator >::insert_fixup (node_pointer p_nd)
|
|
|
360 {
|
|
|
361 {
|
|
|
362 {
|
|
|
363 {
|
|
|
364 this->rotate_right (p_nd);
|
|
|
365 }
|
|
|
366 }
|
|
|
367 }
|
|
|
368 }
|
|
|
369 template
|
|
|
370 <
|
|
|
371 typename,
|
|
|
372 typename, typename, typename, typename > struct container_base_dispatch;
|
|
|
373 template
|
|
|
374 <
|
|
|
375 typename
|
|
|
376 Key,
|
|
|
377 typename
|
|
|
378 Policy_Tl,
|
|
|
379 typename
|
|
|
380 Alloc
|
|
|
381 >
|
|
|
382 struct
|
|
|
383 container_base_dispatch
|
|
|
384 <Key, null_mapped_type, rb_tree_tag, Policy_Tl, Alloc >
|
|
|
385 {
|
|
|
386 typedef __gnu_cxx::typelist::at_index < Policy_Tl, 0 > at0;
|
|
|
387 typedef typename at0::type at0t;
|
|
|
388 typedef __gnu_cxx::typelist::at_index < Policy_Tl, 1 > at1;
|
|
|
389 typedef typename at1::type at1t;
|
|
|
390 typedef
|
|
|
391 rb_tree_no_data_ < Key, null_mapped_type, at0t, at1t, Alloc > type;
|
|
|
392 };
|
|
|
393 template
|
|
|
394 <
|
|
|
395 typename
|
|
|
396 Node_Pointer,
|
|
|
397 typename,
|
|
|
398 typename,
|
|
|
399 typename,
|
|
|
400 typename, typename, bool, class > class bin_search_tree_const_it_
|
|
|
401 {
|
|
|
402 public:
|
|
|
403 Node_Pointer m_p_nd;
|
|
|
404 };
|
|
|
405 template
|
|
|
406 <
|
|
|
407 typename
|
|
|
408 Node,
|
|
|
409 class
|
|
|
410 Const_Iterator,
|
|
|
411 class Iterator, class Allocator > class bin_search_tree_const_node_it_
|
|
|
412 {
|
|
|
413 typedef
|
|
|
414 typename
|
|
|
415 Allocator::template rebind < Node >::other::pointer node_pointer;
|
|
|
416 public:
|
|
|
417 typedef typename Node::metadata_type metadata_type;
|
|
|
418 typedef
|
|
|
419 typename
|
|
|
420 Allocator::template
|
|
|
421 rebind
|
|
|
422 < metadata_type >::other::const_reference const_metadata_reference;
|
|
|
423 bin_search_tree_const_node_it_ (node_pointer p_nd):
|
|
|
424 m_p_nd ((p_nd))
|
|
|
425 {}
|
|
|
426 const_metadata_reference get_metadata ()
|
|
|
427 {
|
|
|
428 return (m_p_nd->get_metadata ());
|
|
|
429 }
|
|
|
430 bin_search_tree_const_node_it_ ()
|
|
|
431 {}
|
|
|
432 bin_search_tree_const_node_it_
|
|
|
433 < Node, Const_Iterator, Iterator, Allocator > get_r_child ()
|
|
|
434 {
|
|
|
435 return ((m_p_nd->m_p_right));
|
|
|
436 }
|
|
|
437 bool operator == (bin_search_tree_const_node_it_)
|
|
131
|
438 { return true; }
|
|
111
|
439 node_pointer m_p_nd;
|
|
|
440 };
|
|
|
441 template
|
|
|
442 <
|
|
|
443 typename,
|
|
|
444 typename,
|
|
|
445 class,
|
|
|
446 template
|
|
|
447 <
|
|
|
448 typename,
|
|
|
449 class,
|
|
|
450 class, class > class, class, class > struct bin_search_tree_traits;
|
|
|
451 template
|
|
|
452 <
|
|
|
453 typename
|
|
|
454 Key,
|
|
|
455 class
|
|
|
456 Cmp_Fn,
|
|
|
457 template
|
|
|
458 <
|
|
|
459 typename,
|
|
|
460 class,
|
|
|
461 class,
|
|
|
462 class
|
|
|
463 >
|
|
|
464 class
|
|
|
465 Node_Update,
|
|
|
466 class
|
|
|
467 Node,
|
|
|
468 class
|
|
|
469 Allocator
|
|
|
470 >
|
|
|
471 struct
|
|
|
472 bin_search_tree_traits
|
|
|
473 <Key, null_mapped_type, Cmp_Fn, Node_Update, Node, Allocator >
|
|
|
474 {
|
|
|
475 typedef
|
|
|
476 types_traits < Key, null_mapped_type, Allocator, false > type_traits;
|
|
|
477 typedef Node node;
|
|
|
478 typedef
|
|
|
479 bin_search_tree_const_it_
|
|
|
480 <
|
|
|
481 typename
|
|
|
482 Allocator::template
|
|
|
483 rebind
|
|
|
484 <
|
|
|
485 node
|
|
|
486 >::other::pointer,
|
|
|
487 typename
|
|
|
488 type_traits::value_type,
|
|
|
489 typename
|
|
|
490 type_traits::pointer,
|
|
|
491 typename
|
|
|
492 type_traits::const_pointer,
|
|
|
493 typename
|
|
|
494 type_traits::reference,
|
|
|
495 typename
|
|
|
496 type_traits::const_reference, true, Allocator > const_point_iterator;
|
|
|
497 typedef const_point_iterator point_iterator;
|
|
|
498 typedef
|
|
|
499 bin_search_tree_const_node_it_
|
|
|
500 <
|
|
|
501 Node,
|
|
|
502 const_point_iterator, point_iterator, Allocator > const_node_iterator;
|
|
|
503 typedef const_node_iterator node_iterator;
|
|
|
504 typedef
|
|
|
505 Node_Update
|
|
|
506 < const_node_iterator, node_iterator, Cmp_Fn, Allocator > node_update;
|
|
|
507 };
|
|
|
508 template < typename Node_Update, bool > struct tree_metadata_helper
|
|
|
509 {
|
|
|
510 typedef typename Node_Update::metadata_type type;
|
|
|
511 };
|
|
|
512 template
|
|
|
513 <
|
|
|
514 typename
|
|
|
515 Key,
|
|
|
516 typename
|
|
|
517 Data,
|
|
|
518 class
|
|
|
519 Cmp_Fn,
|
|
|
520 template
|
|
|
521 <
|
|
|
522 typename,
|
|
|
523 class,
|
|
|
524 class,
|
|
|
525 class
|
|
|
526 >
|
|
|
527 class Node_Update, class Allocator > struct tree_node_metadata_selector
|
|
|
528 {
|
|
|
529 typedef
|
|
|
530 dumconst_node_iterator < Key, Data, Allocator > dumconst_node_it;
|
|
|
531 enum
|
|
|
532 {
|
|
|
533 null_update = is_same < Node_Update < dumconst_node_it,
|
|
|
534 dumconst_node_it,
|
|
|
535 Cmp_Fn,
|
|
|
536 Allocator >,
|
|
|
537 null_tree_node_update < dumconst_node_it,
|
|
|
538 dumconst_node_it,
|
|
|
539 Cmp_Fn,
|
|
|
540 Allocator > >::value
|
|
|
541 };
|
|
|
542 typedef
|
|
|
543 typename
|
|
|
544 tree_metadata_helper
|
|
|
545 <
|
|
|
546 Node_Update
|
|
|
547 <
|
|
|
548 dumconst_node_it,
|
|
|
549 dumconst_node_it, Cmp_Fn, Allocator >, null_update >::type type;
|
|
|
550 };
|
|
|
551 template
|
|
|
552 <
|
|
|
553 typename,
|
|
|
554 typename,
|
|
|
555 class,
|
|
|
556 template
|
|
|
557 <
|
|
|
558 typename,
|
|
|
559 class, class, class > class, class, class > struct tree_traits;
|
|
|
560 template < typename Value_Type, class Metadata, class Allocator > struct rb_tree_node_
|
|
|
561 {
|
|
|
562 typedef Metadata metadata_type;
|
|
|
563 typedef
|
|
|
564 typename
|
|
|
565 Allocator::template
|
|
|
566 rebind
|
|
|
567 <
|
|
|
568 rb_tree_node_
|
|
|
569 < Value_Type, Metadata, Allocator > >::other::pointer node_pointer;
|
|
|
570 typedef
|
|
|
571 typename
|
|
|
572 Allocator::template
|
|
|
573 rebind < metadata_type >::other::reference metadata_reference;
|
|
|
574 metadata_reference get_metadata ()
|
|
|
575 {
|
|
|
576 return m_metadata;
|
|
|
577 }
|
|
|
578 node_pointer m_p_right;
|
|
|
579 node_pointer m_p_parent;
|
|
|
580 metadata_type m_metadata;
|
|
|
581 };
|
|
|
582 template
|
|
|
583 <
|
|
|
584 typename
|
|
|
585 Key,
|
|
|
586 typename
|
|
|
587 Mapped,
|
|
|
588 typename
|
|
|
589 Cmp_Fn,
|
|
|
590 template
|
|
|
591 <
|
|
|
592 typename,
|
|
|
593 class,
|
|
|
594 class,
|
|
|
595 class
|
|
|
596 >
|
|
|
597 class
|
|
|
598 Node_Update,
|
|
|
599 typename
|
|
|
600 Allocator
|
|
|
601 >
|
|
|
602 struct
|
|
|
603 tree_traits
|
|
|
604 <Key,
|
|
|
605 Mapped,
|
|
|
606 Cmp_Fn,
|
|
|
607 Node_Update,
|
|
|
608 rb_tree_tag,
|
|
|
609 Allocator
|
|
|
610 >:bin_search_tree_traits
|
|
|
611 <
|
|
|
612 Key,
|
|
|
613 Mapped,
|
|
|
614 Cmp_Fn,
|
|
|
615 Node_Update,
|
|
|
616 rb_tree_node_
|
|
|
617 <
|
|
|
618 typename
|
|
|
619 types_traits
|
|
|
620 <
|
|
|
621 Key,
|
|
|
622 Mapped,
|
|
|
623 Allocator,
|
|
|
624 false
|
|
|
625 >::value_type,
|
|
|
626 typename
|
|
|
627 tree_node_metadata_selector
|
|
|
628 <
|
|
|
629 Key,
|
|
|
630 Mapped, Cmp_Fn, Node_Update, Allocator >::type, Allocator >, Allocator >
|
|
|
631 {};
|
|
|
632 }
|
|
|
633 template < typename Key, typename Mapped, typename Tag, typename Policy_Tl, typename Allocator > class container_base:
|
|
|
634 public
|
|
|
635 detail::container_base_dispatch
|
|
|
636 < Key, Mapped, Tag, Policy_Tl, Allocator >::type
|
|
|
637 {};
|
|
|
638 template < typename Key, typename Mapped, typename Tag, typename, typename Policy_Tl, typename Allocator > class basic_tree:
|
|
|
639 public
|
|
|
640 container_base < Key, Mapped, Tag, Policy_Tl, Allocator >
|
|
|
641 {};
|
|
|
642 template
|
|
|
643 <
|
|
|
644 typename
|
|
|
645 Key,
|
|
|
646 typename
|
|
|
647 Mapped,
|
|
|
648 typename
|
|
|
649 Cmp_Fn
|
|
|
650 =
|
|
|
651 std::less
|
|
|
652 <
|
|
|
653 Key
|
|
|
654 >,
|
|
|
655 typename
|
|
|
656 Tag
|
|
|
657 =
|
|
|
658 rb_tree_tag,
|
|
|
659 template
|
|
|
660 <
|
|
|
661 typename,
|
|
|
662 typename,
|
|
|
663 typename,
|
|
|
664 typename
|
|
|
665 >
|
|
|
666 class
|
|
|
667 Node_Update
|
|
|
668 =
|
|
|
669 null_tree_node_update,
|
|
|
670 typename
|
|
|
671 Allocator
|
|
|
672 =
|
|
|
673 std::allocator
|
|
|
674 <
|
|
|
675 char
|
|
|
676 > >class
|
|
|
677 tree:public
|
|
|
678 basic_tree
|
|
|
679 <
|
|
|
680 Key,
|
|
|
681 Mapped,
|
|
|
682 Tag,
|
|
|
683 detail::tree_traits
|
|
|
684 <
|
|
|
685 Key,
|
|
|
686 Mapped,
|
|
|
687 Cmp_Fn,
|
|
|
688 Node_Update,
|
|
|
689 Tag,
|
|
|
690 Allocator
|
|
|
691 >,
|
|
|
692 typename
|
|
|
693 __gnu_cxx::typelist::create2
|
|
|
694 <
|
|
|
695 Cmp_Fn,
|
|
|
696 detail::tree_traits
|
|
|
697 < Key, Mapped, Cmp_Fn, Node_Update, Tag, Allocator > >::type, Allocator >
|
|
|
698 {};
|
|
|
699 }
|
|
|
700 using namespace std;
|
|
|
701 using namespace __gnu_pbds;
|
|
|
702 typedef
|
|
|
703 tree
|
|
|
704 <
|
|
|
705 int,
|
|
|
706 null_mapped_type,
|
|
|
707 less < int >, rb_tree_tag, tree_order_statistics_node_update > set_t;
|
|
131
|
708 int main ()
|
|
111
|
709 {
|
|
|
710 set_t s;
|
|
|
711 s.insert (12);
|
|
|
712 }
|
