std::map of objects or object pointers?

Question

I have two options to create a std map. I can work with both the types of map.

1.    std::map<A, std::string>    
2.    std::map<A*, std::string>

where A is a class object

Later in the code I will have to perform a find operation.

1.    std::map<A, std::string>   myMap1;
          if(myMap1.find(A_obj) != myMap1.end())
          {
          }

2.    std::map<A*, std::string>   myMap2;
          if(myMap2.find(A_obj_ptr) != myMap2.end())
          {
          }

I want to know which one is recommend to create. In which of these two, would I not have to overload any operators in class A for find operation to work. Which of these would have problems on insert operation when any operators are not overloaded.

If it helps, this is class A

class A
{
    private:
        std::vector<std::string> m_member;

    public:
        A(std::vector<std::string> input);  
};

Depends on what your object represents. For such a decision one needs more information about `A`. — Sebastian Hoffmann, Feb 11 '14 at 18:18
Also consider using (1) a std::unordered_map for faster lookup times (given a suitable hash function and perhaps a cached hash), or (2) a sorted std::vector> for better cache locality. — metal, Feb 11 '14 at 18:27
I hope that isn't all there is to class A verbatim. Is there a free operator for comparing, `bool operator <(const A& lhs, const A& rhs)` because I don't see (1) even being valid to compile without it. An unordered map has better chances, but even then it needs a way to hash an A into something. Finally, for a regular map the (2)is only valid if *all* the addresses used for your A's are from the same contiguous sequence, as the standard only allows range-comparison from said-sequence +1 to be valid for evaluation. I.e. `p1 < p2` where they *not* from the same sequence is not legit. — WhozCraig, Feb 11 '14 at 19:29
@Whoz `map` uses `less` rather than `<` by default, and `less ` is required to provide a total order over pointers. (This doesn't mean it's a good idea, of course.) — Alan Stokes, Feb 11 '14 at 19:31
@AlanStokes I'm aware of this. The posted code is using the default `std::less` for the comparator, and as you're aware *it* defaults to invoking `operator <`. Thus why I even brought it up. Certainly specializing `std::less<>` for `A` is valid as well, but no such specialization seems present from the posted code (or at least it wasn't mentioned). Are you referring to (2) ? If so, news to me. Where is that in the std if you don't mind my asking? — WhozCraig, Feb 11 '14 at 19:33
@Whoz I don't understand your remark about contiguous ranges then. A map with arbitrary pointers as keys is legal, precisely because `less` must give a total order. — Alan Stokes, Feb 11 '14 at 19:36
nm. I just found what you were referring to. 20.3.3, [Johanes covers it nicely with this answer](http://stackoverflow.com/questions/1098966/universal-less-for-pointers-in-c-standard). Muchos Gracias for the schooling, kind sir =P. You certainly knew what I was referring to, I was simply not aware of the universality of `std::less<>` Hey, I learned something today!! — WhozCraig, Feb 11 '14 at 19:38
@WhozCraig I didn't overload any operator, because I wasn't sure what & why to overload. Now I know and everything works with `operator<` being overloaded. Need to learn more about hashing and a way to make it work with unordered_map. — ontherocks, Feb 11 '14 at 19:50

score 8 · Accepted Answer · answered Feb 11 '14 at 18:23

8

Note that these two samples are only functionally equivalent if A instances are singletons. Otherwise it's very possible that two A values which are equal in value but different in address. This would lead to different semantics.

Personally I prefer the std::map<A, std::string> version because the semantics of it are crystal clear. The keys have equality semantics and there is no potentially for a dangling or nullptr value. The std::map<A*, std::string> version comes with a host of questions for the developer looking through the code

Who owns the key values?
Are all instances of A singletons? If not how do I ensure the A I'm looking for is the A* value that is stored?
When are the keys freed?

answered Feb 11 '14 at 18:23

JaredPar

733,204
149
1,241
1,454

4

Good questions. If one follow's [Herb Sutter's sage advice](http://herbsutter.com/2013/06/05/gotw-91-solution-smart-pointer-parameters), raw pointers are only non-owning observers. For ownership, one would use a suitable smart pointer (usually, std::unique_ptr for unique ownership or std::shared_ptr for shared ownership). – metal Feb 11 '14 at 18:31
You are right. std::map is cleaner. But then I will have to overload operators like map::key_comp for find to work and other operator for insert to work. Am I right? Could you please provide an example what do I need to do for insert and find to work in this case. – ontherocks Feb 11 '14 at 18:31
1

@ontherocks in order to be a key in `std::map` there only needs to exist a valid implementation of `std::less`. That can be done by having a template specialization or adding operator `<` to the type – JaredPar Feb 11 '14 at 18:34
Why does it work with `std::map` without any operator overloading? Because pointers are numbers? – ontherocks Feb 11 '14 at 19:54

Nipun Talukdar · Answer 2 · 2014-02-11T19:38:45.540

First option is preferable. For second option, we need to make sure that keys (pointers here) are protected. May be shared pointers will help. Other issue is that the map will be shorted w.r.t. the address of the A objects and that might not be very useful. Below sample demonstrates how the comparator can be defined or the default comparator can be overridden:

class A 
{
public:
    int a;  
};

namespace std 
{
   template<> 
   struct less<A*>
   {
    bool operator()(const A* const a, const A*  const b) const{
        return a->a < b->a;

   }
};

std::map of objects or object pointers?

2 Answers2