Overload custom comparator to std::map

Question

I am trying to solve this problem. I came up with this solution:

typedef unordered_map<string, double> stockDictType;

class StockTicker {
  class Comparator {
  public:
    inline bool operator() (const string &a, const string &b) const {
      return stocksDict.at(a) < stocksDict.at(b);
    }
  };

  stockDictType stocksDict;

  map<string, stockDictType::iterator, Comparator> stocksTicker; // this is where I need a custom comparator method

  int tickerSize;

public:
  StockTicker(int k): tickerSize(k) {}

  // some other methods
};

As is evident, this fails to compile: StockTicker::stocksDict is not a static member. Now I can't make it so because I could require multiple instances of the StockTicker class.

std::map uses a strict comparator function parameter definition (std::map will only pass in the keys to be compared), so I can't overload it to pass a reference to the current instance of the StockTicker class (which I could've used to get access to StockTicker::stocksDict through public getters)

I took inspiration from this SO question and the subsequent answer to do this:

typedef unordered_map<string, double> stockDictType;

class StockTicker {
  class Comparator {
  public:
    stockDictType &_stockDictRef;

    explicit Comparator(stockDictType &stocksDict): _stockDictRef(stocksDict) {}

    inline bool operator() (const string &a, const string &b) const {
      return _stockDictRef.at(a) < _stockDictRef.at(b);
    }
  };

  stockDictType stocksDict;
  map<string, stockDictType::iterator, Comparator> stocksTicker(Comparator{stocksDict});
  int tickerSize;

public:
  StockTicker(int k): tickerSize(k) {}

  void addOrUpdate(string name, double price) {
    stocksDict[name] = price;
    stocksTicker.at(name) = stocksDict.find(name);
  }

  vector<stockDictType::iterator> top() {
    vector<stockDictType::iterator> ret(tickerSize);

    auto it = stocksTicker.begin();
    for(int i = 0; i < tickerSize; i++, it++)
      ret[i] = it->second;

    return ret;
  }
};

This won't compile either. I get this kind of error in the StockTicker::addOrUpdate() and StockTicker::top() methods: error: '((StockTicker*)this)->StockTicker::stocksTicker' does not have class type.

I tried a bunch of other stuff too (like declaring a public comparator method in the StockTicker class itself and trying to pass a function pointer of it to std::map. That failed as well; StockTicker::stocksTicker gets declared before the comparator method does and the compiler complains).

Any ideas on how to go about fixing this?

score 2 · Accepted Answer · answered Mar 31 '17 at 17:11

2

 std::map<std::string, stockDictType::iterator, Comparator> stocksTicker(Comparator(stocksDict));

this defines a member function named stocksTicker that takes a stocksDict argument of type Comparator and returns a std::map.

std::map<std::string, stockDictType::iterator, Comparator> stocksTicker{Comparator{stocksDict}};

This defines a member variable stocksTicker which, by default, is initialized with a Comparator, which in turn was initialized with the member variable stocksDict.

I assume you want the second.

Your syntax was partway between the two. Whatever compiler you had got confused by this.

Live example

You should StockTicker(StockTicker &&)=delete and StockTicker& operator=(StockTicker &&)=delete, as maps containing references to their containing class are not safe to move or copy.

Generating an efficient move here is tricky. I suspect C++17 node splicing might make it possible to do it. You might have to embed a std::shared_ptr<stocksDict*> (yes, a shared pointer to a pointer), and use .key_comp to reseat the stocksDict in the target.

answered Mar 31 '17 at 17:11

Yakk - Adam Nevraumont

262,606
27
330
524

This works perfectly. The last two paragraphs make zero sense to me though. Anywhere I can find more explanation on that? – Quirk Mar 31 '17 at 17:47
@Quirk If you have a `struct foo` and within `foo` you store a pointer *back to the struct*, the default move/copy operators will end up with the copied-to `foo` containing a pointer *back to the original foo*. Like this: `struct foo { foo* self; foo():self(this) {} }; foo f1; foo f2=f1;` now `f2.self == &f1;` which is **usually** not what you want. Your comparator in the map effectively has a pointer-to-the-object-containing-the-map (well, to a member field in the object). 2nd last paragraph says easy way to fix this is to ban move/copy. – Yakk - Adam Nevraumont Mar 31 '17 at 17:49
Thanks! I was also wondering why this did not work: `std::map stocksTicker((Comparator(stocksDict)));` According to [this answer](http://stackoverflow.com/a/28955450/2844164), this should've bypassed the syntax problem, isn't it? – Quirk Mar 31 '17 at 17:52
1

@quirk `()` are not allowed in inline variable init in a class. Use `{}`s – Yakk - Adam Nevraumont Mar 31 '17 at 17:58

Overload custom comparator to std::map

1 Answers1