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