Are the iterators of `map<key, value, greater<>>` and `map<key, value, less<>>` guaranteed to be the same type?

Question

I have 2 maps

using BidBook = std::map<float, int, std::greater<>>; // price -> qty
using AskBook = std::map<float, int, std::less<>>;

I have a struct that contain iterator that points to element in either a BidBook or a AskBook, depending on side

enum class Side { Buy, Sell };

struct Ref {
    Side side;
    BidBook::iterator it;   // iterator into *either* bids or asks
    // AskBook::iterator ask_it;
};

If BidBook::iterator and AskBook::iterator are the same, then this struct only needs 1 iterator object. Then we can use side to figure out which version it points to. If not, we needs to store 2 iterators in Ref.

On gcc 13, both are the same type and the program below works. But is it guaranteed in the C++ standard that this works? Assuming C++11 and above.

#include <map>
#include <functional>
#include <iostream>
#include <type_traits>

using BidBook = std::map<float, int, std::greater<>>; // price -> qty
using AskBook = std::map<float, int, std::less<>>;

enum class Side { Buy, Sell };

struct Ref {
    Side side;
    BidBook::iterator it;   // iterator into *either* bids or asks
};

int main() {
    static_assert(std::is_same_v<BidBook::iterator, AskBook::iterator>,
                  "iterators must be the same to store them together");

    BidBook bids;
    AskBook asks;

    // populate
    bids[101.0f] = 10;
    bids[100.5f] = 5;

    asks[102.0f] = 7;
    asks[103.5f] = 12;

    // create refs to different books
    Ref r1{Side::Buy,  bids.begin()};  // points to best bid (101 -> 10)
    Ref r2{Side::Sell, asks.begin()};  // points to best ask (102 -> 7)

    // now later we can interpret the iterator depending on side:
    auto print_ref = [&](const Ref& r) {
        if (r.side == Side::Buy) {
            std::cout << "[BID]  price=" << r.it->first
                      << " qty=" << r.it->second << "\n";
        } else {
            // safe because iterator type is the same
            std::cout << "[ASK]  price=" << r.it->first
                      << " qty=" << r.it->second << "\n";
        }
    };

    print_ref(r1);
    print_ref(r2);

    return 0;
}

Answer 1

Your code does work with libstdc++, libc++ and MSVC's STL. All three standard libraries implement std::map with some hidden base class and don't add the comparator type to the iterator, but there is no such guarantee in the standard.

std::map::iterator is an unspecified type, another standard library implementation could easily implement it's iterator like this:

namespace std
{
  template <typename Key, typename T, typename Compare>
  class map_iterator;

  template <typename Key, typename T, typename Compare>
  class map
  {
  public:
    using iterator = map_iterator<Key, T, Compare>;
  };

  template <typename Key, typename T, typename Compare>
  class map_iterator
  {
  private:
    map<Key, T, Compare>* map;
  };
}

With this implementation BidBook::iterator and AskBook::iterator would be different types and your code wouldn't compile.

Note that using float as a std::map key is potentially error prone, see Is floating-point math broken?