Failure on initialization of unordered map

Question

and thanks for any input. I have a large dataset I am trying to manipulate. I am holding active elements in a list, and removing them when they become inactive. I want to hold all elements active and inactive in some data structure. Currently trying a map or an unordered_map, but am welcome to any suggestions.

I am compiling with

clang++ -std=c++11 -Wall -Wextra

When trying map:

#include <map>
std::map <class1, std::string> fullMap;
//and later...
for (std::list<class1>::iterator x = l.begin(); x != l.end(); x++)
{
    fullMap[(*x)] =  s
}

output reads:

error: invalid operands to binary expression ('const class1' and 'const class1') { return __x < __y; }

Even though I have overloaded the less than operator for class1. This error originates at the overloaded bracket operators for map. To circumvent I tried storing in an unordered_map.

#include <unordered_map>
std::unordered_map <class1, std::string> fullMap;

and the program fails at the initialization of fullMap with the even more confusing:

/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.4/include/g++-v4/bits/hashtable_policy.h:830:23: error: implicit instantiation of undefined template 'std::hash' bool __use_ebo = !__is_final(_Tp) && __is_empty(_Tp)> ^

/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.4/include/g++-v4/bits/hashtable_policy.h:1073:15: note: in instantiation of default argument for '_Hashtable_ebo_helper<1, std::hash >' required here private _Hashtable_ebo_helper<1, _H1>, ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.4/include/g++-v4/bits/hashtable_policy.h:1403:12: note: in instantiation of template class 'std::__detail::_Hash_code_base >, std::__detail::_Select1st, std::hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, true>' requested here : public _Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, ^

/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.4/include/g++-v4/bits/hashtable.h:175:14: note: in instantiation of template class 'std::__detail::_Hashtable_base >, std::__detail::_Select1st, std::equal_to, std::hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Hashtable_traits >' requested here : public __detail::_Hashtable_base<_Key, _Value, _ExtractKey, _Equal, ^

/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.4/include/g++-v4/bits/unordered_map.h:100:18: note: in instantiation of template class 'std::_Hashtable >, std::allocator > >, std::__detail::_Select1st, std::equal_to, std::hash, std::__detail::_Mod_range_hashing, std::__detail::_Default_ranged_hash, std::__detail::_Prime_rehash_policy, std::__detail::_Hashtable_traits >' requested here _Hashtable _M_h; ^

main.cpp:34:44: note: in instantiation of template class 'std::unordered_map, std::hash, std::equal_to, std::allocator > > >' requested here std::unordered_map fullMap; ^

/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.4/include/g++-v4/bits/functional_hash.h:58:12: note: template is declared here struct hash;

I tried to cut the code down only to the relevant chunks, but let me know if more information is needed. Thanks for reading, any help is appreciated.

//
//  class1.hpp
//  class
//
//  Created by Roach on 9/3/16.
//  Copyright © 2016 Roach. All rights reserved.
//

#ifndef class1_hpp
#define class1_hpp

#include <iostream>
#include <sstream>
#include <iomanip>
#include <ctime>


class class1
{
public:
  class1 ();
  class1 (const class1& t); // copy constructor
  ~class1 (); // destructor
  class1& operator = (const class1& t); // assignment operator
  bool operator == (const class1& t); // comparison operator
  void setSetting2 (std::string t);
  void setSetting1 (std::string p);
  void setSetting3 (double d);
  void setSetting4 (double d);
  std::tm getTime () const;
  std::string getSetting2 () const;
  double getSetting3 () const;
  double getSetting4 () const;
  std::string getSetting1 () const;
  void setSetting3End (double d);
  void setSetting4End (double d);
  double getSetting3End () const;
  double getSetting4End () const;
  double getSetting3flag () const;
  double getSetting4flag () const;
  double getSetting3final () const; // in pips
  double getSetting4final () const; // in pips
  void processList (class1::class1 t);
  void setNew ();
  //void dump (std::ostream& os) const;

private:
  std::string setting1;
  double setting4;
  double setting3;
  std::tm setting2;
  double setting4End_;
  double setting3End_;
  bool setting4Flag_;
  bool setting3Flag_;
  double setting4final_; // in pips
  double setting3final_; // in pips
};
// stream extraction operator
std::ostream& operator << (std::ostream& os, const class1& s);
std::istream& operator >> (std::istream& is, class1& t);

endif /* class1_hpp */

The following is my overloaded less than operator (I know it isn't the most succinct or efficient):

bool class1::operator< (const class1& t)
{
  if (this->time_.tm_year < t.time_.tm_year) {return true;}
  else if (this->time_.tm_year > t.time_.tm_year) {return false;}
  else if (this->time_.tm_mon < t.time_.tm_mon) {return true;}
  else if (this->time_.tm_mon > t.time_.tm_mon) {return false;}
  else if (this->time_.tm_mday < t.time_.tm_mday) {return true;}
  else if (this->time_.tm_mday > t.time_.tm_mday) {return false;}
  else if (this->time_.tm_hour < t.time_.tm_hour) {return true;}
  else if (this->time_.tm_hour > t.time_.tm_hour) {return false;}
  else if (this->time_.tm_min < t.time_.tm_min) {return true;}
  else if (this->time_.tm_min > t.time_.tm_min) {return false;}
  else if (this->time_.tm_sec < t.time_.tm_sec) {return true;}
  else {return false;}
}

Well, you probably didn't declare the relevant operations necessary to use your type as a map key. — Kerrek SB
– Kerrek SB, Commented Sep 22, 2016 at 23:11
Can you post the interface for class1? Also, what's the definition of l? — templatetypedef
– templatetypedef, Commented Sep 22, 2016 at 23:12
@KerrekSB I have overloaded assignment, equality, less than, stream extraction and insertion, as well as all the usual constructors. Is there something I am missing I am not aware of? — Free Url
– Free Url, Commented Sep 22, 2016 at 23:17
@templatetypedef I will post header file as edit at bottom of the post in a few min. Also 'l' is a std::list — Free Url
– Free Url, Commented Sep 22, 2016 at 23:19
Re: "I tried to cut the code down only to the relevant chunks, but let me know if more information is needed": Yes: what's needed a minimal, complete, and verifiable example. — ruakh
– ruakh, Commented Sep 22, 2016 at 23:19

sjrowlinson · Accepted Answer · 2016-09-22 23:45:51Z

2

The issue is that std::map<key_type, value_type> requires a properly defined operator< for key_type, in this case your operator< is not const specified so it is incompatible with std::map as this data structure requires that the comparator not alter the key object in any way. Thus the solution is to mark class1::operator< as const.

The second error notes that no hash function-object has been applied for use with std::unordered_map, this would require the following framework:

auto class1_hasher = [](const class1& c) -> std::size_t { return {some hash based on c}; }
std::unordered_map<class1, std::string, decltype(class1_hasher)> um;

answered Sep 22, 2016 at 23:45

sjrowlinson

3,3651 gold badge22 silver badges37 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

templatetypedef · Accepted Answer · 2016-09-22 23:31:50Z

1

I think the issue here is that you're breaking the preconditions required of the std::map and std::unordered_map interfaces.

In a std::map, the key type needs to be able to be compared using the less-than operator. This means that you either need to provide an overload of operator <, or provide a custom comparator when you're using the std::map type. Since you didn't provide a way of doing this with your type, the internal implementation of std::map wasn't able to make an expression of the form

 somethingOfTypeClass1 < somethingElseOfTypeClass1

compile, hence your error message.

When you switched to std::unordered_map, you ran into trouble because, in order to store something as a key in an std::unordered_map, you need to specialize the std::hash template on your custom type because the internal works of an unordered_map require that the type is hashable. That's the second error you got.

To fix this issue, either

Define a custom operator < or comparator type for class1, then use std::map, or
Define a custom std::hash for class1, then use std::unordered_map.

answered Sep 22, 2016 at 23:31

templatetypedef

376k112 gold badges954 silver badges1.1k bronze badges

3 Comments

Free Url Over a year ago

Thanks for the continued help. Although I don't have the hash function for the unordered_map defined, I do have an overloaded less than operator which is why I don't understand why std::map isn't working. I've added it at the bottom of my original post.

Paul Over a year ago

@Zroach Make your operator< const - bool class1::operator< (const class1& t) const and your std::map should work.

Free Url Over a year ago

@Paul, you are correct, ArchbishopofBanterbury suggested that above in comments on my post and that was the answer. Waiting for someone to include this in the answer to mark as solved, though I guess this answer will do with these comments attached. Thanks paul.

Pavan Chandaka · Accepted Answer · 2016-09-22 23:42:42Z

0

Its difficult to suggest best data structure until we know the functionality requirement. But the Below code is working for me on GCC 4.9.3. Please check your include files and syntax.

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <list>

using namespace std;

int main()
{
//LIST
std::list<int> myList;
myList.push_front(1);
myList.push_front(2);
myList.push_front(3);
myList.push_front(4);    

//STRING
string s = "Test";

//MAP    
std::map <int, std::string> fullMap;   
for (std::list<int>::iterator x = myList.begin(); x != myList.end(); x++)
{               
    fullMap.insert(std::make_pair(*x,s));

}

//UNORDERED MAP    
std::unordered_map <int, std::string> fullUnorderedMap;   
for (std::list<int>::iterator y = myList.begin(); y != myList.end(); y++)
{        
     fullUnorderedMap.insert(std::make_pair(*y,s));
}

//PRINTING    
for(auto it = fullMap.begin(); it != fullMap.end(); ++it)
{

    cout<<it->first<<"       "<<it->second<<endl;

}

for(auto it = fullUnorderedMap.begin(); it != fullUnorderedMap.end(); ++it)
{

    cout<<it->first<<"       "<<it->second<<endl;

}

}

answered Sep 22, 2016 at 23:42

Pavan Chandaka

13k5 gold badges35 silver badges42 bronze badges

2 Comments

templatetypedef Over a year ago

With the code updated in the question it looks like the issue is that the key type in the map didn't support the proper operations. You're using int keys, which do support all the necessary operations, hence the lack of errors.

Pavan Chandaka Over a year ago

I agree. He should overload comparator operator.

Collectives™ on Stack Overflow

Failure on initialization of unordered map

3 Answers 3

Comments

3 Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

3 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related