2

I've always seen pointers as a specialization of iterators, used in the particular case where objects are stored contiguously in memory. However, I found out that the Allocator member type pointer (which then defines the same member type on iterators and containers) is not required to be a real pointer but it may be what's called a fancy pointer that, according to cppreference,

is used to access objects allocated in address spaces that differ from the homogeneous virtual address space.

This is what I used to call an iterator but not a pointer, but that's not the point. I'm wondering how an Allocator is not required to allocate contiguous memory. Imagine passing a custom allocator to std::vector that does not allocate objects in a contiguous manner. For me that's not a vector anymore. If I don't want objects to be contiguous in memory I use a list rather than a vector with a custom allocator. They just look like a big source of confusion, why were they introduced?

user7769147
  • 1,559
  • 9
  • 15
  • 1
    *Imagine passing a custom allocator to std::vector that does not allocate objects in a contiguous manner.* The vector is going to request a pointer to s specifically sized chunk of memory. If you allocator lies and returns a pointer to memory of insufficient space then you have UB. Garbe in - Garbage out – NathanOliver Jul 02 '20 at 16:12
  • @NathanOliver what I'm saying is that the allocator may not return a contiguous chuck of memory. `std::vector` accesses the allocated memory using `Allocator::pointer` that may act as a LegacyRandomAccessIterator, but not as a LegacyContiguousIterator, thus making the vector work as a list – user7769147 Jul 02 '20 at 16:17
  • *what I'm saying is that the allocator may not return a contiguous chuck of memory.*. It can't, or at least it is non-compliant if it does. On the page you linked to look at the requirements for `allocate`. It returns an array of size `n`. Arrays are contiguous, no way around that. The reason you can have a fancy pointer, is because you can be a in a structure like a list where each node is allocated with a separate call to `allocate`. That wont happen in a vector though as it only grabs a single appropriately sized chunk of memory to use. – NathanOliver Jul 02 '20 at 16:20

2 Answers2

3

So, C++ as a language has a concept of a pointer. For any type T*, the language requires certain specific things out of it. In particular, sizeof(T*) is statically-determined, and all language pointers have the same size.

In the long-before time however, the things that T* could work with did not reflect hardware capabilities. Imagine if hardware had two pools of memory, but these pools of memory have different maximum sizes. So if the compiler mapped T* to the smaller pool, then one could not have a T* that points to the larger pool of memory. After all, the address space of the larger memory would exceed the size of T*.

This led to the use of things like LONG_POINTER and the like for "pointing" into memory outside of the T* accessible space.

The goal of the allocator::pointer concept is to be able to write an allocator that can allow any allocator-aware container to work with such non-T*-compatible pools of memory transparently.

Of course... that is no longer relevant for most hardware. Virtual memory, 32 and 64-bit addressing, and the like are now standard. As such, if there's memory that's not directly accessible and you want to address it, the expectation is that you'll convert such memory into virtual addresses via OS calls which can then be used with language pointers just fine. See mapping of files and GPU memory.

It was intended to solve a problem at the library level, but the problem was instead solved at the hardware/OS level. Thus, it's an unnecessary complication of allocators and allocator-aware containers, but it remains present because of decisions made nearly 25 years ago.

Nicol Bolas
  • 449,505
  • 63
  • 781
  • 982
1

I've always seen pointers as a specialization of iterators

Iteration of arrays is one of the uses of pointers. It is not their only purpose. They are also used as a "handle" to identify dynamic allocations.

why were [fancy pointers] introduced?

The page that you linked explains a reason for their introduction:

Such pointers were introduced to support segmented memory architectures ...

These days, such architectures are quite rare, but programmers have found other use cases:

... and are used today to access objects allocated in address spaces that differ from the homogeneous virtual address space that is accessed by raw pointers. An example of a fancy pointer is the mapping address-independent pointer boost::interprocess::offset_ptr, which makes it possible to allocate node-based data structures such as std::set in shared memory and memory mapped files mapped in different addresses in every process.

The standard paper P0773R0 linked in the linked page has a more detailed list of purposes:

  • Scenario A. "Offset" pointers with a modified bit-level representation.
  • Scenario B. Small-data-area "near" pointers.
  • Scenario C. High-memory-area "far" pointers.
  • Scenario D. "Fat" pointers carrying metadata for dereference-time.
  • Scenario E. "Segmented" pointers carrying metadata for deallocate-time.

Note that not all standard library implementations support all use cases of fancy pointers for all standard containers as explored in P0773R0.

eerorika
  • 232,697
  • 12
  • 197
  • 326