priority_queue_container_traits.cc revision 1.1.1.1
1// -*- C++ -*- 2 3// Copyright (C) 2005, 2006, 2009 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 terms 7// of the GNU General Public License as published by the Free Software 8// Foundation; either version 3, or (at your option) any later 9// version. 10 11// This library is distributed in the hope that it will be useful, but 12// WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14// General Public License for more details. 15 16// You should have received a copy of the GNU General Public License 17// along with this library; see the file COPYING3. If not see 18// <http://www.gnu.org/licenses/>. 19 20 21// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 22 23// Permission to use, copy, modify, sell, and distribute this software 24// is hereby granted without fee, provided that the above copyright 25// notice appears in all copies, and that both that copyright notice 26// and this permission notice appear in supporting documentation. None 27// of the above authors, nor IBM Haifa Research Laboratories, make any 28// representation about the suitability of this software for any 29// purpose. It is provided "as is" without express or implied 30// warranty. 31 32/** 33 * @file priority_queue_container_traits_example.cpp 34 * A basic example showing how to use container_traits for querying container types 35 * for their behavior. 36 */ 37 38/** 39 * The following example shows how to use container_traits in order to print 40 * out information on an priority queue's behavior, e.g., its underlying 41 * data structure. 42 */ 43 44#include <iostream> 45#include <ext/pb_ds/priority_queue.hpp> 46#include <ext/pb_ds/tag_and_trait.hpp> 47 48using namespace std; 49using namespace __gnu_pbds; 50 51template<class DS_Category> 52void 53print_container_category(DS_Category); 54 55template<> 56void 57print_container_category(binary_heap_tag) 58{ cout << "Binary heap:" << endl; } 59 60template<> 61void 62print_container_category(binomial_heap_tag) 63{ cout << "Binomial heap:" << endl; } 64 65template<> 66void 67print_container_category(rc_binomial_heap_tag) 68{ cout << "Redundant-counter binomial heap:" << endl; } 69 70template<> 71void 72print_container_category(pairing_heap_tag) 73{ cout << "Pairing heap:" << endl; } 74 75template<> 76void 77print_container_category(thin_heap_tag) 78{ cout << "Thin heap:" << endl; } 79 80template<class Invalidation_Guarantee> 81void 82print_invalidation_guarantee(Invalidation_Guarantee); 83 84template<> 85void 86print_invalidation_guarantee(basic_invalidation_guarantee) 87{ 88 cout << "Guarantees only that found references, pointers, and " 89 "iterators are valid as long as the container object is not " 90 "modified" << endl; 91} 92 93template<> 94void 95print_invalidation_guarantee(point_invalidation_guarantee) 96{ 97 cout << "Guarantees that found references, pointers, and " 98 "point_iterators are valid even if the container object " 99 "is modified" << endl; 100} 101 102template<> 103void 104print_invalidation_guarantee(range_invalidation_guarantee) 105{ 106 cout << "Guarantees that iterators remain valid even if the " 107 "container object is modified" << endl; 108} 109 110void 111print_split_join_can_throw(bool can) 112{ 113 if (can) 114 { 115 cout << "Can throw exceptions if split or joined" << endl; 116 return; 117 } 118 cout << "Cannot throw exceptions if split or joined" << endl; 119} 120 121template<class DS_Traits> 122void 123print_container_attributes() 124{ 125 // First print out the data structure category. 126 print_container_category(typename DS_Traits::container_category()); 127 128 // Now print the attributes of the container. 129 print_invalidation_guarantee(typename DS_Traits::invalidation_guarantee()); 130 print_split_join_can_throw(DS_Traits::split_join_can_throw); 131 cout << endl << endl; 132} 133 134int main() 135{ 136 { 137 // Print the attributes of a binary heap. 138 typedef 139 __gnu_pbds::priority_queue< 140 int, 141 std::less<int>, 142 binary_heap_tag> 143 t; 144 145 print_container_attributes<container_traits<t> >(); 146 } 147 148 { 149 // Print the attributes of a binomial heap. 150 typedef 151 __gnu_pbds::priority_queue< 152 int, 153 std::less<int>, 154 binomial_heap_tag> 155 t; 156 157 print_container_attributes<container_traits<t> >(); 158 } 159 160 { 161 // Print the attributes of a redundant-counter binomial heap. 162 typedef 163 __gnu_pbds::priority_queue< 164 int, 165 std::less<int>, 166 rc_binomial_heap_tag> 167 t; 168 169 print_container_attributes<container_traits<t> >(); 170 } 171 172 { 173 // Print the attributes of a pairing heap. 174 typedef 175 __gnu_pbds::priority_queue< 176 int, 177 std::less<int>, 178 pairing_heap_tag> 179 t; 180 181 print_container_attributes<container_traits<t> >(); 182 } 183 184 { 185 /** 186 * Print the attributes of a thin heap. 187 */ 188 189 typedef 190 __gnu_pbds::priority_queue< 191 int, 192 std::less<int>, 193 thin_heap_tag> 194 t; 195 196 print_container_attributes<container_traits<t> >(); 197 } 198 199 return 0; 200} 201