What does struct rebind::other mean?

Question

this question follows from my previous one: Why shouldn't C++ operator new/delete/variants be in header files?. To quickly summarize, I'm learning about overriding global operator new, delete, etc. I now have need for a custom allocator class (my overloaded operator new calls std::set::insert(...), which seems to itself call new, thus infinite recusion). I think that if I supply a custom allocator (that, for example, uses malloc instead of new) to my std::set I can bypass the infinite recursion.

I've done some reading about implementing custom allocators, and am a bit confused by the semantics of struct rebind.

There is a good Q&A here: Parsing allocator::rebind calls, but I'm confused by one particular item still. cplusplus.com says about struct rebind:

Its member type other is the equivalent allocator type to allocate elements of type Type

I don't understand how other is a member of struct rebind. The definitions for struct rebind I've found look like:

template <class Type> struct rebind {
  typedef allocator<Type> other;
};

I don't see how other is a member variable of struct rebind. It's just typedefed. If I did typedef int foo; in the global namespace, that doesn't mean there's a global variable of type int declared in the global namespace, so in turn, how does other become a member of struct rebind?

By the way, I know (or at least I've read that) this has all been simplified post C++11, but I'd still like to understand this first, so that I have my fundamentals down. Thanks for any help.

While on this topic, can someone also explain the deal with typedefing within a struct? I've seen it once before in this amazing example from answerer Johannes Schaub, but I don't fully grok it yet. To me it looks like it's restricting the scope of the typedef to within an instance of the containing struct.

UPDATE:

I'd like to add this to my question. Using this abridged example from cppreference.com:

#include <memory>
#include <iostream>
#include <string>

int main()
{
    std::allocator<int> a1; // default allocator for ints

    decltype(a1)::rebind<std::string>::other a2_1;
}

Isn't the line decltype(a1)::rebind<std::string>::other a2_1; a long way of saying std::allocator<std::string> a2_1; ?

Answer 1

I don't see how other is a member variable of struct rebind.

It's not.

It's just typedefed.

That's right. It's a member type, just as the quote says.

While on this topic, can someone also explain the deal with typedefing within a struct? I've seen it once before in this amazing example from answerer Johannes Schaub, but I don't fully grok it yet.

It's hard to give an example that won't simply have the same problem (as you didn't state what you don't understand about litb's example), but here we go:

struct Foo
{
   typedef int bar;
};

Foo::bar x = 42;  // creates an int named `x`, because Foo::bar is int

To me it looks like it's restricting the scope of the typedef to within an instance of the containing struct.

That's right. The resulting type is a member of the class, just like a nested class would be, and just like a class is a member of its enclosing namespace(s).

By the way, I know (or at least I've read that) this has all been simplified post C++11

No, member types have not fundamentally changed in any revision of the language (although the new using syntax optionally makes it easier to declare them).

If I did typedef int foo; in the global namespace, that doesn't mean there's a global variable of type int declared in the global namespace

No, but there would be a type called foo in the global namespace.

Isn't the line decltype(a1)::rebind<std::string>::other a2_1; a long way of saying std::allocator<std::string> a2_1; ?

Yes; a long way, and a way that works no matter what a1 is (so the result may not be std::allocator<T> at all). That's important when you're writing templates.