What are the meaning of template parameters A, B of std::multiset<A,B> respectively, and how does it work?

Question

I have asked in another question about std::multiset, but now I see I need a decent understanding and cannot find any more complicated example in the internet.

Can you explain to me, maybe exemplarize, how std::multiset<A,B> works and what function is here of A and of B, and also if any of those can be omitted? Can I put A or B to some variable? I'd really appreciate some short example, or reference,

Answer 1

The std::multiset class template has a first template parameter specifying the type of objects to be stored in the set, and a second one specifying the type of a comparison functor. We can ignore the third template parameter for now.

The second, optional, parameter, B, must implement strict weak ordering and is used to order the set/multiset. This ordering is required to ensure the logarithmic complexity of element look-up operations. Here is an example:

struct A
{
  int x;
};

struct B
{
  bool operator()(const A& lhs, const A& rhs) const {
    return lhs.x < rhs.x;
  }
};

This class B has an operator(), which means that it can be called, for example

B comp;
A a1, a2;
bool a1lessThana2 = comp(a1, a2);

This is needed for the set/multiset to place elements in the correct location, and figure out if two elements are the same. If there is an operator< for your type, the second template parameter can be omitted.

bool operator<(constA& lhs, const A& rhs) { return lhs.x < rhs.x; }

This is an example of usage:

int main()
{
  std::multiset<A, B> m;
  A a1, a2;
  a1.x = 23;
  a2.x = 100;
  m.insert(a1);
  m.insert(a2);
}