[Boost-bugs] [Boost C++ Libraries] #5711: Equality of unordered containers violates Library requirements

Subject: [Boost-bugs] [Boost C++ Libraries] #5711: Equality of unordered containers violates Library requirements
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2011-07-18 20:22:16

#5711: Equality of unordered containers violates Library requirements
-------------------------------------------------------------+--------------
 Reporter:  Daniel Krügler <daniel.kruegler@…>               |       Owner:  danieljames
     Type:  Bugs                                             |      Status:  new        
Milestone:  To Be Determined                                 |   Component:  unordered  
  Version:  Boost 1.47.0                                     |    Severity:  Problem    
 Keywords:  unordered_set unordered_map hash map equality    |  
-------------------------------------------------------------+--------------
 Both unordered sets and maps have operator==/!= implementations that
 violate the Library requirements of unordered containers. The following
 program makes this observable:

 {{{
 #include <iostream>
 #include <cstring>
 #include <boost/unordered_set.hpp>

 struct CharIC {

   bool operator()(char c1, char c2) const {
     return std::toupper(c1) == std::toupper(c2);
   }

   std::size_t operator()(char c) const {
     return std::toupper(c);
   }

 };

 int main()
 {
   boost::unordered_set<char, CharIC, CharIC> us1, us2;
   us1.insert('a');
   us2.insert('A');
   std::cout << "us1 == us1: " << (us1 == us1) << std::endl;
   std::cout << "us1 != us2: " << (us1 != us2) << std::endl;
 }
 }}}

 The second output is:

 us1 != us2: 0

 instead of the expected

 us1 != us2: 1

 Reason for this deviation is that the current boost implementation does
 not additionally test for equality of the container key (which is the
 value_type for sets). But this is required as of FDIS, [unord.req] p11,
 where the semantics is defined in terms of the form of std::is_permutation
 that uses operator== of the iterator value_type. The proper usage of the
 key equality test is part of the reference implementation of N3068 as
 well. As far as I read boost/unordered/detail/equivalent.hpp correctly,
 the same defect applies to the non-unique containers.

-- 
Ticket URL: <https://svn.boost.org/trac/boost/ticket/5711>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.