libstdc++
tag_and_trait.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2008, 2009, 2010, 2011
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the terms
00008 // of the GNU General Public License as published by the Free Software
00009 // Foundation; either version 3, or (at your option) any later
00010 // version.
00011 
00012 // This library is distributed in the hope that it will be useful, but
00013 // WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 // General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00027 
00028 // Permission to use, copy, modify, sell, and distribute this software
00029 // is hereby granted without fee, provided that the above copyright
00030 // notice appears in all copies, and that both that copyright notice
00031 // and this permission notice appear in supporting documentation. None
00032 // of the above authors, nor IBM Haifa Research Laboratories, make any
00033 // representation about the suitability of this software for any
00034 // purpose. It is provided "as is" without express or implied
00035 // warranty.
00036 
00037 /**
00038  * @file tag_and_trait.hpp
00039  * Contains tags and traits, e.g., ones describing underlying
00040  * data structures.
00041  */
00042 
00043 #ifndef PB_DS_TAG_AND_TRAIT_HPP
00044 #define PB_DS_TAG_AND_TRAIT_HPP
00045 
00046 #include <bits/c++config.h>
00047 #include <ext/pb_ds/detail/type_utils.hpp>
00048 
00049 /**
00050  * @namespace __gnu_pbds
00051  * @brief GNU extensions for policy-based data structures for public use.
00052  */
00053 namespace __gnu_pbds
00054 {
00055   /** @defgroup pbds Policy-Based Data Structures
00056    *  @ingroup extensions
00057    *
00058    *  This is a library of policy-based elementary data structures:
00059    *  associative containers and priority queues. It is designed for
00060    *  high-performance, flexibility, semantic safety, and conformance
00061    *  to the corresponding containers in std (except for some points
00062    *  where it differs by design).
00063    *
00064    *  For details, see:
00065    *  http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html
00066    *
00067    *  @{
00068    */
00069 
00070   /**
00071    *  @defgroup tags Tags
00072    *  @{   
00073    */
00074   /// A trivial iterator tag. Signifies that the iterators has none of
00075   /// std::iterators's movement abilities.
00076   struct trivial_iterator_tag
00077   { };
00078 
00079   /// Prohibit moving trivial iterators.
00080   typedef void trivial_iterator_difference_type;
00081 
00082 
00083   /**
00084    *  @defgroup invalidation_tags  Invalidation Guarantees
00085    *  @ingroup tags
00086    *  @{
00087    */
00088 
00089   /**
00090    *  Signifies a basic invalidation guarantee that any iterator,
00091    *  pointer, or reference to a container object's mapped value type
00092    *  is valid as long as the container is not modified.
00093    */
00094   struct basic_invalidation_guarantee
00095   { };
00096 
00097   /**
00098    *  Signifies an invalidation guarantee that includes all those of
00099    *  its base, and additionally, that any point-type iterator,
00100    *  pointer, or reference to a container object's mapped value type
00101    *  is valid as long as its corresponding entry has not be erased,
00102    *  regardless of modifications to the container object.
00103    */
00104   struct point_invalidation_guarantee : public basic_invalidation_guarantee
00105   { };
00106 
00107   /**
00108    *  Signifies an invalidation guarantee that includes all those of
00109    *  its base, and additionally, that any range-type iterator
00110    *  (including the returns of begin() and end()) is in the correct
00111    *  relative positions to other range-type iterators as long as its
00112    *  corresponding entry has not be erased, regardless of
00113    *  modifications to the container object.
00114    */
00115   struct range_invalidation_guarantee : public point_invalidation_guarantee
00116   { };
00117   //@}
00118 
00119 
00120   /**
00121    *  @defgroup ds_tags Data Structure Type
00122    *  @ingroup tags
00123    *  @{
00124    */
00125   /// Base data structure tag.
00126   struct container_tag
00127   { };
00128 
00129   /// Basic sequence.
00130   struct sequence_tag : public container_tag { };
00131 
00132   /// Basic string container, inclusive of strings, ropes, etc.
00133   struct string_tag : public sequence_tag { };
00134 
00135   /// Basic associative-container.
00136   struct associative_tag : public container_tag { };
00137 
00138   /// Basic hash structure.
00139   struct basic_hash_tag : public associative_tag { };
00140 
00141   /// Collision-chaining hash.
00142   struct cc_hash_tag : public basic_hash_tag { };
00143 
00144   /// General-probing hash.
00145   struct gp_hash_tag : public basic_hash_tag { };
00146 
00147   /// Basic branch structure.
00148   struct basic_branch_tag : public associative_tag { };
00149 
00150   /// Basic tree structure.
00151   struct tree_tag : public basic_branch_tag { };
00152 
00153   /// Red-black tree.
00154   struct rb_tree_tag : public tree_tag { };
00155 
00156   /// Splay tree.
00157   struct splay_tree_tag : public tree_tag { };
00158 
00159   /// Ordered-vector tree.
00160   struct ov_tree_tag : public tree_tag { };
00161 
00162   /// Basic trie structure.
00163   struct trie_tag : public basic_branch_tag { };
00164 
00165   /// PATRICIA trie.
00166   struct pat_trie_tag : public trie_tag { };
00167 
00168   /// List-update.
00169   struct list_update_tag : public associative_tag { };
00170 
00171   /// Basic priority-queue.
00172   struct priority_queue_tag : public container_tag { };
00173 
00174   /// Pairing-heap.
00175   struct pairing_heap_tag : public priority_queue_tag { };
00176 
00177   /// Binomial-heap.
00178   struct binomial_heap_tag : public priority_queue_tag { };
00179 
00180   /// Redundant-counter binomial-heap.
00181   struct rc_binomial_heap_tag : public priority_queue_tag { };
00182 
00183   /// Binary-heap (array-based).
00184   struct binary_heap_tag : public priority_queue_tag { };
00185 
00186   /// Thin heap.
00187   struct thin_heap_tag : public priority_queue_tag { };
00188   //@}
00189   //@}
00190 
00191 
00192   /**
00193    *  @defgroup traits Traits
00194    *  @{
00195    */
00196 
00197   /**
00198    *  @brief Represents no type, or absence of type, for template tricks.
00199    *
00200    *  In a mapped-policy, indicates that an associative container is a set.
00201    *
00202    *  In a list-update policy, indicates that each link does not need
00203    *  metadata.
00204    *
00205    *  In a hash policy, indicates that the combining hash function
00206    *  is actually a ranged hash function.
00207    *
00208    *  In a probe policy, indicates that the combining probe function
00209    *  is actually a ranged probe function.
00210    */
00211   struct null_type { };
00212 
00213   /// A null node updator, indicating that no node updates are required.
00214   template<typename _Tp1, typename _Tp2, typename _Tp3, typename _Tp4>
00215     struct null_node_update : public null_type
00216     { };
00217 
00218 
00219   /// Primary template, container traits base.
00220   template<typename _Tag>
00221     struct container_traits_base;
00222 
00223   /// Specialization, cc hash.
00224   template<>
00225   struct container_traits_base<cc_hash_tag>
00226   {
00227     typedef cc_hash_tag                 container_category;
00228     typedef point_invalidation_guarantee        invalidation_guarantee;
00229 
00230     enum
00231       {
00232     order_preserving = false,
00233     erase_can_throw = false,
00234     split_join_can_throw = false,
00235     reverse_iteration = false
00236       };
00237   };
00238 
00239   /// Specialization, gp hash.
00240   template<>
00241   struct container_traits_base<gp_hash_tag>
00242   {
00243     typedef gp_hash_tag                 container_category;
00244     typedef basic_invalidation_guarantee        invalidation_guarantee;
00245 
00246     enum
00247       {
00248     order_preserving = false,
00249     erase_can_throw = false,
00250     split_join_can_throw = false,
00251     reverse_iteration = false
00252       };
00253   };
00254 
00255   /// Specialization, rb tree.
00256   template<>
00257   struct container_traits_base<rb_tree_tag>
00258   {
00259     typedef rb_tree_tag                 container_category;
00260     typedef range_invalidation_guarantee        invalidation_guarantee;
00261 
00262     enum
00263       {
00264     order_preserving = true,
00265     erase_can_throw = false,
00266     split_join_can_throw = false,
00267     reverse_iteration = true
00268       };
00269   };
00270 
00271   /// Specialization, splay tree.
00272   template<>
00273   struct container_traits_base<splay_tree_tag>
00274   {
00275     typedef splay_tree_tag              container_category;
00276     typedef range_invalidation_guarantee        invalidation_guarantee;
00277 
00278     enum
00279       {
00280     order_preserving = true,
00281     erase_can_throw = false,
00282     split_join_can_throw = false,
00283     reverse_iteration = true
00284       };
00285   };
00286 
00287   /// Specialization, ov tree.
00288   template<>
00289   struct container_traits_base<ov_tree_tag>
00290   {
00291     typedef ov_tree_tag                 container_category;
00292     typedef basic_invalidation_guarantee        invalidation_guarantee;
00293 
00294     enum
00295       {
00296     order_preserving = true,
00297     erase_can_throw = true,
00298     split_join_can_throw = true,
00299     reverse_iteration = false
00300       };
00301   };
00302 
00303   /// Specialization, pat trie.
00304   template<>
00305   struct container_traits_base<pat_trie_tag>
00306   {
00307     typedef pat_trie_tag                container_category;
00308     typedef range_invalidation_guarantee        invalidation_guarantee;
00309 
00310     enum
00311       {
00312     order_preserving = true,
00313     erase_can_throw = false,
00314     split_join_can_throw = true,
00315     reverse_iteration = true
00316       };
00317   };
00318 
00319   /// Specialization, list update.
00320   template<>
00321   struct container_traits_base<list_update_tag>
00322   {
00323     typedef list_update_tag                 container_category;
00324     typedef point_invalidation_guarantee        invalidation_guarantee;
00325 
00326     enum
00327       {
00328     order_preserving = false,
00329     erase_can_throw = false,
00330     split_join_can_throw = false,
00331     reverse_iteration = false
00332       };
00333   };
00334 
00335   /// Specialization, pairing heap.
00336   template<>
00337   struct container_traits_base<pairing_heap_tag>
00338   {
00339     typedef pairing_heap_tag                container_category;
00340     typedef point_invalidation_guarantee        invalidation_guarantee;
00341 
00342     enum
00343       {
00344     order_preserving = false,
00345     erase_can_throw = false,
00346     split_join_can_throw = false,
00347     reverse_iteration = false
00348       };
00349   };
00350 
00351   /// Specialization, thin heap.
00352   template<>
00353   struct container_traits_base<thin_heap_tag>
00354   {
00355     typedef thin_heap_tag               container_category;
00356     typedef point_invalidation_guarantee        invalidation_guarantee;
00357 
00358     enum
00359       {
00360     order_preserving = false,
00361     erase_can_throw = false,
00362     split_join_can_throw = false,
00363     reverse_iteration = false
00364       };
00365   };
00366 
00367   /// Specialization, binomial heap.
00368   template<>
00369   struct container_traits_base<binomial_heap_tag>
00370   {
00371     typedef binomial_heap_tag               container_category;
00372     typedef point_invalidation_guarantee        invalidation_guarantee;
00373 
00374     enum
00375       {
00376     order_preserving = false,
00377     erase_can_throw = false,
00378     split_join_can_throw = false,
00379     reverse_iteration = false
00380       };
00381   };
00382 
00383   /// Specialization, rc binomial heap.
00384   template<>
00385   struct container_traits_base<rc_binomial_heap_tag>
00386   {
00387     typedef rc_binomial_heap_tag            container_category;
00388     typedef point_invalidation_guarantee        invalidation_guarantee;
00389 
00390     enum
00391       {
00392     order_preserving = false,
00393     erase_can_throw = false,
00394     split_join_can_throw = false,
00395     reverse_iteration = false
00396       };
00397   };
00398 
00399   /// Specialization, binary heap.
00400   template<>
00401   struct container_traits_base<binary_heap_tag>
00402   {
00403     typedef binary_heap_tag                 container_category;
00404     typedef basic_invalidation_guarantee        invalidation_guarantee;
00405 
00406     enum
00407       {
00408     order_preserving = false,
00409     erase_can_throw = false,
00410     split_join_can_throw = true,
00411     reverse_iteration = false
00412       };
00413   };
00414 
00415 
00416   /// Container traits.
00417   // See Matt Austern for the name, S. Meyers MEFC++ #2, others.
00418   template<typename Cntnr>
00419   struct container_traits
00420   : public container_traits_base<typename Cntnr::container_category>
00421   {
00422     typedef Cntnr                      container_type;
00423     typedef typename Cntnr::container_category         container_category;
00424     typedef container_traits_base<container_category>  base_type;
00425     typedef typename base_type::invalidation_guarantee invalidation_guarantee;
00426 
00427     enum
00428       {
00429     /// True only if Cntnr objects guarantee storing  keys by order.
00430     order_preserving = base_type::order_preserving,
00431 
00432     /// True only if erasing a key can throw.
00433     erase_can_throw = base_type::erase_can_throw,
00434 
00435     /// True only if split or join operations can throw.
00436     split_join_can_throw = base_type::split_join_can_throw,
00437 
00438     /// True only reverse iterators are supported.
00439     reverse_iteration = base_type::reverse_iteration
00440       };
00441   };
00442   //@}
00443 
00444 
00445   namespace detail
00446   {
00447     /// Dispatch mechanism, primary template for associative types.
00448     template<typename Key, typename Mapped, typename _Alloc, typename Tag,
00449          typename Policy_Tl = null_type>
00450       struct container_base_dispatch;
00451   } // namespace __detail
00452   //@}
00453 } // namespace __gnu_pbds
00454 
00455 #endif