ward declarations @endlink * * They are required by default to cooperate with the global C library's * @c FILE streams, and to be available during program startup and * termination. For more information, see the HOWTO linked to above. */ //@{ extern istream cin; ///< Linked to standard input extern ostream cout; ///< Linked to standard output extern ostream cerr; ///< Linked to standard error (unbuffered) extern ostream clog; ///< Linked to standard error (buffered) #ifdef _GLIBCXX_USE_WCHAR_T extern wistream wcin; ///< Linked to standard input extern wostream wcout; ///< Linked to standard output extern wostream wcerr; ///< Linked to standard error (unbuffered) extern wostream wclog; ///< Linked to standard error (buffered) #endif //@} // For construction of filebuffers for cout, cin, cerr, clog et. al. static ios_base::Init __ioinit; _GLIBCXX_END_NAMESPACE #endif /* _GLIBCXX_IOSTREAM */ // -*- C++ -*- // Copyright (C) 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file include/random * This is a Standard C++ Library header. */ #ifndef _GLIBCXX_RANDOM #define _GLIBCXX_RANDOM 1 #pragma GCC system_header #ifndef __GXX_EXPERIMENTAL_CXX0X__ # include #endif #if defined(_GLIBCXX_INCLUDE_AS_TR1) # error C++0x header cannot be included from TR1 header #endif #include #include #include #include #include #include #include #include #include #include #include #if defined(_GLIBCXX_INCLUDE_AS_CXX0X) # include #else # define _GLIBCXX_INCLUDE_AS_CXX0X # define _GLIBCXX_BEGIN_NAMESPACE_TR1 # define _GLIBCXX_END_NAMESPACE_TR1 # define _GLIBCXX_TR1 # include # undef _GLIBCXX_TR1 # undef _GLIBCXX_END_NAMESPACE_TR1 # undef _GLIBCXX_BEGIN_NAMESPACE_TR1 # undef _GLIBCXX_INCLUDE_AS_CXX0X #endif #endif // _GLIBCXX_RANDOM // -*- C++ -*- forwarding header. // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, // 2006, 2007, 2008 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file include/cstdlib * This is a Standard C++ Library file. You should @c #include this file * in your programs, rather than any of the "*.h" implementation files. * * This is the C++ version of the Standard C Library header @c stdlib.h, * and its contents are (mostly) the same as that header, but are all * contained in the namespace @c std (except for names which are defined * as macros in C). */ // // ISO C++ 14882: 20.4.6 C library // #pragma GCC system_header #include #include #ifndef _GLIBCXX_CSTDLIB #define _GLIBCXX_CSTDLIB 1 #if !_GLIBCXX_HOSTED // The C standard does not require a freestanding implementation to // provide . However, the C++ standard does still require // -- but only the functionality mentioned in // [lib.support.start.term]. #define EXIT_SUCCESS 0 #define EXIT_FAILURE 1 _GLIBCXX_BEGIN_NAMESPACE(std) extern "C" void abort(void); extern "C" int atexit(void (*)()); extern "C" void exit(int); _GLIBCXX_END_NAMESPACE #else #include // Get rid of those macros defined in in lieu of real functions. #undef abort #undef abs #undef atexit #undef atof #undef atoi #undef atol #undef bsearch #undef calloc #undef div #undef exit #undef free #undef getenv #undef labs #undef ldiv #undef malloc #undef mblen #undef mbstowcs #undef mbtowc #undef qsort #undef rand #undef realloc #undef srand #undef strtod #undef strtol #undef strtoul #undef system #undef wcstombs #undef wctomb _GLIBCXX_BEGIN_NAMESPACE(std) using ::div_t; using ::ldiv_t; using ::abort; using ::abs; using ::atexit; using ::atof; using ::atoi; using ::atol; using ::bsearch; using ::calloc; using ::div; using ::exit; using ::free; using ::getenv; using ::labs; using ::ldiv; using ::malloc; #ifdef _GLIBCXX_HAVE_MBSTATE_T using ::mblen; using ::mbstowcs; using ::mbtowc; #endif // _GLIBCXX_HAVE_MBSTATE_T using ::qsort; using ::rand; using ::realloc; using ::srand; using ::strtod; using ::strtol; using ::strtoul; using ::system; #ifdef _GLIBCXX_USE_WCHAR_T using ::wcstombs; using ::wctomb; #endif // _GLIBCXX_USE_WCHAR_T inline long abs(long __i) { return labs(__i); } inline ldiv_t div(long __i, long __j) { return ldiv(__i, __j); } _GLIBCXX_END_NAMESPACE #if _GLIBCXX_USE_C99 #undef _Exit #undef llabs #undef lldiv #undef atoll #undef strtoll #undef strtoull #undef strtof #undef strtold _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) #if !_GLIBCXX_USE_C99_LONG_LONG_DYNAMIC using ::lldiv_t; #endif #if _GLIBCXX_USE_C99_CHECK || _GLIBCXX_USE_C99_DYNAMIC extern "C" void (_Exit)(int); #endif #if !_GLIBCXX_USE_C99_DYNAMIC using ::_Exit; #endif inline long long abs(long long __x) { return __x >= 0 ? __x : -__x; } #if !_GLIBCXX_USE_C99_LONG_LONG_DYNAMIC using ::llabs; inline lldiv_t div(long long __n, long long __d) { lldiv_t __q; __q.quot = __n / __d; __q.rem = __n % __d; return __q; } using ::lldiv; #endif #if _GLIBCXX_USE_C99_LONG_LONG_CHECK || _GLIBCXX_USE_C99_LONG_LONG_DYNAMIC extern "C" long long int (atoll)(const char *); extern "C" long long int (strtoll)(const char * restrict, char ** restrict, int); extern "C" unsigned long long int (strtoull)(const char * restrict, char ** restrict, int); #endif #if !_GLIBCXX_USE_C99_LONG_LONG_DYNAMIC using ::atoll; using ::strtoll; using ::strtoull; #endif using ::strtof; using ::strtold; _GLIBCXX_END_NAMESPACE _GLIBCXX_BEGIN_NAMESPACE(std) #if !_GLIBCXX_USE_C99_LONG_LONG_DYNAMIC using ::__gnu_cxx::lldiv_t; #endif using ::__gnu_cxx::_Exit; using ::__gnu_cxx::abs; #if !_GLIBCXX_USE_C99_LONG_LONG_DYNAMIC using ::__gnu_cxx::llabs; using ::__gnu_cxx::div; using ::__gnu_cxx::lldiv; #endif using ::__gnu_cxx::atoll; using ::__gnu_cxx::strtof; using ::__gnu_cxx::strtoll; using ::__gnu_cxx::strtoull; using ::__gnu_cxx::strtold; _GLIBCXX_END_NAMESPACE #endif // _GLIBCXX_USE_C99 #ifdef __GXX_EXPERIMENTAL_CXX0X__ # if defined(_GLIBCXX_INCLUDE_AS_TR1) # error C++0x header cannot be included from TR1 header # endif # if defined(_GLIBCXX_INCLUDE_AS_CXX0X) # include # else # define _GLIBCXX_INCLUDE_AS_CXX0X # define _GLIBCXX_BEGIN_NAMESPACE_TR1 # define _GLIBCXX_END_NAMESPACE_TR1 # define _GLIBCXX_TR1 # include # undef _GLIBCXX_TR1 # undef _GLIBCXX_END_NAMESPACE_TR1 # undef _GLIBCXX_BEGIN_NAMESPACE_TR1 # undef _GLIBCXX_INCLUDE_AS_CXX0X # endif #endif #endif // !_GLIBCXX_HOSTED #endif // -*- C++ -*- // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007 // Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /* * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. */ /** @file include/stack * This is a Standard C++ Library header. */ #ifndef _GLIBCXX_STACK #define _GLIBCXX_STACK 1 #pragma GCC system_header #include #include #endif /* _GLIBCXX_STACK */ // -*- C++ -*- compatibility header. // Copyright (C) 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 51 Franklin Street, Fifth Floor, // Boston, MA 02110-1301, USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file complex.h * This is a Standard C++ Library header. */ #include #ifdef __GXX_EXPERIMENTAL_CXX0X__ # include #else # if _GLIBCXX_HAVE_COMPLEX_H # include_next # endif #endif #ifndef _GLIBCXX_COMPLEX_H #define _GLIBCXX_COMPLEX_H 1 #endif  . ..complexcctypefunctional_hash.harray  hashtable!utility"cstdio#boost_shared_ptr.h$cfenv% boost_sp_counted_base.h&random'cstdlib( unordered_set)cwchar* unordered_map+regex,cstdint-hashtable_policy.h.cwctype/ random.tcc0 cinttypes1 type_traits2cmath3$ functional// TR1 complex -*- C++ -*- // Copyright (C) 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file tr1_impl/complex * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ namespace std { _GLIBCXX_BEGIN_NAMESPACE_TR1 // Forward declarations. template std::complex<_Tp> acos(const std::complex<_Tp>&); template std::complex<_Tp> asin(const std::complex<_Tp>&); template std::complex<_Tp> atan(const std::complex<_Tp>&); template std::complex<_Tp> acosh(const std::complex<_Tp>&); template std::complex<_Tp> asinh(const std::complex<_Tp>&); template std::complex<_Tp> atanh(const std::complex<_Tp>&); #ifdef _GLIBCXX_INCLUDE_AS_CXX0X // DR 595. template _Tp fabs(const std::complex<_Tp>&); #else template std::complex<_Tp> fabs(const std::complex<_Tp>&); #endif /// acos(__z) [8.1.2]. // Effects: Behaves the same as C99 function cacos, defined // in subclause 7.3.5.1. template inline std::complex<_Tp> __complex_acos(const std::complex<_Tp>& __z) { const std::complex<_Tp> __t = std::_GLIBCXX_TR1 asin(__z); const _Tp __pi_2 = 1.5707963267948966192313216916397514L; return std::complex<_Tp>(__pi_2 - __t.real(), -__t.imag()); } #if _GLIBCXX_USE_C99_COMPLEX_TR1 inline __complex__ float __complex_acos(__complex__ float __z) { return __builtin_cacosf(__z); } inline __complex__ double __complex_acos(__complex__ double __z) { return __builtin_cacos(__z); } inline __complex__ long double __complex_acos(const __complex__ long double& __z) { return __builtin_cacosl(__z); } template inline std::complex<_Tp> acos(const std::complex<_Tp>& __z) { return __complex_acos(__z.__rep()); } #else template inline std::complex<_Tp> acos(const std::complex<_Tp>& __z) { return __complex_acos(__z); } #endif /// asin(__z) [8.1.3]. // Effects: Behaves the same as C99 function casin, defined // in subclause 7.3.5.2. template inline std::complex<_Tp> __complex_asin(const std::complex<_Tp>& __z) { std::complex<_Tp> __t(-__z.imag(), __z.real()); __t = std::_GLIBCXX_TR1 asinh(__t); return std::complex<_Tp>(__t.imag(), -__t.real()); } #if _GLIBCXX_USE_C99_COMPLEX_TR1 inline __complex__ float __complex_asin(__complex__ float __z) { return __builtin_casinf(__z); } inline __complex__ double __complex_asin(__complex__ double __z) { return __builtin_casin(__z); } inline __complex__ long double __complex_asin(const __complex__ long double& __z) { return __builtin_casinl(__z); } template inline std::complex<_Tp> asin(const std::complex<_Tp>& __z) { return __complex_asin(__z.__rep()); } #else template inline std::complex<_Tp> asin(const std::complex<_Tp>& __z) { return __complex_asin(__z); } #endif /// atan(__z) [8.1.4]. // Effects: Behaves the same as C99 function catan, defined // in subclause 7.3.5.3. template std::complex<_Tp> __complex_atan(const std::complex<_Tp>& __z) { const _Tp __r2 = __z.real() * __z.real(); const _Tp __x = _Tp(1.0) - __r2 - __z.imag() * __z.imag(); _Tp __num = __z.imag() + _Tp(1.0); _Tp __den = __z.imag() - _Tp(1.0); __num = __r2 + __num * __num; __den = __r2 + __den * __den; return std::complex<_Tp>(_Tp(0.5) * atan2(_Tp(2.0) * __z.real(), __x), _Tp(0.25) * log(__num / __den)); } #if _GLIBCXX_USE_C99_COMPLEX_TR1 inline __complex__ float __complex_atan(__complex__ float __z) { return __builtin_catanf(__z); } inline __complex__ double __complex_atan(__complex__ double __z) { return __builtin_catan(__z); } inline __complex__ long double __complex_atan(const __complex__ long double& __z) { return __builtin_catanl(__z); } template inline std::complex<_Tp> atan(const std::complex<_Tp>& __z) { return __complex_atan(__z.__rep()); } #else template inline std::complex<_Tp> atan(const std::complex<_Tp>& __z) { return __complex_atan(__z); } #endif /// acosh(__z) [8.1.5]. // Effects: Behaves the same as C99 function cacosh, defined // in subclause 7.3.6.1. template std::complex<_Tp> __complex_acosh(const std::complex<_Tp>& __z) { std::complex<_Tp> __t((__z.real() - __z.imag()) * (__z.real() + __z.imag()) - _Tp(1.0), _Tp(2.0) * __z.real() * __z.imag()); __t = std::sqrt(__t); return std::log(__t + __z); } #if _GLIBCXX_USE_C99_COMPLEX_TR1 inline __complex__ float __complex_acosh(__complex__ float __z) { return __builtin_cacoshf(__z); } inline __complex__ double __complex_acosh(__complex__ double __z) { return __builtin_cacosh(__z); } inline __complex__ long double __complex_acosh(const __complex__ long double& __z) { return __builtin_cacoshl(__z); } template inline std::complex<_Tp> acosh(const std::complex<_Tp>& __z) { return __complex_acosh(__z.__rep()); } #else template inline std::complex<_Tp> acosh(const std::complex<_Tp>& __z) { return __complex_acosh(__z); } #endif /// asinh(__z) [8.1.6]. // Effects: Behaves the same as C99 function casin, defined // in subclause 7.3.6.2. template std::complex<_Tp> __complex_asinh(const std::complex<_Tp>& __z) { std::complex<_Tp> __t((__z.real() - __z.imag()) * (__z.real() + __z.imag()) + _Tp(1.0), _Tp(2.0) * __z.real() * __z.imag()); __t = std::sqrt(__t); return std::log(__t + __z); } #if _GLIBCXX_USE_C99_COMPLEX_TR1 inline __complex__ float __complex_asinh(__complex__ float __z) { return __builtin_casinhf(__z); } inline __complex__ double __complex_asinh(__complex__ double __z) { return __builtin_casinh(__z); } inline __complex__ long double __complex_asinh(const __complex__ long double& __z) { return __builtin_casinhl(__z); } template inline std::complex<_Tp> asinh(const std::complex<_Tp>& __z) { return __complex_asinh(__z.__rep()); } #else template inline std::complex<_Tp> asinh(const std::complex<_Tp>& __z) { return __complex_asinh(__z); } #endif /// atanh(__z) [8.1.7]. // Effects: Behaves the same as C99 function catanh, defined // in subclause 7.3.6.3. template std::complex<_Tp> __complex_atanh(const std::complex<_Tp>& __z) { const _Tp __i2 = __z.imag() * __z.imag(); const _Tp __x = _Tp(1.0) - __i2 - __z.real() * __z.real(); _Tp __num = _Tp(1.0) + __z.real(); _Tp __den = _Tp(1.0) - __z.real(); __num = __i2 + __num * __num; __den = __i2 + __den * __den; return std::complex<_Tp>(_Tp(0.25) * (log(__num) - log(__den)), _Tp(0.5) * atan2(_Tp(2.0) * __z.imag(), __x)); } #if _GLIBCXX_USE_C99_COMPLEX_TR1 inline __complex__ float __complex_atanh(__complex__ float __z) { return __builtin_catanhf(__z); } inline __complex__ double __complex_atanh(__complex__ double __z) { return __builtin_catanh(__z); } inline __complex__ long double __complex_atanh(const __complex__ long double& __z) { return __builtin_catanhl(__z); } template inline std::complex<_Tp> atanh(const std::complex<_Tp>& __z) { return __complex_atanh(__z.__rep()); } #else template inline std::complex<_Tp> atanh(const std::complex<_Tp>& __z) { return __complex_atanh(__z); } #endif /// fabs(__z) [8.1.8]. // Effects: Behaves the same as C99 function cabs, defined // in subclause 7.3.8.1. template #ifdef _GLIBCXX_INCLUDE_AS_CXX0X inline _Tp #else inline std::complex<_Tp> #endif fabs(const std::complex<_Tp>& __z) { return std::abs(__z); } #if (defined(_GLIBCXX_INCLUDE_AS_CXX0X) \ || (defined(_GLIBCXX_INCLUDE_AS_TR1) \ && !defined(__GXX_EXPERIMENTAL_CXX0X__))) /// Additional overloads [8.1.9]. template inline typename __gnu_cxx::__promote<_Tp>::__type arg(_Tp __x) { typedef typename __gnu_cxx::__promote<_Tp>::__type __type; return std::arg(std::complex<__type>(__x)); } template inline std::complex::__type> conj(_Tp __x) { return __x; } template inline typename __gnu_cxx::__promote<_Tp>::__type imag(_Tp) { return _Tp(); } template inline typename __gnu_cxx::__promote<_Tp>::__type norm(_Tp __x) { typedef typename __gnu_cxx::__promote<_Tp>::__type __type; return __type(__x) * __type(__x); } template inline std::complex::__type> polar(const _Tp& __rho, const _Up& __theta) { typedef typename __gnu_cxx::__promote_2<_Tp, _Up>::__type __type; return std::polar(__type(__rho), __type(__theta)); } template inline std::complex::__type> pow(const std::complex<_Tp>& __x, const _Up& __y) { typedef typename __gnu_cxx::__promote_2<_Tp, _Up>::__type __type; return std::pow(std::complex<__type>(__x), __type(__y)); } template inline std::complex::__type> pow(const _Tp& __x, const std::complex<_Up>& __y) { typedef typename __gnu_cxx::__promote_2<_Tp, _Up>::__type __type; return std::pow(__type(__x), std::complex<__type>(__y)); } template inline std::complex::__type> pow(const std::complex<_Tp>& __x, const std::complex<_Up>& __y) { typedef typename __gnu_cxx::__promote_2<_Tp, _Up>::__type __type; return std::pow(std::complex<__type>(__x), std::complex<__type>(__y)); } template inline typename __gnu_cxx::__promote<_Tp>::__type real(_Tp __x) { return __x; } #endif _GLIBCXX_END_NAMESPACE_TR1 } // TR1 cctype -*- C++ -*- // Copyright (C) 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file tr1_impl/cctype * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ #if _GLIBCXX_USE_C99_CTYPE_TR1 #undef isblank namespace std { _GLIBCXX_BEGIN_NAMESPACE_TR1 using ::isblank; _GLIBCXX_END_NAMESPACE_TR1 } #endif // TR1 functional -*- C++ -*- // Copyright (C) 2007, 2008 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file tr1_impl/functional_hash.h * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ namespace std { _GLIBCXX_BEGIN_NAMESPACE_TR1 /// Class template hash. // Declaration of default hash functor std::tr1::hash. The types for // which std::tr1::hash is well-defined is in clause 6.3.3. of the PDTR. template struct hash : public std::unary_function<_Tp, size_t> { size_t operator()(_Tp __val) const; }; /// Partial specializations for pointer types. template struct hash<_Tp*> : public std::unary_function<_Tp*, size_t> { size_t operator()(_Tp* __p) const { return reinterpret_cast(__p); } }; /// Explicit specializations for integer types. #define _TR1_hashtable_define_trivial_hash(_Tp) \ template<> \ inline size_t \ hash<_Tp>::operator()(_Tp __val) const \ { return static_cast(__val); } _TR1_hashtable_define_trivial_hash(bool); _TR1_hashtable_define_trivial_hash(char); _TR1_hashtable_define_trivial_hash(signed char); _TR1_hashtable_define_trivial_hash(unsigned char); _TR1_hashtable_define_trivial_hash(wchar_t); _TR1_hashtable_define_trivial_hash(short); _TR1_hashtable_define_trivial_hash(int); _TR1_hashtable_define_trivial_hash(long); _TR1_hashtable_define_trivial_hash(long long); _TR1_hashtable_define_trivial_hash(unsigned short); _TR1_hashtable_define_trivial_hash(unsigned int); _TR1_hashtable_define_trivial_hash(unsigned long); _TR1_hashtable_define_trivial_hash(unsigned long long); #undef _TR1_hashtable_define_trivial_hash // Fowler / Noll / Vo (FNV) Hash (type FNV-1a) // (Used by the next specializations of std::tr1::hash.) /// Dummy generic implementation (for sizeof(size_t) != 4, 8). template struct _Fnv_hash { static size_t hash(const char* __first, size_t __length) { size_t __result = 0; for (; __length > 0; --__length) __result = (__result * 131) + *__first++; return __result; } }; template<> struct _Fnv_hash<4> { static size_t hash(const char* __first, size_t __length) { size_t __result = static_cast(2166136261UL); for (; __length > 0; --__length) { __result ^= static_cast(*__first++); __result *= static_cast(16777619UL); } return __result; } }; template<> struct _Fnv_hash<8> { static size_t hash(const char* __first, size_t __length) { size_t __result = static_cast(14695981039346656037ULL); for (; __length > 0; --__length) { __result ^= static_cast(*__first++); __result *= static_cast(1099511628211ULL); } return __result; } }; /// Explicit specializations for float. template<> inline size_t hash::operator()(float __val) const { size_t __result = 0; // 0 and -0 both hash to zero. if (__val != 0.0f) __result = _Fnv_hash<>::hash(reinterpret_cast(&__val), sizeof(__val)); return __result; }; /// Explicit specializations for double. template<> inline size_t hash::operator()(double __val) const { size_t __result = 0; // 0 and -0 both hash to zero. if (__val != 0.0) __result = _Fnv_hash<>::hash(reinterpret_cast(&__val), sizeof(__val)); return __result; }; /// Explicit specializations for long double. template<> size_t hash::operator()(long double __val) const; /// Explicit specialization of member operator for non-builtin types. template<> size_t hash::operator()(string) const; template<> size_t hash::operator()(const string&) const; #ifdef _GLIBCXX_USE_WCHAR_T template<> size_t hash::operator()(wstring) const; template<> size_t hash::operator()(const wstring&) const; #endif _GLIBCXX_END_NAMESPACE_TR1 } // class template array -*- C++ -*- // Copyright (C) 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file tr1_impl/array * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ namespace std { _GLIBCXX_BEGIN_NAMESPACE_TR1 /// array. /// NB: Requires complete type _Tp. template struct array { typedef _Tp value_type; typedef value_type& reference; typedef const value_type& const_reference; typedef value_type* iterator; typedef const value_type* const_iterator; typedef std::size_t size_type; typedef std::ptrdiff_t difference_type; typedef std::reverse_iterator reverse_iterator; typedef std::reverse_iterator const_reverse_iterator; // Support for zero-sized arrays mandatory. value_type _M_instance[_Nm ? _Nm : 1]; // No explicit construct/copy/destroy for aggregate type. void assign(const value_type& __u) { std::fill_n(begin(), size(), __u); } void swap(array& __other) { std::swap_ranges(begin(), end(), __other.begin()); } // Iterators. iterator begin() { return iterator(&_M_instance[0]); } const_iterator begin() const { return const_iterator(&_M_instance[0]); } iterator end() { return iterator(&_M_instance[_Nm]); } const_iterator end() const { return const_iterator(&_M_instance[_Nm]); } reverse_iterator rbegin() { return reverse_iterator(end()); } const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); } reverse_iterator rend() { return reverse_iterator(begin()); } const_reverse_iterator rend() const { return const_reverse_iterator(begin()); } #ifdef _GLIBCXX_INCLUDE_AS_CXX0X const_iterator cbegin() const { return const_iterator(&_M_instance[0]); } const_iterator cend() const { return const_iterator(&_M_instance[_Nm]); } const_reverse_iterator crbegin() const { return const_reverse_iterator(end()); } const_reverse_iterator crend() const { return const_reverse_iterator(begin()); } #endif // Capacity. size_type size() const { return _Nm; } size_type max_size() const { return _Nm; } bool empty() const { return size() == 0; } // Element access. reference operator[](size_type __n) { return _M_instance[__n]; } const_reference operator[](size_type __n) const { return _M_instance[__n]; } reference at(size_type __n) { if (__builtin_expect(__n >= _Nm, false)) std::__throw_out_of_range(__N("array::at")); return _M_instance[__n]; } const_reference at(size_type __n) const { if (__builtin_expect(__n >= _Nm, false)) std::__throw_out_of_range(__N("array::at")); return _M_instance[__n]; } reference front() { return *begin(); } const_reference front() const { return *begin(); } reference back() { return _Nm ? *(end() - 1) : *end(); } const_reference back() const { return _Nm ? *(end() - 1) : *end(); } _Tp* data() { return &_M_instance[0]; } const _Tp* data() const { return &_M_instance[0]; } }; // Array comparisons. template inline bool operator==(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two) { return std::equal(__one.begin(), __one.end(), __two.begin()); } template inline bool operator!=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two) { return !(__one == __two); } template inline bool operator<(const array<_Tp, _Nm>& __a, const array<_Tp, _Nm>& __b) { return std::lexicographical_compare(__a.begin(), __a.end(), __b.begin(), __b.end()); } template inline bool operator>(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two) { return __two < __one; } template inline bool operator<=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two) { return !(__one > __two); } template inline bool operator>=(const array<_Tp, _Nm>& __one, const array<_Tp, _Nm>& __two) { return !(__one < __two); } // Specialized algorithms [6.2.2.2]. template inline void swap(array<_Tp, _Nm>& __one, array<_Tp, _Nm>& __two) { std::swap_ranges(__one.begin(), __one.end(), __two.begin()); } // Tuple interface to class template array [6.2.2.5]. /// tuple_size template class tuple_size; /// tuple_element template class tuple_element; template struct tuple_size > { static const int value = _Nm; }; template const int tuple_size >::value; template struct tuple_element<_Int, array<_Tp, _Nm> > { typedef _Tp type; }; template inline _Tp& get(array<_Tp, _Nm>& __arr) { return __arr[_Int]; } template inline const _Tp& get(const array<_Tp, _Nm>& __arr) { return __arr[_Int]; } _GLIBCXX_END_NAMESPACE_TR1 } // Internal header for TR1 unordered_set and unordered_map -*- C++ -*- // Copyright (C) 2007 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the // terms of the GNU General Public License as published by the // Free Software Foundation; either version 2, or (at your option) // any later version. // This library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License along // with this library; see the file COPYING. If not, write to the Free // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, // USA. // As a special exception, you may use this file as part of a free software // library without restriction. Specifically, if other files instantiate // templates or use macros or inline functions from this file, or you compile // this file and link it with other files to produce an executable, this // file does not by itself cause the resulting executable to be covered by // the GNU General Public License. This exception does not however // invalidate any other reasons why the executable file might be covered by // the GNU General Public License. /** @file tr1_impl/hashtable * This is an internal header file, included by other library headers. * You should not attempt to use it directly. */ // This header file defines std::tr1::hashtable, which is used to // implement std::tr1::unordered_set, std::tr1::unordered_map, // std::tr1::unordered_multiset, and std::tr1::unordered_multimap. // hashtable has many template parameters, partly to accommodate // the differences between those four classes and partly to // accommodate policy choices that go beyond TR1 specifications. // Class template hashtable attempts to encapsulate all reasonable // variation among hash tables that use chaining. It does not handle // open addressing. // References: // M. Austern, "A Proposal to Add Hash Tables to the Standard // Library (revision 4)," WG21 Document N1456=03-0039, 2003. // D. E. Knuth, The Art of Computer Programming, v. 3, Sorting and Searching. // A. Tavori and V. Dreizin, "Policy-Based Data Structures", 2004. // http://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/index.html #include namespace std { _GLIBCXX_BEGIN_NAMESPACE_TR1 // Class template _Hashtable, class definition. // Meaning of class template _Hashtable's template parameters // _Key and _Value: arbitrary CopyConstructible types. // _Allocator: an allocator type ([lib.allocator.requirements]) whose // value type is Value. As a conforming extension, we allow for // value type != Value. // _ExtractKey: function object that takes a object of type Value // and returns a value of type _Key. // _Equal: function object that takes two objects of type k and returns // a bool-like value that is true if the two objects are considered equal. // _H1: the hash function. A unary function object with argument type // Key and result type size_t. Return values should be distributed // over the entire range [0, numeric_limits:::max()]. // _H2: the range-hashing function (in the terminology of Tavori and // Dreizin). A binary function object whose argument types and result // type are all size_t. Given arguments r and N, the return value is // in the range [0, N). // _Hash: the ranged hash function (Tavori and Dreizin). A binary function // whose argument types are _Key and size_t and whose result type is // size_t. Given arguments k and N, the return value is in the range // [0, N). Default: hash(k, N) = h2(h1(k), N). If _Hash is anything other // than the default, _H1 and _H2 are ignored. // _RehashPolicy: Policy class with three members, all of which govern // the bucket count. _M_next_bkt(n) returns a bucket count no smaller // than n. _M_bkt_for_elements(n) returns a bucket count appropriate // for an element count of n. _M_need_rehash(n_bkt, n_elt, n_ins) // determines whether, if the current bucket count is n_bkt and the // current element count is n_elt, we need to increase the bucket // count. If so, returns make_pair(true, n), where n is the new // bucket count. If not, returns make_pair(false, ). // ??? Right now it is hard-wired that the number of buckets never // shrinks. Should we allow _RehashPolicy to change that? // __cache_hash_code: bool. true if we store the value of the hash // function along with the value. This is a time-space tradeoff. // Storing it may improve lookup speed by reducing the number of times // we need to call the Equal function. // __constant_iterators: bool. true if iterator and const_iterator are // both constant iterator types. This is true for unordered_set and // unordered_multiset, false for unordered_map and unordered_multimap. // __unique_keys: bool. true if the return value of _Hashtable::count(k) // is always at most one, false if it may be an arbitrary number. This // true for unordered_set and unordered_map, false for unordered_multiset // and unordered_multimap. template class _Hashtable : public __detail::_Rehash_base<_RehashPolicy, _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys> >, public __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, __cache_hash_code>, public __detail::_Map_base<_Key, _Value, _ExtractKey, __unique_keys, _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __cache_hash_code, __constant_iterators, __unique_keys> > { public: typedef _Allocator allocator_type; typedef _Value value_type; typedef _Key key_type; typedef _Equal key_equal; // mapped_type, if present, comes from _Map_base. // hasher, if present, comes from _Hash_code_base. typedef typename _Allocator::difference_type difference_type; typedef typename _Allocator::size_type size_type; typedef typename _Allocator::reference reference; typedef typename _Allocator::const_reference const_reference; typedef __detail::_Node_iterator local_iterator; typedef __detail::_Node_const_iterator const_local_iterator; typedef __detail::_Hashtable_iterator iterator; typedef __detail::_Hashtable_const_iterator const_iterator; template friend struct __detail::_Map_base; private: typedef __detail::_Hash_node<_Value, __cache_hash_code> _Node; typedef typename _Allocator::template rebind<_Node>::other _Node_allocator_type; typedef typename _Allocator::template rebind<_Node*>::other _Bucket_allocator_type; typedef typename _Allocator::template rebind<_Value>::other _Value_allocator_type; _Node_allocator_type _M_node_allocator; _Node** _M_buckets; size_type _M_bucket_count; size_type _M_element_count; _RehashPolicy _M_rehash_policy; _Node* _M_allocate_node(const value_type& __v); void _M_deallocate_node(_Node* __n); void _M_deallocate_nodes(_Node**, size_type); _Node** _M_allocate_buckets(size_type __n); void _M_deallocate_buckets(_Node**, size_type __n); public: // Constructor, destructor, assignment, swap _Hashtable(size_type __bucket_hint, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&); template _Hashtable(_InputIterator __first, _InputIterator __last, size_type __bucket_hint, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&); _Hashtable(const _Hashtable&); #ifdef _GLIBCXX_INCLUDE_AS_CXX0X _Hashtable(_Hashtable&&); #endif _Hashtable& operator=(const _Hashtable&); ~_Hashtable(); #ifdef _GLIBCXX_INCLUDE_AS_CXX0X void swap(_Hashtable&&); #else void swap(_Hashtable&); #endif // Basic container operations iterator begin() { iterator __i(_M_buckets); if (!__i._M_cur_node) __i._M_incr_bucket(); return __i; } const_iterator begin() const { const_iterator __i(_M_buckets); if (!__i._M_cur_node) __i._M_incr_bucket(); return __i; } iterator end() { return iterator(_M_buckets + _M_bucket_count); } const_iterator end() const { return const_iterator(_M_buckets + _M_bucket_count); } #ifdef _GLIBCXX_INCLUDE_AS_CXX0X const_iterator cbegin() const { const_iterator __i(_M_buckets); if (!__i._M_cur_node) __i._M_incr_bucket(); return __i; } const_iterator cend() const { return const_iterator(_M_buckets + _M_bucket_count); } #endif size_type size() const { return _M_element_count; } bool empty() const { return size() == 0; } allocator_type get_allocator() const { return allocator_type(_M_node_allocator); } _Value_allocator_type _M_get_Value_allocator() const { return _Value_allocator_type(_M_node_allocator); } size_type max_size() const { return _M_get_Value_allocator().max_size(); } // Observers key_equal key_eq() const { return this->_M_eq; } // hash_function, if present, comes from _Hash_code_base. // Bucket operations size_type bucket_count() const { return _M_bucket_count; } size_type max_bucket_count() const { return max_size(); } size_type bucket_size(size_type __n) const { return std::distance(begin(__n), end(__n)); } size_type bucket(const key_type& __k) const { return this->_M_bucket_index(__k, this->_M_hash_code(__k), bucket_count()); } local_iterator begin(size_type __n) { return local_iterator(_M_buckets[__n]); } local_iterator end(size_type) { return local_iterator(0); } const_local_iterator begin(size_type __n) const { return const_local_iterator(_M_buckets[__n]); } const_local_iterator end(size_type) const { return const_local_iterator(0); } float load_factor() const { return static_cast(size()) / static_cast(bucket_count()); } // max_load_factor, if present, comes from _9.:.;.<.=.>.?.@.A.B.C.D.E.F.G.H.I.J.K.L.M.N.O.P.Q.R.S.T.U.V.W.X.Rehash_base. // Generalization of max_load_factor. Extension, not found in TR1. Only // useful if _RehashPolicy is something other than the default. const _RehashPolicy& __rehash_policy() const { return _M_rehash_policy; } void __rehash_policy(const _RehashPolicy&); // Lookup. iterator find(const key_type& __k); const_iterator find(const key_type& __k) const; size_type count(const key_type& __k) const; std::pair equal_range(const key_type& __k); std::pair equal_range(const key_type& __k) const; private: // Find, insert and erase helper functions // ??? This dispatching is a workaround for the fact that we don't // have partial specialization of member templates; it would be // better to just specialize insert on __unique_keys. There may be a // cleaner workaround. typedef typename __gnu_cxx::__conditional_type<__unique_keys, std::pair, iterator>::__type _Insert_Return_Type; typedef typename __gnu_cxx::__conditional_type<__unique_keys, std::_Select1st<_Insert_Return_Type>, std::_Identity<_Insert_Return_Type> >::__type _Insert_Conv_Type; _Node* _M_find_node(_Node*, const key_type&, typename _Hashtable::_Hash_code_type) const; iterator _M_insert_bucket(const value_type&, size_type, typename _Hashtable::_Hash_code_type); std::pair _M_insert(const value_type&, std::_GLIBCXX_TR1 true_type); iterator _M_insert(const value_type&, std::_GLIBCXX_TR1 false_type); void _M_erase_node(_Node*, _Node**); public: // Insert and erase _Insert_Return_Type insert(const value_type& __v) { return _M_insert(__v, std::_GLIBCXX_TR1 integral_constant()); } iterator insert(iterator, const value_type& __v) { return iterator(_Insert_Conv_Type()(this->insert(__v))); } const_iterator insert(const_iterator, const value_type& __v) { return const_iterator(_Insert_Conv_Type()(this->insert(__v))); } template void insert(_InputIterator __first, _InputIterator __last); iterator erase(iterator); const_iterator erase(const_iterator); size_type erase(const key_type&); iterator erase(iterator, iterator); const_iterator erase(const_iterator, const_iterator); void clear(); // Set number of buckets to be appropriate for container of n element. void rehash(size_type __n); private: // Unconditionally change size of bucket array to n. void _M_rehash(size_type __n); }; // Definitions of class template _Hashtable's out-of-line member functions. template typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::_Node* _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _M_allocate_node(const value_type& __v) { _Node* __n = _M_node_allocator.allocate(1); try { _M_get_Value_allocator().construct(&__n->_M_v, __v); __n->_M_next = 0; return __n; } catch(...) { _M_node_allocator.deallocate(__n, 1); __throw_exception_again; } } template void _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _M_deallocate_node(_Node* __n) { _M_get_Value_allocator().destroy(&__n->_M_v); _M_node_allocator.deallocate(__n, 1); } template void _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _M_deallocate_nodes(_Node** __array, size_type __n) { for (size_type __i = 0; __i < __n; ++__i) { _Node* __p = __array[__i]; while (__p) { _Node* __tmp = __p; __p = __p->_M_next; _M_deallocate_node(__tmp); } __array[__i] = 0; } } template typename _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>::_Node** _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _M_allocate_buckets(size_type __n) { _Bucket_allocator_type __alloc(_M_node_allocator); // We allocate one extra bucket to hold a sentinel, an arbitrary // non-null pointer. Iterator increment relies on this. _Node** __p = __alloc.allocate(__n + 1); std::fill(__p, __p + __n, (_Node*) 0); __p[__n] = reinterpret_cast<_Node*>(0x1000); return __p; } template void _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _M_deallocate_buckets(_Node** __p, size_type __n) { _Bucket_allocator_type __alloc(_M_node_allocator); __alloc.deallocate(__p, __n + 1); } template _Hashtable<_Key, _Value, _Allocator, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, __chc, __cit, __uk>:: _Hashtable(size_type __bucket_hint, const _H1& __h1, const _H2& __h2, const _Hash& __h, const _Equal& __eq, const _ExtractKey& __exk, const allocator_type& __a) : __detail::_Rehash_base<_RehashPolicy, _Hashtable>(), __detail::_Hash_code_base<_Key, _Value, _ExtractKey, _Equal, _H1, _H2, _Hash, __chc>(__exk, __eq, __h1, __h2, __h), __detail::_Map_base<_Key, _Value, _ExtractKey, __uk, _Hashtable>(), _M_node_allocator(__