old-autovect-branch/libstdc++-v3/include/ext/pb_assoc/assoc_cntnr.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 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 2, 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 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /**
  41  * @file assoc_cntnr.hpp
  42  * Contains associative containers.
  43  */
  44
  45 #ifndef ASSOC_CNTNR_HPP
  46 #define ASSOC_CNTNR_HPP
  47
  48 #include <ext/pb_assoc/ms_trait.hpp>
  49 #include <ext/pb_assoc/ds_trait.hpp>
  50 #include <ext/pb_assoc/detail/type_utils.hpp>
  51 #include <ext/pb_assoc/detail/typelist.hpp>
  52 #include <ext/pb_assoc/detail/standard_policies.hpp>
  53 #include <ext/pb_assoc/detail/mapping_level_imp.hpp>
  54 #include <ext/pb_assoc/detail/assoc_cntnr_base.hpp>
  55 #include <ext/pb_assoc/detail/value_type_adapter/value_type_adapter.hpp>
  56
  57 namespace pb_assoc
  58 {
  59
  60 #define PB_ASSOC_CLASS_T_DEC \
  61         template< \
  62                 typename Key, \
  63                 typename Data, \
  64                 class DS_Tag, \
  65                 class Policy_Tl, \
  66                 class Allocator>
  67
  68 #define PB_ASSOC_CLASS_C_DEC \
  69         basic_assoc_cntnr< \
  70                 Key, \
  71                 Data, \
  72                 DS_Tag, \
  73                 Policy_Tl, \
  74                 Allocator>
  75
  76 #define PB_ASSOC_BASE_C_DEC \
  77         detail::assoc_cntnr_base< \
  78                 Key, \
  79                 Data, \
  80                 DS_Tag, \
  81                 Policy_Tl, \
  82                 Allocator>::type
  83
  84 #define PB_ASSOC_DIRECT_BASE_C_DEC \
  85         detail::assoc_cntnr_base< \
  86                 Key, \
  87                 Data, \
  88                 DS_Tag, \
  89                 Policy_Tl, \
  90                 Allocator>::type
  91
  92   template<typename Key,
  93            typename Data,
  94            class DS_Tag,
  95            class Policy_Tl,
  96            class Allocator>
  97   class basic_assoc_cntnr
  98   : public detail::assoc_cntnr_base<Key, Data, DS_Tag, Policy_Tl, Allocator>::type
  99   {
 100   public:
 101     typedef typename Allocator::size_type size_type;
 102     typedef typename Allocator::difference_type difference_type;
 103     typedef DS_Tag ds_category;
 104     typedef data_enabled_ms_tag ms_category;
 105     typedef Allocator allocator;
 106
 107     typedef
 108     typename allocator::template rebind<
 109       Key>::other::value_type
 110     key_type;
 111
 112     typedef
 113     typename allocator::template rebind<
 114       Key>::other::reference
 115     key_reference;
 116
 117     typedef
 118     typename allocator::template rebind<
 119       Key>::other::const_reference
 120     const_key_reference;
 121
 122     typedef
 123     typename allocator::template rebind<
 124       Key>::other::pointer
 125     key_pointer;
 126
 127     typedef
 128     typename allocator::template rebind<
 129       Key>::other::const_pointer
 130     const_key_pointer;
 131
 132     typedef
 133     typename allocator::template rebind<
 134       Data>::other::value_type
 135     data_type;
 136
 137     typedef
 138     typename allocator::template rebind<
 139       Data>::other::reference
 140     data_reference;
 141
 142     typedef
 143     typename allocator::template rebind<
 144       Data>::other::const_reference
 145     const_data_reference;
 146
 147     typedef
 148     typename allocator::template rebind<
 149       Data>::other::pointer
 150     data_pointer;
 151
 152     typedef
 153     typename allocator::template rebind<
 154       Data>::other::const_pointer
 155     const_data_pointer;
 156
 157     typedef
 158     typename allocator::template rebind<
 159       std::pair<const key_type, data_type> >::other::value_type
 160     value_type;
 161
 162     typedef
 163     typename allocator::template rebind<
 164       std::pair<const key_type, data_type> >::other::reference
 165     reference;
 166
 167     typedef
 168     typename allocator::template rebind<
 169       std::pair<const key_type, data_type> >::other::const_reference
 170     const_reference;
 171
 172     typedef
 173     typename allocator::template rebind<
 174       std::pair<const key_type, data_type> >::other::pointer
 175     pointer;
 176
 177     typedef
 178     typename allocator::template rebind<
 179       std::pair<const key_type, data_type> >::other::const_pointer
 180     const_pointer;
 181
 182     typedef
 183     typename PB_ASSOC_BASE_C_DEC::const_find_iterator
 184     const_find_iterator;
 185
 186     typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
 187
 188     typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
 189
 190     typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
 191
 192   public:
 193
 194     virtual
 195     ~basic_assoc_cntnr();
 196
 197     inline size_type
 198     size() const;
 199
 200     inline size_type
 201     max_size() const;
 202
 203     inline bool
 204     empty() const;
 205
 206     inline static const_key_reference
 207     extract_key(const_reference r_val);
 208
 209     inline std::pair<find_iterator, bool>
 210     insert(const_reference r_val);
 211
 212     inline data_reference
 213     operator[](const_key_reference r_key);
 214
 215     inline find_iterator
 216     find(const_key_reference r_key)
 217     {
 218       return (my_base::find(r_key));
 219     }
 220
 221     inline const_find_iterator
 222     find(const_key_reference r_key) const
 223     {
 224       return (my_base::find(r_key));
 225     }
 226
 227     inline const_data_reference
 228     operator[](const_key_reference r_key) const;
 229
 230     inline size_type
 231     erase(const_key_reference r_key);
 232
 233     template<class Pred>
 234     inline size_type
 235     erase_if(Pred prd);
 236
 237     void
 238     clear();
 239
 240     inline iterator
 241     begin();
 242
 243     inline const_iterator
 244     begin() const;
 245
 246     inline iterator
 247     end();
 248
 249     inline const_iterator
 250     end() const;
 251
 252   protected:
 253
 254 #define PB_ASSOC_CLASS_NAME basic_assoc_cntnr
 255
 256 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
 257         typename PB_ASSOC_DIRECT_BASE_C_DEC
 258
 259 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
 260
 261 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
 262
 263 #undef PB_ASSOC_CLASS_NAME
 264
 265   private:
 266     typedef typename PB_ASSOC_BASE_C_DEC my_base;
 267
 268   private:
 269     basic_assoc_cntnr&
 270     operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
 271   };
 272
 273 #include <ext/pb_assoc/detail/basic_assoc_cntnr/constructors_destructor_fn_imps.hpp>
 274 #include <ext/pb_assoc/detail/basic_assoc_cntnr/iterators_fn_imps.hpp>
 275 #include <ext/pb_assoc/detail/basic_assoc_cntnr/info_fn_imps.hpp>
 276 #include <ext/pb_assoc/detail/basic_assoc_cntnr/erase_fn_imps.hpp>
 277 #include <ext/pb_assoc/detail/basic_assoc_cntnr/insert_fn_imps.hpp>
 278 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_insert_fn_imps.hpp>
 279 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_find_fn_imps.hpp>
 280 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_extract_key.hpp>
 281
 282 #undef PB_ASSOC_CLASS_T_DEC
 283
 284 #undef PB_ASSOC_CLASS_C_DEC
 285
 286 #undef PB_ASSOC_BASE_C_DEC
 287
 288 #undef PB_ASSOC_DIRECT_BASE_C_DEC
 289
 290 #define PB_ASSOC_CLASS_T_DEC \
 291         template< \
 292                 typename Key, \
 293                 class Cntnr, \
 294                 class DS_Tag, \
 295                 class Policy_Tl, \
 296                 class Allocator>
 297
 298 #define PB_ASSOC_CLASS_C_DEC \
 299         basic_assoc_cntnr< \
 300                 Key, \
 301                 compound_data_type< \
 302                         Cntnr>, \
 303                 DS_Tag, \
 304                 Policy_Tl, \
 305                 Allocator>
 306
 307 #define PB_ASSOC_DIRECT_BASE_C_DEC \
 308         detail::value_type_adapter< \
 309                 Key, \
 310                 compound_data_type< \
 311                         Cntnr>, \
 312                 DS_Tag, \
 313                 Policy_Tl, \
 314                 Allocator, \
 315                 detail::mapping_level_imp< \
 316                         compound_data_type< \
 317                                 Cntnr> >::value - 1>
 318
 319 #define PB_ASSOC_BASE_C_DEC \
 320         detail::assoc_cntnr_base< \
 321                 Key, \
 322                 compound_data_type< \
 323                         Cntnr>, \
 324                 DS_Tag, \
 325                 Policy_Tl, \
 326                 Allocator>::type
 327
 328   template<typename Key,
 329            class Cntnr,
 330            class DS_Tag,
 331            class Policy_Tl,
 332            class Allocator>
 333   class basic_assoc_cntnr<Key, compound_data_type< Cntnr>, DS_Tag, Policy_Tl, Allocator> : public PB_ASSOC_DIRECT_BASE_C_DEC
 334   {
 335   public:
 336     typedef typename Allocator::size_type size_type;
 337     typedef typename Allocator::difference_type difference_type;
 338     typedef DS_Tag ds_category;
 339     typedef compound_data_enabled_ms_tag ms_category;
 340     typedef Allocator allocator;
 341
 342     typedef
 343     typename allocator::template rebind<
 344       Key>::other::value_type
 345     key_type;
 346
 347     typedef
 348     typename allocator::template rebind<
 349       Key>::other::reference
 350     key_reference;
 351
 352     typedef
 353     typename allocator::template rebind<
 354       Key>::other::const_reference
 355     const_key_reference;
 356
 357     typedef
 358     typename allocator::template rebind<
 359       Key>::other::pointer
 360     key_pointer;
 361
 362     typedef
 363     typename allocator::template rebind<
 364       Key>::other::const_pointer
 365     const_key_pointer;
 366
 367     typedef
 368     typename allocator::template rebind<
 369       Cntnr>::other::value_type
 370     data_type;
 371
 372     typedef
 373     typename allocator::template rebind<
 374       Cntnr>::other::reference
 375     data_reference;
 376
 377     typedef
 378     typename allocator::template rebind<
 379       Cntnr>::other::const_reference
 380     const_data_reference;
 381
 382     typedef
 383     typename allocator::template rebind<
 384       Cntnr>::other::pointer
 385     data_pointer;
 386
 387     typedef
 388     typename allocator::template rebind<
 389       Cntnr>::other::const_pointer
 390     const_data_pointer;
 391
 392     typedef
 393     typename allocator::template rebind<
 394       std::pair<const key_type, Cntnr> >::other::value_type
 395     value_type;
 396
 397     typedef
 398     typename allocator::template rebind<
 399       std::pair<const key_type, Cntnr> >::other::reference
 400     reference;
 401
 402     typedef
 403     typename allocator::template rebind<
 404       std::pair<const key_type, Cntnr> >::other::const_reference
 405     const_reference;
 406
 407     typedef
 408     typename allocator::template rebind<
 409       std::pair<const key_type, Cntnr> >::other::pointer
 410     pointer;
 411
 412     typedef
 413     typename allocator::template rebind<
 414       std::pair<const key_type, Cntnr> >::other::const_pointer
 415     const_pointer;
 416
 417     typedef
 418     typename PB_ASSOC_BASE_C_DEC::const_find_iterator
 419     const_find_iterator;
 420
 421     typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
 422
 423     typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
 424
 425     typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
 426
 427     template<int Mapping_Level>
 428     struct rebind
 429     {
 430     private:
 431       enum
 432         {
 433           mapping_level =
 434           detail::mapping_level_imp<compound_data_type<Cntnr> >::value
 435         };
 436
 437     public:
 438       typedef
 439       detail::value_type_adapter<
 440         Key,
 441         compound_data_type<
 442         Cntnr>,
 443         DS_Tag,
 444         Policy_Tl,
 445         Allocator,
 446         mapping_level - Mapping_Level>
 447       other;
 448     };
 449
 450   public:
 451
 452     virtual
 453     ~basic_assoc_cntnr();
 454
 455     inline size_type
 456     size() const;
 457
 458     inline size_type
 459     max_size() const;
 460
 461     inline bool
 462     empty() const;
 463
 464     inline static const_key_reference
 465     extract_key(const_reference r_val);
 466
 467     inline std::pair<find_iterator, bool>
 468     insert(const_reference r_val);
 469
 470     inline data_reference
 471     operator[](const_key_reference r_key);
 472
 473     inline find_iterator
 474     find(const_key_reference r_key)
 475     {
 476       return (my_base::find(r_key));
 477     }
 478
 479     inline const_find_iterator
 480     find(const_key_reference r_key) const
 481     {
 482       return (my_base::find(r_key));
 483     }
 484
 485     inline const_data_reference
 486     operator[](const_key_reference r_key) const;
 487
 488     inline size_type
 489     erase(const_key_reference r_key);
 490
 491     template<class Pred>
 492     inline size_type
 493     erase_if(Pred prd);
 494
 495     void
 496     clear();
 497
 498     inline iterator
 499     begin();
 500
 501     inline const_iterator
 502     begin() const;
 503
 504     inline iterator
 505     end();
 506
 507     inline const_iterator
 508     end() const;
 509
 510   protected:
 511
 512 #define PB_ASSOC_CLASS_NAME basic_assoc_cntnr
 513
 514 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
 515         typename PB_ASSOC_DIRECT_BASE_C_DEC
 516
 517 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
 518
 519 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
 520
 521 #undef PB_ASSOC_CLASS_NAME
 522
 523   private:
 524     typedef typename PB_ASSOC_BASE_C_DEC my_base;
 525
 526   private:
 527     basic_assoc_cntnr&
 528     operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
 529   };
 530
 531 #include <ext/pb_assoc/detail/basic_assoc_cntnr/constructors_destructor_fn_imps.hpp>
 532 #include <ext/pb_assoc/detail/basic_assoc_cntnr/iterators_fn_imps.hpp>
 533 #include <ext/pb_assoc/detail/basic_assoc_cntnr/info_fn_imps.hpp>
 534 #include <ext/pb_assoc/detail/basic_assoc_cntnr/erase_fn_imps.hpp>
 535 #include <ext/pb_assoc/detail/basic_assoc_cntnr/insert_fn_imps.hpp>
 536 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_insert_fn_imps.hpp>
 537 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_find_fn_imps.hpp>
 538 #include <ext/pb_assoc/detail/basic_assoc_cntnr/d_extract_key.hpp>
 539
 540 #undef PB_ASSOC_CLASS_T_DEC
 541
 542 #undef PB_ASSOC_CLASS_C_DEC
 543
 544 #undef PB_ASSOC_BASE_C_DEC
 545
 546 #undef PB_ASSOC_DIRECT_BASE_C_DEC
 547
 548 #define PB_ASSOC_CLASS_T_DEC \
 549         template<typename Key, class DS_Tag, class Policy_Tl, class Allocator>
 550
 551 #define PB_ASSOC_CLASS_C_DEC \
 552         basic_assoc_cntnr< \
 553                 Key, \
 554                 null_data_type, \
 555                 DS_Tag, \
 556                 Policy_Tl, \
 557                 Allocator>
 558
 559 #define PB_ASSOC_BASE_C_DEC \
 560         detail::assoc_cntnr_base< \
 561                 Key, \
 562                 null_data_type, \
 563                 DS_Tag, \
 564                 Policy_Tl, \
 565                 Allocator>::type
 566
 567   template<typename Key, class DS_Tag, class Policy_Tl, class Allocator>
 568   class basic_assoc_cntnr<Key, null_data_type, DS_Tag, Policy_Tl, Allocator> : public PB_ASSOC_BASE_C_DEC
 569   {
 570   public:
 571     typedef typename Allocator::size_type size_type;
 572     typedef typename Allocator::difference_type difference_type;
 573     typedef DS_Tag ds_category;
 574     typedef basic_ms_tag ms_category;
 575     typedef Allocator allocator;
 576
 577     typedef
 578     typename allocator::template rebind<
 579       Key>::other::value_type
 580     key_type;
 581
 582     typedef
 583     typename allocator::template rebind<
 584       Key>::other::reference
 585     key_reference;
 586
 587     typedef
 588     typename allocator::template rebind<
 589       Key>::other::const_reference
 590     const_key_reference;
 591
 592     typedef
 593     typename allocator::template rebind<
 594       Key>::other::pointer
 595     key_pointer;
 596
 597     typedef
 598     typename allocator::template rebind<
 599       Key>::other::const_pointer
 600     const_key_pointer;
 601
 602     typedef
 603     typename allocator::template rebind<
 604       key_type>::other::value_type
 605     value_type;
 606
 607     typedef
 608     typename allocator::template rebind<
 609       key_type>::other::const_reference
 610     reference;
 611
 612     typedef
 613     typename allocator::template rebind<
 614       key_type>::other::const_reference
 615     const_reference;
 616
 617     typedef
 618     typename allocator::template rebind<
 619       key_type>::other::const_pointer
 620     pointer;
 621
 622     typedef
 623     typename allocator::template rebind<key_type>::other::const_pointer
 624     const_pointer;
 625
 626     typedef
 627     typename PB_ASSOC_BASE_C_DEC::const_find_iterator
 628     const_find_iterator;
 629
 630     typedef typename PB_ASSOC_BASE_C_DEC::find_iterator find_iterator;
 631
 632     typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
 633
 634     typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
 635
 636   public:
 637
 638     virtual
 639     ~basic_assoc_cntnr();
 640
 641     inline size_type
 642     size() const;
 643
 644     inline size_type
 645     max_size() const;
 646
 647     inline bool
 648     empty() const;
 649
 650     inline static const_key_reference
 651     extract_key(const_reference r_val);
 652
 653     inline std::pair<find_iterator, bool>
 654     insert(const_reference r_val);
 655
 656     inline find_iterator
 657     find(const_key_reference r_key)
 658     { return (my_base::find(r_key)); }
 659
 660     inline const_find_iterator
 661     find(const_key_reference r_key) const
 662     { return (my_base::find(r_key)); }
 663
 664     inline size_type
 665     erase(const_key_reference r_key);
 666
 667     template<class Pred>
 668     inline size_type
 669     erase_if(Pred prd);
 670
 671     void
 672     clear();
 673
 674     inline iterator
 675     begin();
 676
 677     inline const_iterator
 678     begin() const;
 679
 680     inline iterator
 681     end();
 682
 683     inline const_iterator
 684     end() const;
 685
 686   protected:
 687
 688 #define PB_ASSOC_CLASS_NAME basic_assoc_cntnr
 689
 690 #define PB_ASSOC_DIRECT_BASE_C_DEC PB_ASSOC_BASE_C_DEC
 691
 692 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
 693         typename PB_ASSOC_DIRECT_BASE_C_DEC
 694
 695 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
 696
 697 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
 698
 699 #undef PB_ASSOC_DIRECT_BASE_C_DEC
 700
 701 #undef PB_ASSOC_CLASS_NAME
 702
 703   private:
 704     typedef typename PB_ASSOC_BASE_C_DEC my_base;
 705
 706   private:
 707     basic_assoc_cntnr&
 708     operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
 709   };
 710
 711 #include <ext/pb_assoc/detail/basic_assoc_cntnr/constructors_destructor_fn_imps.hpp>
 712 #include <ext/pb_assoc/detail/basic_assoc_cntnr/iterators_fn_imps.hpp>
 713 #include <ext/pb_assoc/detail/basic_assoc_cntnr/info_fn_imps.hpp>
 714 #include <ext/pb_assoc/detail/basic_assoc_cntnr/erase_fn_imps.hpp>
 715 #include <ext/pb_assoc/detail/basic_assoc_cntnr/insert_fn_imps.hpp>
 716 #include <ext/pb_assoc/detail/basic_assoc_cntnr/extract_key.hpp>
 717
 718 #undef PB_ASSOC_CLASS_T_DEC
 719
 720 #undef PB_ASSOC_CLASS_C_DEC
 721
 722 #undef PB_ASSOC_BASE_C_DEC
 723
 724 #define PB_ASSOC_TYPELIST_CHAIN1(X0) pb_assoc::detail::typelist_chain<X0, pb_assoc::detail::null_type>
 725 #define PB_ASSOC_TYPELIST_CHAIN2(X0, X1) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN1(X1) >
 726 #define PB_ASSOC_TYPELIST_CHAIN3(X0, X1, X2) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN2(X1, X2) >
 727 #define PB_ASSOC_TYPELIST_CHAIN4(X0, X1, X2, X3) pb_assoc::detail::typelist_chain<X0,  PB_ASSOC_TYPELIST_CHAIN3(X1, X2, X3) >
 728 #define PB_ASSOC_TYPELIST_CHAIN5(X0, X1, X2, X3, X4) pb_assoc::detail::typelist_chain<X0,  PB_ASSOC_TYPELIST_CHAIN4(X1, X2, X3, X4) >
 729 #define PB_ASSOC_TYPELIST_CHAIN6(X0, X1, X2, X3, X4, X5) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN5(X1, X2, X3, X4, X5) >
 730 #define PB_ASSOC_TYPELIST_CHAIN7(X0, X1, X2, X3, X4, X5, X6) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN6(X1, X2, X3, X4, X5, X6) >
 731 #define PB_ASSOC_TYPELIST_CHAIN8(X0, X1, X2, X3, X4, X5, X6, X7) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN7(X1, X2, X3, X4, X5, X6, X7) >
 732 #define PB_ASSOC_TYPELIST_CHAIN9(X0, X1, X2, X3, X4, X5, X6, X7, X8) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN8(X1, X2, X3, X4, X5, X6, X7, X8) >
 733 #define PB_ASSOC_TYPELIST_CHAIN10(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN9(X1, X2, X3, X4, X5, X6, X7, X8, X9) >
 734 #define PB_ASSOC_TYPELIST_CHAIN11(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN10(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10) >
 735 #define PB_ASSOC_TYPELIST_CHAIN12(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN11(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11) >
 736 #define PB_ASSOC_TYPELIST_CHAIN13(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN12(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12) >
 737 #define PB_ASSOC_TYPELIST_CHAIN14(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN13(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13) >
 738 #define PB_ASSOC_TYPELIST_CHAIN15(X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14) pb_assoc::detail::typelist_chain<X0, PB_ASSOC_TYPELIST_CHAIN14(X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11, X12, X13, X14) >
 739
 740 #define PB_ASSOC_CLASS_T_DEC \
 741         template< \
 742                 typename Key, \
 743                 typename Data, \
 744                 class Hash_Fn, \
 745                 class Eq_Fn, \
 746                 class Resize_Policy, \
 747                 bool Store_Hash, \
 748                 class DS_Tag, \
 749                 class Policy_TL, \
 750                 class Allocator>
 751
 752 #define PB_ASSOC_CLASS_C_DEC \
 753         basic_hash_assoc_cntnr< \
 754                 Key, \
 755                 Data, \
 756                 Hash_Fn, \
 757                 Eq_Fn, \
 758                 Resize_Policy, \
 759                 Store_Hash, \
 760                 DS_Tag, \
 761                 Policy_TL, \
 762                 Allocator>
 763
 764 #define PB_ASSOC_BASE_C_DEC \
 765         basic_assoc_cntnr< \
 766                 Key, \
 767                 Data, \
 768                 DS_Tag, \
 769                 typename pb_assoc::detail::typelist_append< \
 770                         pb_assoc::detail::typelist< \
 771                                 PB_ASSOC_TYPELIST_CHAIN4( Hash_Fn, Eq_Fn, Resize_Policy, pb_assoc::detail::int_to_type<Store_Hash>) >, \
 772                                 Policy_TL>::type, \
 773                 Allocator>
 774
 775   template<typename Key,
 776            typename Data,
 777            class Hash_Fn,
 778            class Eq_Fn,
 779            class Resize_Policy,
 780            bool Store_Hash,
 781            class DS_Tag,
 782            class Policy_TL,
 783            class Allocator>
 784   class basic_hash_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
 785   {
 786   public:
 787     typedef Hash_Fn hash_fn;
 788
 789     typedef Eq_Fn eq_fn;
 790
 791     typedef Resize_Policy resize_policy;
 792
 793     enum
 794       {
 795         store_hash = Store_Hash
 796       };
 797
 798     virtual
 799     ~basic_hash_assoc_cntnr();
 800
 801     hash_fn&
 802     get_hash_fn();
 803
 804     const hash_fn&
 805     get_hash_fn() const;
 806
 807     eq_fn&
 808     get_eq_fn();
 809
 810     const eq_fn&
 811     get_eq_fn() const;
 812
 813     Resize_Policy&
 814     get_resize_policy();
 815
 816     const resize_policy&
 817     get_resize_policy() const;
 818
 819   protected:
 820
 821     typedef typename Allocator::size_type size_type;
 822
 823     virtual void
 824     do_resize(size_type new_size);
 825
 826 #define PB_ASSOC_CLASS_NAME basic_hash_assoc_cntnr
 827
 828 #define PB_ASSOC_DIRECT_BASE_C_DEC PB_ASSOC_BASE_C_DEC
 829
 830 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
 831         PB_ASSOC_DIRECT_BASE_C_DEC
 832
 833 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
 834
 835 #undef PB_ASSOC_DIRECT_BASE_C_DEC
 836
 837 #undef PB_ASSOC_CLASS_NAME
 838
 839 #undef PB_ASSOC_DIRECT_BASE_C_DEC
 840
 841   private:
 842     typedef PB_ASSOC_BASE_C_DEC my_base;
 843
 844     basic_hash_assoc_cntnr&
 845     operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
 846   };
 847
 848 #include <ext/pb_assoc/detail/basic_hash_assoc_cntnr/constructors_destructor_fn_imps.hpp>
 849 #include <ext/pb_assoc/detail/basic_hash_assoc_cntnr/resize_fn_imps.hpp>
 850
 851 #undef PB_ASSOC_CLASS_T_DEC
 852
 853 #undef PB_ASSOC_CLASS_C_DEC
 854
 855 #undef PB_ASSOC_BASE_C_DEC
 856
 857 #define PB_ASSOC_CLASS_T_DEC \
 858         template< \
 859                 typename Key, \
 860                 typename Data, \
 861                 class Hash_Fn, \
 862                 class Eq_Fn, \
 863                 class Comb_Hash_Fn, \
 864                 class Resize_Policy, \
 865                 bool Store_Hash, \
 866                 class Allocator>
 867
 868 #define PB_ASSOC_CLASS_C_DEC \
 869         cc_hash_assoc_cntnr< \
 870                 Key, \
 871                 Data, \
 872                 Hash_Fn, \
 873                 Eq_Fn, \
 874                 Comb_Hash_Fn, \
 875                 Resize_Policy, \
 876                 Store_Hash, \
 877                 Allocator>
 878
 879 #define PB_ASSOC_BASE_C_DEC \
 880         basic_hash_assoc_cntnr< \
 881                 Key, \
 882                 Data, \
 883                 Hash_Fn, \
 884                 Eq_Fn, \
 885                 Resize_Policy, \
 886                 Store_Hash, \
 887                 cc_hash_ds_tag, \
 888                 pb_assoc::detail::typelist< \
 889                         PB_ASSOC_TYPELIST_CHAIN1( \
 890                                 Comb_Hash_Fn) >, \
 891                 Allocator>
 892
 893   template<typename Key,
 894            typename Data,
 895            class Hash_Fn = typename pb_assoc::detail::def_hash_fn<Key>::type,
 896            class Eq_Fn = typename pb_assoc::detail::def_eq_fn<Key>::type,
 897            class Comb_Hash_Fn = pb_assoc::detail::def_comb_hash_fn::type,
 898            class Resize_Policy =
 899            typename pb_assoc::detail::def_resize_policy<Comb_Hash_Fn>::type,
 900            bool Store_Hash = pb_assoc::detail::def_store_hash,
 901            class Allocator = std::allocator<char> >
 902   class cc_hash_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
 903   {
 904   public:
 905     typedef Comb_Hash_Fn comb_hash_fn;
 906
 907     cc_hash_assoc_cntnr();
 908
 909     cc_hash_assoc_cntnr(const Hash_Fn& r_hash_fn);
 910
 911     cc_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
 912
 913     cc_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
 914                         const Comb_Hash_Fn& r_comb_hash_fn);
 915
 916     cc_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
 917                         const Comb_Hash_Fn& r_comb_hash_fn,
 918                         const Resize_Policy& r_resize_policy);
 919
 920     template<class It>
 921     cc_hash_assoc_cntnr(It first_it, It last_it);
 922
 923     template<class It>
 924     cc_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn);
 925
 926     template<class It>
 927     cc_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn,
 928                         const Eq_Fn& r_eq_fn);
 929
 930     template<class It>
 931     cc_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn);
 932
 933     template<class It>
 934     cc_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn, const Resize_Policy& r_resize_policy);
 935
 936     cc_hash_assoc_cntnr(const PB_ASSOC_CLASS_C_DEC& r_other);
 937
 938     virtual
 939     ~cc_hash_assoc_cntnr();
 940
 941     PB_ASSOC_CLASS_C_DEC&
 942     operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
 943
 944     void
 945     swap(PB_ASSOC_CLASS_C_DEC& r_other);
 946
 947     comb_hash_fn&
 948     get_comb_hash_fn();
 949
 950     const comb_hash_fn&
 951     get_comb_hash_fn() const;
 952
 953   private:
 954     typedef PB_ASSOC_BASE_C_DEC my_base;
 955   };
 956
 957 #include <ext/pb_assoc/detail/cc_hash_assoc_cntnr/constructor_destructor_fn_imps.hpp>
 958
 959 #undef PB_ASSOC_CLASS_T_DEC
 960
 961 #undef PB_ASSOC_CLASS_C_DEC
 962
 963 #undef PB_ASSOC_BASE_C_DEC
 964
 965 #define PB_ASSOC_CLASS_T_DEC \
 966         template< \
 967                 typename Key, \
 968                 typename Data, \
 969                 class Hash_Fn, \
 970                 class Eq_Fn, \
 971                 class Comb_Probe_Fn, \
 972                 class Probe_Fn, \
 973                 class Resize_Policy, \
 974                 bool Store_Hash, \
 975                 class Allocator>
 976
 977 #define PB_ASSOC_CLASS_C_DEC \
 978         gp_hash_assoc_cntnr< \
 979                 Key, \
 980                 Data, \
 981                 Hash_Fn, \
 982                 Eq_Fn, \
 983                 Comb_Probe_Fn, \
 984                 Probe_Fn, \
 985                 Resize_Policy, \
 986                 Store_Hash, \
 987                 Allocator>
 988
 989 #define PB_ASSOC_BASE_C_DEC \
 990         basic_hash_assoc_cntnr< \
 991                 Key, \
 992                 Data, \
 993                 Hash_Fn, \
 994                 Eq_Fn, \
 995                 Resize_Policy, \
 996                 Store_Hash, \
 997                 gp_hash_ds_tag, \
 998                 pb_assoc::detail::typelist< \
 999                         PB_ASSOC_TYPELIST_CHAIN2( Comb_Probe_Fn, Probe_Fn) >, \
1000                 Allocator>
1001
1002   template<typename Key,
1003            typename Data,
1004            class Hash_Fn = typename pb_assoc::detail::def_hash_fn<Key>::type,
1005            class Eq_Fn = typename pb_assoc::detail::def_eq_fn<Key>::type,
1006            class Comb_Probe_Fn = pb_assoc::detail::def_comb_hash_fn::type,
1007            class Probe_Fn = typename detail::def_probe_fn<Comb_Probe_Fn>::type,
1008            class Resize_Policy =
1009            typename pb_assoc::detail::def_resize_policy<Comb_Probe_Fn>::type,
1010
1011            bool Store_Hash = pb_assoc::detail::def_store_hash,
1012            class Allocator = std::allocator<char> >
1013   class gp_hash_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
1014   {
1015   public:
1016     typedef Comb_Probe_Fn comb_probe_fn;
1017     typedef Probe_Fn probe_fn;
1018
1019     gp_hash_assoc_cntnr();
1020
1021     gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn);
1022
1023     gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
1024
1025     gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
1026                         const Comb_Probe_Fn& r_comb_probe_fn);
1027
1028     gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
1029                         const Comb_Probe_Fn& r_comb_probe_fn,
1030                         const Probe_Fn& r_probe_fn);
1031
1032     gp_hash_assoc_cntnr(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn,
1033                         const Comb_Probe_Fn& r_comb_probe_fn,
1034                         const Probe_Fn& r_probe_fn,
1035                         const Resize_Policy& r_resize_policy);
1036
1037     template<class It>
1038     gp_hash_assoc_cntnr(It first_it, It last_it);
1039
1040     template<class It>
1041     gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn);
1042
1043     template<class It>
1044     gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn);
1045
1046     template<class It>
1047     gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn);
1048
1049     template<class It>
1050     gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn);
1051
1052     template<class It>
1053     gp_hash_assoc_cntnr(It first_it, It last_it, const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Probe_Fn& r_comb_probe_fn, const Probe_Fn& r_probe_fn, const Resize_Policy& r_resize_policy);
1054
1055     gp_hash_assoc_cntnr(const PB_ASSOC_CLASS_C_DEC& r_other);
1056
1057     virtual
1058     ~gp_hash_assoc_cntnr();
1059
1060     PB_ASSOC_CLASS_C_DEC&
1061     operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
1062
1063     void
1064     swap(PB_ASSOC_CLASS_C_DEC& r_other);
1065
1066     comb_probe_fn&
1067     get_comb_probe_fn();
1068
1069     const comb_probe_fn&
1070     get_comb_probe_fn() const;
1071
1072     probe_fn&
1073     get_probe_fn();
1074
1075     const probe_fn&
1076     get_probe_fn() const;
1077
1078   private:
1079     typedef PB_ASSOC_BASE_C_DEC my_base;
1080   };
1081
1082 #include <ext/pb_assoc/detail/gp_hash_assoc_cntnr/constructor_destructor_fn_imps.hpp>
1083
1084 #undef PB_ASSOC_CLASS_T_DEC
1085
1086 #undef  PB_ASSOC_CLASS_C_DEC
1087
1088 #undef  PB_ASSOC_BASE_C_DEC
1089
1090 #define PB_ASSOC_CLASS_T_DEC \
1091         template< \
1092                 typename Key, \
1093                 typename Data, \
1094                 class Cmp_Fn, \
1095                 class DS_Tag, \
1096                 class Node_Updator, \
1097                 class Allocator>
1098
1099 #define PB_ASSOC_CLASS_C_DEC \
1100         basic_tree_assoc_cntnr< \
1101                 Key, \
1102                 Data, \
1103                 Cmp_Fn, \
1104                 DS_Tag, \
1105                 Node_Updator, \
1106                 Allocator>
1107
1108 #define PB_ASSOC_BASE_C_DEC \
1109         basic_assoc_cntnr< \
1110                 Key, \
1111                 Data, \
1112                 DS_Tag, \
1113                 pb_assoc::detail::typelist< \
1114                         PB_ASSOC_TYPELIST_CHAIN2( Cmp_Fn, Node_Updator) >, \
1115                 Allocator>
1116
1117   template<typename Key,
1118            typename Data,
1119            class Cmp_Fn,
1120            class DS_Tag,
1121            class Node_Updator,
1122            class Allocator>
1123   class basic_tree_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
1124   {
1125   public:
1126     typedef typename Allocator::size_type size_type;
1127
1128     typedef
1129     typename Allocator::template rebind<
1130       Key>::other::const_reference
1131     const_key_reference;
1132
1133     typedef Cmp_Fn cmp_fn;
1134
1135     typedef Node_Updator node_updator;
1136
1137     typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
1138
1139     typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
1140
1141     typedef
1142     typename PB_ASSOC_BASE_C_DEC::const_reverse_iterator
1143     const_reverse_iterator;
1144
1145     typedef
1146     typename PB_ASSOC_BASE_C_DEC::reverse_iterator
1147     reverse_iterator;
1148
1149     typedef
1150     typename PB_ASSOC_BASE_C_DEC::const_node_iterator
1151     const_node_iterator;
1152
1153     typedef typename PB_ASSOC_BASE_C_DEC::node_iterator node_iterator;
1154
1155     virtual
1156     ~basic_tree_assoc_cntnr();
1157
1158     cmp_fn&
1159     get_cmp_fn();
1160
1161     const cmp_fn&
1162     get_cmp_fn() const;
1163
1164     node_updator&
1165     get_node_updator();
1166
1167     const node_updator&
1168     get_node_updator() const;
1169
1170     inline size_type
1171     erase(const_key_reference r_key);
1172
1173     inline iterator
1174     erase(iterator it);
1175
1176     inline reverse_iterator
1177     erase(reverse_iterator it)
1178     {
1179       return (my_base::erase(it));
1180     }
1181
1182     inline reverse_iterator
1183     rbegin()
1184     {
1185       return (my_base::rbegin());
1186     }
1187
1188     inline const_reverse_iterator
1189     rbegin() const
1190     {
1191       return (my_base::rbegin());
1192     }
1193
1194     inline reverse_iterator
1195     rend()
1196     {
1197       return (my_base::rend());
1198     }
1199
1200     inline const_reverse_iterator
1201     rend() const
1202     {
1203       return (my_base::rend());
1204     }
1205
1206     inline node_iterator
1207     node_begin()
1208     {
1209       return (my_base::node_begin());
1210     }
1211
1212     inline const_node_iterator
1213     node_begin() const
1214     {
1215       return (my_base::node_begin());
1216     }
1217
1218     inline node_iterator
1219     node_end()
1220     {
1221       return (my_base::node_end());
1222     }
1223
1224     inline const_node_iterator
1225     node_end() const
1226     {
1227       return (my_base::node_end());
1228     }
1229
1230     void
1231     join(PB_ASSOC_CLASS_C_DEC& r_other);
1232
1233     inline void
1234     split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
1235
1236   protected:
1237
1238 #define PB_ASSOC_CLASS_NAME basic_tree_assoc_cntnr
1239
1240 #define PB_ASSOC_DIRECT_BASE_C_DEC PB_ASSOC_BASE_C_DEC
1241
1242 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
1243         PB_ASSOC_DIRECT_BASE_C_DEC
1244
1245 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
1246
1247 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
1248
1249 #undef PB_ASSOC_CLASS_NAME
1250
1251 #undef PB_ASSOC_DIRECT_BASE_C_DEC
1252
1253   private:
1254     typedef PB_ASSOC_BASE_C_DEC my_base;
1255   };
1256
1257 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/constructors_destructor_fn_imps.hpp>
1258 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/policy_access_fn_imps.hpp>
1259 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/range_iteration_fn_imps.hpp>
1260 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/r_range_iteration_fn_imps.hpp>
1261 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/node_iteration_fn_imps.hpp>
1262 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/split_join_fn_imps.hpp>
1263 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/erase_fn_imps.hpp>
1264 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/r_erase_fn_imps.hpp>
1265
1266 #undef PB_ASSOC_CLASS_T_DEC
1267
1268 #undef PB_ASSOC_CLASS_C_DEC
1269
1270 #undef PB_ASSOC_BASE_C_DEC
1271
1272 #define PB_ASSOC_CLASS_T_DEC \
1273         template< \
1274                 typename Key, \
1275                 typename Data, \
1276                 class Cmp_Fn, \
1277                 class Node_Updator, \
1278                 class Allocator>
1279
1280 #define PB_ASSOC_CLASS_C_DEC \
1281         basic_tree_assoc_cntnr< \
1282                 Key, \
1283                 Data, \
1284                 Cmp_Fn, \
1285                 ov_tree_ds_tag, \
1286                 Node_Updator, \
1287                 Allocator>
1288
1289 #define PB_ASSOC_BASE_C_DEC \
1290         basic_assoc_cntnr< \
1291                 Key, \
1292                 Data, \
1293                 ov_tree_ds_tag, \
1294                 pb_assoc::detail::typelist< \
1295                         PB_ASSOC_TYPELIST_CHAIN2( Cmp_Fn, Node_Updator) >, \
1296                 Allocator>
1297
1298   template<typename Key,
1299            typename Data,
1300            typename Cmp_Fn,
1301            typename Node_Updator,
1302            typename Allocator>
1303   class basic_tree_assoc_cntnr<Key, Data, Cmp_Fn, ov_tree_ds_tag, Node_Updator, Allocator>
1304   : public PB_ASSOC_BASE_C_DEC
1305   {
1306   public:
1307     typedef typename Allocator::size_type size_type;
1308
1309     typedef
1310     typename Allocator::template rebind<
1311       Key>::other::const_reference
1312     const_key_reference;
1313
1314     typedef Cmp_Fn cmp_fn;
1315
1316     typedef Node_Updator node_updator;
1317
1318     typedef typename PB_ASSOC_BASE_C_DEC::const_iterator const_iterator;
1319
1320     typedef typename PB_ASSOC_BASE_C_DEC::iterator iterator;
1321
1322     typedef
1323     typename PB_ASSOC_BASE_C_DEC::const_node_iterator
1324     const_node_iterator;
1325
1326     typedef typename PB_ASSOC_BASE_C_DEC::node_iterator node_iterator;
1327
1328     virtual
1329     ~basic_tree_assoc_cntnr();
1330
1331     cmp_fn&
1332     get_cmp_fn();
1333
1334     const cmp_fn&
1335     get_cmp_fn() const;
1336
1337     node_updator&
1338     get_node_updator();
1339
1340     const node_updator&
1341     get_node_updator() const;
1342
1343     inline size_type
1344     erase(const_key_reference r_key);
1345
1346     inline iterator
1347     erase(iterator it);
1348
1349     inline node_iterator
1350     node_begin()
1351     {
1352       return (my_base::node_begin());
1353     }
1354
1355     inline const_node_iterator
1356     node_begin() const
1357     {
1358       return (my_base::node_begin());
1359     }
1360
1361     inline node_iterator
1362     node_end()
1363     {
1364       return (my_base::node_end());
1365     }
1366
1367     inline const_node_iterator
1368     node_end() const
1369     {
1370       return (my_base::node_end());
1371     }
1372
1373     void
1374     join(PB_ASSOC_CLASS_C_DEC& r_other);
1375
1376     inline void
1377     split(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other);
1378
1379   protected:
1380
1381 #define PB_ASSOC_CLASS_NAME basic_tree_assoc_cntnr
1382
1383 #define PB_ASSOC_DIRECT_BASE_C_DEC PB_ASSOC_BASE_C_DEC
1384
1385 #define PB_ASSOC_DIRECT_BASE_CAST_C_DEC \
1386         PB_ASSOC_DIRECT_BASE_C_DEC
1387
1388 #include <ext/pb_assoc/detail/constructors_destructor_fn_imps.hpp>
1389
1390 #undef PB_ASSOC_DIRECT_BASE_CAST_C_DEC
1391
1392 #undef PB_ASSOC_CLASS_NAME
1393
1394 #undef PB_ASSOC_DIRECT_BASE_C_DEC
1395
1396   private:
1397     typedef PB_ASSOC_BASE_C_DEC my_base;
1398   };
1399
1400 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/constructors_destructor_fn_imps.hpp>
1401 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/policy_access_fn_imps.hpp>
1402 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/range_iteration_fn_imps.hpp>
1403 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/node_iteration_fn_imps.hpp>
1404 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/split_join_fn_imps.hpp>
1405 #include <ext/pb_assoc/detail/basic_tree_assoc_cntnr/erase_fn_imps.hpp>
1406
1407 #undef PB_ASSOC_CLASS_T_DEC
1408
1409 #undef PB_ASSOC_CLASS_C_DEC
1410
1411 #undef PB_ASSOC_BASE_C_DEC
1412
1413 #define PB_ASSOC_CLASS_T_DEC \
1414         template< \
1415                 typename Key, \
1416                 typename Data, \
1417                 class Cmp_Fn, \
1418                 class DS_Tag, \
1419                 class Node_Updator, \
1420                 class Allocator>
1421
1422 #define PB_ASSOC_CLASS_C_DEC \
1423         tree_assoc_cntnr< \
1424                 Key, \
1425                 Data, \
1426                 Cmp_Fn, \
1427                 DS_Tag, \
1428                 Node_Updator, \
1429                 Allocator>
1430
1431 #define PB_ASSOC_BASE_C_DEC \
1432         basic_tree_assoc_cntnr< \
1433                 Key, \
1434                 Data, \
1435                 Cmp_Fn, \
1436                 DS_Tag, \
1437                 Node_Updator, \
1438                 Allocator>
1439
1440   template<typename Key, typename Data, class Cmp_Fn =  std::less<Key>,
1441            typename DS_Tag = rb_tree_ds_tag,
1442            typename Node_Updator = pb_assoc::detail::def_node_updator,
1443            typename Allocator = std::allocator<char> >
1444   class tree_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
1445   {
1446     typedef Cmp_Fn cmp_fn;
1447     typedef Node_Updator node_updator;
1448
1449   public:
1450     tree_assoc_cntnr();
1451     tree_assoc_cntnr(const cmp_fn& r_cmp_fn);
1452     tree_assoc_cntnr(const cmp_fn& r_cmp_fn, const Node_Updator&r);
1453
1454     template<typename It>
1455       tree_assoc_cntnr(It first_it, It last_it);
1456
1457     template<typename It>
1458       tree_assoc_cntnr(It first_it, It last_it, const cmp_fn& r_cmp_fn);
1459
1460     template<typename It>
1461       tree_assoc_cntnr(It, It, const cmp_fn&, const Node_Updator&);
1462
1463     tree_assoc_cntnr(const PB_ASSOC_CLASS_C_DEC& r_other);
1464
1465     virtual
1466     ~tree_assoc_cntnr();
1467
1468     PB_ASSOC_CLASS_C_DEC&
1469     operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
1470
1471     void
1472     swap(PB_ASSOC_CLASS_C_DEC& r_other);
1473
1474   private:
1475     typedef PB_ASSOC_BASE_C_DEC my_base;
1476   };
1477
1478 #include <ext/pb_assoc/detail/tree_assoc_cntnr/constructor_destructor_fn_imps.hpp>
1479
1480 #undef PB_ASSOC_CLASS_T_DEC
1481
1482 #undef PB_ASSOC_CLASS_C_DEC
1483
1484 #undef PB_ASSOC_BASE_C_DEC
1485
1486 #define PB_ASSOC_CLASS_T_DEC \
1487         template< \
1488                 typename Key, \
1489                 typename Data, \
1490                 class Eq_Fn, \
1491                 class Update_Policy, \
1492                 class Allocator>
1493
1494 #define PB_ASSOC_CLASS_C_DEC \
1495         lu_assoc_cntnr< \
1496                 Key, \
1497                 Data, \
1498                 Eq_Fn, \
1499                 Update_Policy, \
1500                 Allocator>
1501
1502 #define PB_ASSOC_BASE_C_DEC \
1503         basic_assoc_cntnr< \
1504                 Key, \
1505                 Data, \
1506                 lu_ds_tag, \
1507                 pb_assoc::detail::typelist< \
1508                         PB_ASSOC_TYPELIST_CHAIN2( Eq_Fn, Update_Policy) >, \
1509                 Allocator>
1510
1511   template<typename Key,
1512            typename Data,
1513            typename Eq_Fn = typename pb_assoc::detail::def_eq_fn<Key>::type,
1514            typename Update_Policy = pb_assoc::detail::def_update_policy::type,
1515            typename Allocator = std::allocator<char> >
1516   class lu_assoc_cntnr : public PB_ASSOC_BASE_C_DEC
1517   {
1518   public:
1519     typedef Eq_Fn eq_fn;
1520     typedef Allocator allocator;
1521     typedef Update_Policy update_policy;
1522
1523     lu_assoc_cntnr();
1524     lu_assoc_cntnr(const Eq_Fn& r_eq_fn);
1525     lu_assoc_cntnr(const Eq_Fn& r_eq_fn, const Update_Policy& r_update_policy);
1526
1527     template<typename It>
1528       lu_assoc_cntnr(It first_it, It last_it);
1529
1530     template<typename It>
1531       lu_assoc_cntnr(It first_it, It last_it, const Eq_Fn& r_eq_fn);
1532
1533     template<typename It>
1534       lu_assoc_cntnr(It, It, const Eq_Fn&, const Update_Policy&);
1535
1536     lu_assoc_cntnr(const PB_ASSOC_CLASS_C_DEC& r_other);
1537
1538     virtual
1539     ~lu_assoc_cntnr();
1540
1541     PB_ASSOC_CLASS_C_DEC&
1542     operator=(const PB_ASSOC_CLASS_C_DEC& r_other);
1543
1544     void
1545     swap(PB_ASSOC_CLASS_C_DEC& r_other);
1546
1547     eq_fn&
1548     get_eq_fn();
1549
1550     const eq_fn&
1551     get_eq_fn() const;
1552
1553     update_policy&
1554     get_update_policy();
1555
1556     const update_policy&
1557     get_update_policy() const;
1558
1559   private:
1560     typedef PB_ASSOC_BASE_C_DEC my_base;
1561   };
1562
1563 #include <ext/pb_assoc/detail/lu_assoc_cntnr/constructor_destructor_fn_imps.hpp>
1564 #include <ext/pb_assoc/detail/lu_assoc_cntnr/policy_access_fn_imps.hpp>
1565
1566 #undef PB_ASSOC_CLASS_T_DEC
1567
1568 #undef PB_ASSOC_CLASS_C_DEC
1569
1570 #undef PB_ASSOC_BASE_C_DEC
1571
1572 #undef PB_ASSOC_TYPELIST_CHAIN1
1573 #undef PB_ASSOC_TYPELIST_CHAIN2
1574 #undef PB_ASSOC_TYPELIST_CHAIN3
1575 #undef PB_ASSOC_TYPELIST_CHAIN4
1576 #undef PB_ASSOC_TYPELIST_CHAIN5
1577 #undef PB_ASSOC_TYPELIST_CHAIN6
1578 #undef PB_ASSOC_TYPELIST_CHAIN7
1579 #undef PB_ASSOC_TYPELIST_CHAIN8
1580 #undef PB_ASSOC_TYPELIST_CHAIN9
1581 #undef PB_ASSOC_TYPELIST_CHAIN10
1582 #undef PB_ASSOC_TYPELIST_CHAIN11
1583 #undef PB_ASSOC_TYPELIST_CHAIN12
1584 #undef PB_ASSOC_TYPELIST_CHAIN13
1585 #undef PB_ASSOC_TYPELIST_CHAIN14
1586 #undef PB_ASSOC_TYPELIST_CHAIN15
1587
1588 } // namespace pb_assoc
1589
1590 #endif // #ifndef ASSOC_CNTNR_HPP