// -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file trace_fn_imps.hpp * Contains implementations of cc_ht_map_'s trace-mode functions. */ #ifdef PB_DS_HT_MAP_TRACE_ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace() const { std::cerr << static_cast(m_num_e) << " " << static_cast(m_num_used_e) << std::endl; for (size_type i = 0; i < m_num_e; ++i) { std::cerr << static_cast(i) << " "; trace_list(m_entries[i]); std::cerr << std::endl; } } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace_list(const_entry_pointer p_l) const { size_type iterated_num_used_e = 0; while (p_l != NULL) { std::cerr << PB_DS_V2F(p_l->m_value) << " "; p_l = p_l->m_p_next; } } #endif // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file policy_access_fn_imps.hpp * Contains implementations of cc_ht_map_'s policy access * functions. */ PB_DS_CLASS_T_DEC Hash_Fn& PB_DS_CLASS_C_DEC:: get_hash_fn() { return *this; } PB_DS_CLASS_T_DEC const Hash_Fn& PB_DS_CLASS_C_DEC:: get_hash_fn() const { return *this; } PB_DS_CLASS_T_DEC Eq_Fn& PB_DS_CLASS_C_DEC:: get_eq_fn() { return *this; } PB_DS_CLASS_T_DEC const Eq_Fn& PB_DS_CLASS_C_DEC:: get_eq_fn() const { return *this; } PB_DS_CLASS_T_DEC Comb_Hash_Fn& PB_DS_CLASS_C_DEC:: get_comb_hash_fn() { return *this; } PB_DS_CLASS_T_DEC const Comb_Hash_Fn& PB_DS_CLASS_C_DEC:: get_comb_hash_fn() const { return *this; } PB_DS_CLASS_T_DEC Resize_Policy& PB_DS_CLASS_C_DEC:: get_resize_policy() { return *this; } PB_DS_CLASS_T_DEC const Resize_Policy& PB_DS_CLASS_C_DEC:: get_resize_policy() const { return *this; } // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file find_store_hash_fn_imps.hpp * Contains implementations of cc_ht_map_'s find related functions, * when the hash value is stored. */ // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file entry_list_fn_imps.hpp * Contains implementations of cc_ht_map_'s entry-list related functions. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: deallocate_links_in_list(entry_pointer p_e) { while (p_e != NULL) { entry_pointer p_dealloc_e = p_e; p_e = p_e->m_p_next; s_entry_allocator.deallocate(p_dealloc_e, 1); } } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::entry_pointer PB_DS_CLASS_C_DEC:: get_entry(const_reference r_val, true_type) { // Following line might throw an exception. entry_pointer p_e = s_entry_allocator.allocate(1); // Following lines* cannot* throw an exception. new (&p_e->m_value) value_type(r_val); return p_e; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::entry_pointer PB_DS_CLASS_C_DEC:: get_entry(const_reference r_val, false_type) { // Following line might throw an exception. entry_pointer p_e = s_entry_allocator.allocate(1); cond_dealtor_t cond(p_e); // Following lines might throw an exception. new (&p_e->m_value) value_type(r_val); cond.set_no_action(); return p_e; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: rels_entry(entry_pointer p_e) { // The following lines cannot throw exceptions (unless if key-data dtors do). p_e->m_value.~value_type(); s_entry_allocator.deallocate(p_e, 1); } // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file resize_no_store_hash_fn_imps.hpp * Contains implementations of cc_ht_map_'s resize related functions, when the * hash value is not stored. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::entry_pointer PB_DS_CLASS_C_DEC:: resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, false_type) { const size_type hash_pos = ranged_hash_fn_base::operator()(PB_DS_V2F(p_e->m_value)); entry_pointer const p_next_e = p_e->m_p_next; p_e->m_p_next = a_p_entries_resized[hash_pos]; a_p_entries_resized[hash_pos] = p_e; return p_next_e; } // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file find_fn_imps.hpp * Contains implementations of cc_ht_map_'s find related functions. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::point_iterator PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) return find_key_pointer(r_key, traits_base::m_store_extra_indicator); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_point_iterator PB_DS_CLASS_C_DEC:: find(const_key_reference r_key) const { _GLIBCXX_DEBUG_ONLY(assert_valid();) return const_cast(*this).find_key_pointer(r_key, traits_base::m_store_extra_indicator); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::point_iterator PB_DS_CLASS_C_DEC:: find_end() { return NULL; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_point_iterator PB_DS_CLASS_C_DEC:: find_end() const { return NULL; } // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file constructor_destructor_store_hash_fn_imps.hpp * Contains implementations of cc_ht_map_'s constructors, destructor, * and related functions. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: constructor_insert_new_imp(const_reference r_val, size_type pos, true_type) { // Following lines might throw an exception. entry_pointer p = get_entry(r_val, traits_base::s_no_throw_copies_indicator); // At this point no exceptions can be thrown. p->m_p_next = m_entries[pos]; p->m_hash = ranged_hash_fn_base::operator()((const_key_reference)(PB_DS_V2F(p->m_value))).second; m_entries[pos] = p; _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(r_key);) } // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file debug_fn_imps.hpp * Contains implementations of cc_ht_map_'s debug-mode functions. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { debug_base::check_size(m_num_used_e); assert_entry_pointer_array_valid(m_entries); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_entry_pointer_array_valid(const entry_pointer_array a_p_entries) const { size_type iterated_num_used_e = 0; for (size_type pos = 0; pos < m_num_e; ++pos) { entry_pointer p_e = a_p_entries[pos]; while (p_e != NULL) { ++iterated_num_used_e; assert_entry_pointer_valid(p_e, traits_base::m_store_extra_indicator); p_e = p_e->m_p_next; } } _GLIBCXX_DEBUG_ASSERT(iterated_num_used_e == m_num_used_e); } #include #include #endif // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file cond_key_dtor_entry_dealtor.hpp * Contains a conditional key destructor, used for exception handling. */ namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC template #define PB_DS_CLASS_C_DEC PB_DS_CKDED_CLASS_NAME /** * A conditional key destructor, used for exception handling. **/ template class PB_DS_CKDED_CLASS_NAME { public: typedef typename HT_Map::entry entry; typedef typename HT_Map::entry_allocator entry_allocator; typedef typename HT_Map::key_type key_type; inline PB_DS_CKDED_CLASS_NAME(entry_allocator* p_a, entry* p_e); inline ~PB_DS_CKDED_CLASS_NAME(); inline void set_key_destruct(); inline void set_no_action_destructor(); protected: entry_allocator* const m_p_a; entry* const m_p_e; bool m_key_destruct; bool m_no_action_destructor; }; PB_DS_CLASS_T_DEC inline PB_DS_CLASS_C_DEC:: PB_DS_CKDED_CLASS_NAME(entry_allocator* p_a, entry* p_e) : m_p_a(p_a), m_p_e(p_e), m_key_destruct(false), m_no_action_destructor(false) { } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: set_key_destruct() { m_key_destruct = true; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: set_no_action_destructor() { m_no_action_destructor = true; } PB_DS_CLASS_T_DEC inline PB_DS_CLASS_C_DEC:: ~PB_DS_CKDED_CLASS_NAME() { if (m_no_action_destructor) return; if (m_key_destruct) m_p_e->m_value.first.~key_type(); m_p_a->deallocate(m_p_e, 1); } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC } // namespace detail } // namespace __gnu_pbds // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file erase_fn_imps.hpp * Contains implementations of cc_ht_map_'s erase related functions. */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: erase_entry_pointer(entry_pointer& r_p_e) { _GLIBCXX_DEBUG_ONLY(debug_base::erase_existing(PB_DS_V2F(r_p_e->m_value))); entry_pointer p_e = r_p_e; r_p_e = r_p_e->m_p_next; rels_entry(p_e); _GLIBCXX_DEBUG_ASSERT(m_num_used_e > 0); resize_base::notify_erased(--m_num_used_e); } PB_DS_CLASS_T_DEC template inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { size_type num_ersd = 0; for (size_type pos = 0; pos < m_num_e; ++pos) { while (m_entries[pos] != NULL && pred(m_entries[pos]->m_value)) { ++num_ersd; entry_pointer p_next_e = m_entries[pos]->m_p_next; erase_entry_pointer(m_entries[pos]); m_entries[pos] = p_next_e; } entry_pointer p_e = m_entries[pos]; while (p_e != NULL && p_e->m_p_next != NULL) { if (pred(p_e->m_p_next->m_value)) { ++num_ersd; erase_entry_pointer(p_e->m_p_next); } else p_e = p_e->m_p_next; } } do_resize_if_needed_no_throw(); return num_ersd; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { for (size_type pos = 0; pos < m_num_e; ++pos) while (m_entries[pos] != NULL) erase_entry_pointer(m_entries[pos]); do_resize_if_needed_no_throw(); resize_base::notify_cleared(); } #include #include // -*- C++ -*- // Copyright (C) 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file cc_ht_map_.hpp * Contains an implementation class for cc_ht_map_. */ #include #include #include #include #include #include #include #include #ifdef _GLIBCXX_DEBUG #include #endif #ifdef PB_DS_HT_MAP_TRACE_ #include #endif #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_CLASS_NAME cc_ht_map_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_CLASS_NAME cc_ht_map_no_data_ #endif #define PB_DS_CLASS_C_DEC \ PB_DS_CLASS_NAME #define PB_DS_HASH_EQ_FN_C_DEC \ hash_eq_fn #define PB_DS_RANGED_HASH_FN_C_DEC \ ranged_hash_fn #define PB_DS_TYPES_TRAITS_C_DEC \ types_traits #ifdef _GLIBCXX_DEBUG #define PB_DS_DEBUG_MAP_BASE_C_DEC \ debug_map_base::other::const_reference> #endif #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_V2F(X) (X).first #define PB_DS_V2S(X) (X).second #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_V2F(X) (X) #define PB_DS_V2S(X) Mapped_Data() #endif // <011i$i0|\|-<|-|4i|\|i|\|g |-|4$|-| 74813. template class PB_DS_CLASS_NAME: #ifdef _GLIBCXX_DEBUG protected PB_DS_DEBUG_MAP_BASE_C_DEC, #endif public PB_DS_HASH_EQ_FN_C_DEC, public Resize_Policy, public PB_DS_RANGED_HASH_FN_C_DEC, public PB_DS_TYPES_TRAITS_C_DEC { private: typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; typedef typename traits_base::comp_hash comp_hash; typedef typename traits_base::value_type value_type_; typedef typename traits_base::pointer pointer_; typedef typename traits_base::const_pointer const_pointer_; typedef typename traits_base::reference reference_; typedef typename traits_base::const_reference const_reference_; struct entry : public traits_base::stored_value_type { typename Allocator::template rebind::other::pointer m_p_next; }; typedef cond_dealtor cond_dealtor_t; typedef typename Allocator::template rebind::other entry_allocator; typedef typename entry_allocator::pointer entry_pointer; typedef typename entry_allocator::const_pointer const_entry_pointer; typedef typename entry_allocator::reference entry_reference; typedef typename entry_allocator::const_reference const_entry_reference; typedef typename Allocator::template rebind::other entry_pointer_allocator; typedef typename entry_pointer_allocator::pointer entry_pointer_array; typedef PB_DS_RANGED_HASH_FN_C_DEC ranged_hash_fn_base; typedef PB_DS_HASH_EQ_FN_C_DEC hash_eq_fn_base; typedef Resize_Policy resize_base; #ifdef _GLIBCXX_DEBUG typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; #endif #define PB_DS_GEN_POS std::pair #include #include #include #include #undef PB_DS_GEN_POS public: typedef Allocator allocator; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef Hash_Fn hash_fn; typedef Eq_Fn eq_fn; typedef Comb_Hash_Fn comb_hash_fn; typedef Resize_Policy resize_policy; enum { store_hash = Store_Hash }; typedef typename traits_base::key_type key_type; typedef typename traits_base::key_pointer key_pointer; typedef typename traits_base::const_key_pointer const_key_pointer; typedef typename traits_base::key_reference key_reference; typedef typename traits_base::const_key_reference const_key_reference; typedef typename traits_base::mapped_type mapped_type; typedef typename traits_base::mapped_pointer mapped_pointer; typedef typename traits_base::const_mapped_pointer const_mapped_pointer; typedef typename traits_base::mapped_reference mapped_reference; typedef typename traits_base::const_mapped_reference const_mapped_reference; typedef typename traits_base::value_type value_type; typedef typename traits_base::pointer pointer; typedef typename traits_base::const_pointer const_pointer; typedef typename traits_base::reference reference; typedef typename traits_base::const_reference const_reference; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef point_iterator_ point_iterator; #endif #ifdef PB_DS_DATA_FALSE_INDICATOR typedef const_point_iterator_ point_iterator; #endif typedef const_point_iterator_ const_point_iterator; #ifdef PB_DS_DATA_TRUE_INDICATOR typedef iterator_ iterator; #endif #ifdef PB_DS_DATA_FALSE_INDICATOR typedef const_iterator_ iterator; #endif typedef const_iterator_ const_iterator; PB_DS_CLASS_NAME(); PB_DS_CLASS_NAME(const Hash_Fn&); PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&); PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&); PB_DS_CLASS_NAME(const Hash_Fn&, const Eq_Fn&, const Comb_Hash_Fn&, const Resize_Policy&); PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); virtual ~PB_DS_CLASS_NAME(); void swap(PB_DS_CLASS_C_DEC&); template void copy_from_range(It, It); void initialize(); inline size_type size() const; inline size_type max_size() const; inline bool empty() const; Hash_Fn& get_hash_fn(); const Hash_Fn& get_hash_fn() const; Eq_Fn& get_eq_fn(); const Eq_Fn& get_eq_fn() const; Comb_Hash_Fn& get_comb_hash_fn(); const Comb_Hash_Fn& get_comb_hash_fn() const; Resize_Policy& get_resize_policy(); const Resize_Policy& get_resize_policy() const; inline std::pair insert(const_reference r_val) { return insert_imp(r_val, traits_base::m_store_extra_indicator); } inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR return (subscript_imp(r_key, traits_base::m_store_extra_indicator)); #else insert(r_key); return traits_base::s_null_mapped; #endif } inline point_iterator find(const_key_reference); inline const_point_iterator find(const_key_reference) const; inline point_iterator find_end(); inline const_point_iterator find_end() const; inline bool erase(const_key_reference); template inline size_type erase_if(Pred); void clear(); inline iterator begin(); inline const_iterator begin() const; inline iterator end(); inline const_iterator end() const; #ifdef _GLIBCXX_DEBUG void assert_valid() const; #endif #ifdef PB_DS_HT_MAP_TRACE_ void trace() const; #endif private: void deallocate_all(); inline bool do_resize_if_needed(); inline void do_resize_if_needed_no_throw(); void resize_imp(size_type new_size); void do_resize(size_type new_size); void resize_imp_no_exceptions(size_type, entry_pointer_array, size_type); inline entry_pointer resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, false_type); inline entry_pointer resize_imp_no_exceptions_reassign_pointer(entry_pointer, entry_pointer_array, true_type); void deallocate_links_in_list(entry_pointer); inline entry_pointer get_entry(const_reference, false_type); inline entry_pointer get_entry(const_reference, true_type); inline void rels_entry(entry_pointer); #ifdef PB_DS_DATA_TRUE_INDICATOR inline mapped_reference subscript_imp(const_key_reference r_key, false_type) { _GLIBCXX_DEBUG_ONLY(assert_valid();) const size_type pos = ranged_hash_fn_base::operator()(r_key); entry_pointer p_e = m_entries[pos]; resize_base::notify_insert_search_start(); while (p_e != NULL && !hash_eq_fn_base::operator()(p_e->m_value.first, r_key)) { resize_base::notify_insert_search_collision(); p_e = p_e->m_p_next; } resize_base::notify_insert_search_end(); if (p_e != NULL) { _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) return (p_e->m_value.second); } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) return insert_new_imp(value_type(r_key, mapped_type()), pos)->second; } inline mapped_reference subscript_imp(const_key_reference r_key, true_type) { _GLIBCXX_DEBUG_ONLY(assert_valid();) comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); entry_pointer p_e = m_entries[pos_hash_pair.first]; resize_base::notify_insert_search_start(); while (p_e != NULL && !hash_eq_fn_base::operator()(p_e->m_value.first, p_e->m_hash, r_key, pos_hash_pair.second)) { resize_base::notify_insert_search_collision(); p_e = p_e->m_p_next; } resize_base::notify_insert_search_end(); if (p_e != NULL) { _GLIBCXX_DEBUG_ONLY(deb.6/60616263646ug_base::check_key_exists(r_key);) return p_e->m_value.second; } _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) return insert_new_imp(value_type(r_key, mapped_type()), pos_hash_pair)->second; } #endif inline std::pair insert_imp(const_reference, false_type); inline std::pair insert_imp(const_reference, true_type); inline pointer insert_new_imp(const_reference r_val, size_type pos) { if (do_resize_if_needed()) pos = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); // Following lines might throw an exception. entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator); // At this point no exceptions can be thrown. p_e->m_p_next = m_entries[pos]; m_entries[pos] = p_e; resize_base::notify_inserted(++m_num_used_e); _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) _GLIBCXX_DEBUG_ONLY(assert_valid();) return &p_e->m_value; } inline pointer insert_new_imp(const_reference r_val, comp_hash& r_pos_hash_pair) { // Following lines might throw an exception. if (do_resize_if_needed()) r_pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(r_val)); entry_pointer p_e = get_entry(r_val, traits_base::m_no_throw_copies_indicator); // At this point no exceptions can be thrown. p_e->m_hash = r_pos_hash_pair.second; p_e->m_p_next = m_entries[r_pos_hash_pair.first]; m_entries[r_pos_hash_pair.first] = p_e; resize_base::notify_inserted(++m_num_used_e); _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) _GLIBCXX_DEBUG_ONLY(assert_valid();) return &p_e->m_value; } inline pointer find_key_pointer(const_key_reference r_key, false_type) { entry_pointer p_e = m_entries[ranged_hash_fn_base::operator()(r_key)]; resize_base::notify_find_search_start(); while (p_e != NULL && !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) { resize_base::notify_find_search_collision(); p_e = p_e->m_p_next; } resize_base::notify_find_search_end(); #ifdef _GLIBCXX_DEBUG if (p_e == NULL) debug_base::check_key_does_not_exist(r_key); else debug_base::check_key_exists(r_key); #endif return &p_e->m_value; } inline pointer find_key_pointer(const_key_reference r_key, true_type) { comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(r_key); entry_pointer p_e = m_entries[pos_hash_pair.first]; resize_base::notify_find_search_start(); while (p_e != NULL && !hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, r_key, pos_hash_pair.second)) { resize_base::notify_find_search_collision(); p_e = p_e->m_p_next; } resize_base::notify_find_search_end(); #ifdef _GLIBCXX_DEBUG if (p_e == NULL) debug_base::check_key_does_not_exist(r_key); else debug_base::check_key_exists(r_key); #endif return &p_e->m_value; } inline bool erase_in_pos_imp(const_key_reference, size_type); inline bool erase_in_pos_imp(const_key_reference, const comp_hash&); inline void erase_entry_pointer(entry_pointer&); #ifdef PB_DS_DATA_TRUE_INDICATOR void inc_it_state(pointer& r_p_value, std::pair& r_pos) const { inc_it_state((const_mapped_pointer& )r_p_value, r_pos); } #endif void inc_it_state(const_pointer& r_p_value, std::pair& r_pos) const { _GLIBCXX_DEBUG_ASSERT(r_p_value != NULL); r_pos.first = r_pos.first->m_p_next; if (r_pos.first != NULL) { r_p_value = &r_pos.first->m_value; return; } for (++r_pos.second; r_pos.second < m_num_e; ++r_pos.second) if (m_entries[r_pos.second] != NULL) { r_pos.first = m_entries[r_pos.second]; r_p_value = &r_pos.first->m_value; return; } r_p_value = NULL; } void get_start_it_state(pointer& r_p_value, std::pair& r_pos) const { for (r_pos.second = 0; r_pos.second < m_num_e; ++r_pos.second) if (m_entries[r_pos.second] != NULL) { r_pos.first = m_entries[r_pos.second]; r_p_value = &r_pos.first->m_value; return; } r_p_value = NULL; } #ifdef _GLIBCXX_DEBUG void assert_entry_pointer_array_valid(const entry_pointer_array) const; void assert_entry_pointer_valid(const entry_pointer, true_type) const; void assert_entry_pointer_valid(const entry_pointer, false_type) const; #endif #ifdef PB_DS_HT_MAP_TRACE_ void trace_list(const_entry_pointer) const; #endif private: #ifdef PB_DS_DATA_TRUE_INDICATOR friend class iterator_; #endif friend class const_iterator_; static entry_allocator s_entry_allocator; static entry_pointer_allocator s_entry_pointer_allocator; static iterator s_end_it; static const_iterator s_const_end_it; static point_iterator s_find_end_it; static const_point_iterator s_const_find_end_it; size_type m_num_e; size_type m_num_used_e; entry_pointer_array m_entries; enum { store_hash_ok = !Store_Hash || !is_same::value }; PB_DS_STATIC_ASSERT(sth, store_hash_ok); }; #include #include #include #include #include #include #include #include #include #include #include #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_HASH_EQ_FN_C_DEC #undef PB_DS_RANGED_HASH_FN_C_DEC #undef PB_DS_TYPES_TRAITS_C_DEC #undef PB_DS_DEBUG_MAP_BASE_C_DEC #undef PB_DS_CLASS_NAME #undef PB_DS_V2F #undef PB_DS_V2S } // namespace detail } // namespace __gnu_pbds // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file iterators_fn_imps.hpp * Contains implementations of cc_ht_map_'s iterators related functions, e.g., * begin(). */ PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC::s_end_it; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC::s_const_end_it; PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: begin() { pointer p_value; std::pair pos; get_start_it_state(p_value, pos); return iterator(p_value, pos, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: end() { return s_end_it; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: begin() const { pointer p_value; std::pair pos; get_start_it_state(p_value, pos); return const_iterator(p_value, pos, this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::const_iterator PB_DS_CLASS_C_DEC:: end() const { return s_const_end_it; } // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file standard_policies.hpp * Contains standard policies for cc_ht_map types. */ #ifndef PB_DS_CC_HT_MAP_STANDARD_POLICIES_HPP #define PB_DS_CC_HT_MAP_STANDARD_POLICIES_HPP #include #endif // #ifndef PB_DS_CC_HT_MAP_STANDARD_POLICIES_HPP // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file cmp_fn_imps.hpp * Contains implementations of cc_ht_map_'s entire container comparison related * functions. */ PB_DS_CLASS_T_DEC template bool PB_DS_CLASS_C_DEC:: operator==(const Other_HT_Map_Type& other) const { return cmp_with_other(other); } PB_DS_CLASS_T_DEC template bool PB_DS_CLASS_C_DEC:: cmp_with_other(const Other_Map_Type& other) const { if (size() != other.size()) return false; for (typename Other_Map_Type::const_iterator it = other.begin(); it != other.end(); ++it) { const_key_reference r_key = const_key_reference(PB_DS_V2F(*it)); const_mapped_pointer p_mapped_value = const_cast(*this). find_key_pointer(r_key, traits_base::m_store_extra_indicator); if (p_mapped_value == NULL) return false; #ifdef PB_DS_DATA_TRUE_INDICATOR if (p_mapped_value->second != it->second) return false; #endif } return true; } PB_DS_CLASS_T_DEC template bool PB_DS_CLASS_C_DEC:: operator!=(const Other_HT_Map_Type& other) const { return !operator==(other); } // -*- C++ -*- // Copyright (C) 2005, 2006 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, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, 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