What's the Advantage of Using Std::Allocator Instead of New in C++

What's the advantage of using std::allocator instead of new in C++?

std::allocator is the default memory allocator for the standard library containers, and you can substitute your own allocators. This allows you to control how the standard containers allocate memory. But I don't think that your question is about std::allocator specifically, but rather the strategy of allocating memory, then constucting objects in that memory, rather than using new T[N], for example.

And the reason for that is that new T[N] doesn't allow you control over what constructors are called. And it forces you to construct all your objects at the same time. This is terrible for the purposes of, for example, std::vector where you only want to allocate occasionally.

With a raw memory allocator, you can allocate a certain amount of memory, which determines your capacity. Then, as the user adds items to the vector (using the constructor of their choice), you can construct objects in place in this memory.

Then when you run out of memory, you allocate more, typically twice as much. If std::vector used new T[N], it would have to reallocate every time you wanted to add or remove an element, which would be terrible for performance. You would also be forced to use the default constructor for all the objects, which puts an unnecessary restriction on the types of objects std::vector can hold.

What is std::allocator and why do I need it?

In short, it is useful to be able to control how you allocate dynamic memory. The obvious answer is new and delete, but sometimes people use other types of memory allocation, such as allocating a big amount of memory upfront and chunking it or just using the stack as memory.

The allocator model abstracts over this, by providing functions that give the containers memory to play around with. We don't really care where the memory we use comes from, just that there is enough of it when we need it.

std::allocator in itself uses new and delete, and is the template default for all standard library containers. It is the default choice when you do not want any other allocation model. So to answer your question, you use std::allocator all the time, whenever you don't provide another allocator to your containers.

Why does std::vector use std::allocator instead of operator new and delete?

What could go wrong if I use new and delete?

T* p = new T[newallow];

One reason is that this won't compile if T doesn't have default constructor.

The basic idea of allocator is to separate the steps of allocating memory and object construction. Default new combines the both. In case of vector reserve we only want to allocate the required memory. We can't construct or initialize the objects at that time since the type may not be default constructible. The objects can be constructed later only when we pass the objects to store in some other operation, e.g.

v[i] = myObj;

This can't be achieved without separating memory allocation and object construction in two different steps.

Also note that, allocator have advanced usages when someone wants to customize the memory allocation.

The book mentions that we have to use std::allocator because the vector's data structure consists some initialized data and some uninitialized data.

What author meant here is that while growing the capacity by calling reserve we will have two types of data:

1. Existing objects in the vector which needs to be moved to new space. They are initialized data.
2. Extra reserved space which doesn't store any object yet and thus uninitialized.

C++ STL allocator vs operator new

For general programming, yes you should use new and delete.

However, if you are writing a library, you should not!
I don't have your textbook, but I imagine it is discussing allocators in the context of writing library code.

Users of a library may want control over exactly what gets allocated from where. If all of the library's allocations went through new and delete, the user would have no way to have that fine-grained level of control.

All STL containers take an optional allocator template argument. The container will then use that allocator for its internal memory needs. By default, if you omit the allocator, it will use std::allocator which uses new and delete (specifically, ::operator new(size_t) and ::operator delete(void*)).

This way, the user of that container can control where memory gets allocated from if they desire.

Example of implementing a custom allocator for use with STL, and explanation: Improving Performance with Custom Pool Allocators for STL

Side Note: The STL approach to allocators is non-optimal in several ways. I recommend reading Towards a Better Allocator Model for a discussion of some of those issues.

Edit in 2019: The situation in C++ has improved since this answer was written. Stateful allocators are supported in C++11, and that support was improved in C++17. Some of the people involved in the "Towards a Better Allocator Model" were involved in those changes (eg: N2387), so that's nice (:

Why should C++ programmers minimize use of 'new'?

There are two widely-used memory allocation techniques: automatic allocation and dynamic allocation. Commonly, there is a corresponding region of memory for each: the stack and the heap.

Stack

The stack always allocates memory in a sequential fashion. It can do so because it requires you to release the memory in the reverse order (First-In, Last-Out: FILO). This is the memory allocation technique for local variables in many programming languages. It is very, very fast because it requires minimal bookkeeping and the next address to allocate is implicit.

In C++, this is called automatic storage because the storage is claimed automatically at the end of scope. As soon as execution of current code block (delimited using {}) is completed, memory for all variables in that block is automatically collected. This is also the moment where destructors are invoked to clean up resources.

Heap

The heap allows for a more flexible memory allocation mode. Bookkeeping is more complex and allocation is slower. Because there is no implicit release point, you must release the memory manually, using delete or delete[] (free in C). However, the absence of an implicit release point is the key to the heap's flexibility.

Reasons to use dynamic allocation

Even if using the heap is slower and potentially leads to memory leaks or memory fragmentation, there are perfectly good use cases for dynamic allocation, as it's less limited.

Two key reasons to use dynamic allocation:

• You don't know how much memory you need at compile time. For instance, when reading a text file into a string, you usually don't know what size the file has, so you can't decide how much memory to allocate until you run the program.

• You want to allocate memory which will persist after leaving the current block. For instance, you may want to write a function string readfile(string path) that returns the contents of a file. In this case, even if the stack could hold the entire file contents, you could not return from a function and keep the allocated memory block.

Why dynamic allocation is often unnecessary

In C++ there's a neat construct called a destructor. This mechanism allows you to manage resources by aligning the lifetime of the resource with the lifetime of a variable. This technique is called RAII and is the distinguishing point of C++. It "wraps" resources into objects. std::string is a perfect example. This snippet:

int main ( int argc, char* argv[] )
{
    std::string program(argv[0]);
}

actually allocates a variable amount of memory. The std::string object allocates memory using the heap and releases it in its destructor. In this case, you did not need to manually manage any resources and still got the benefits of dynamic memory allocation.

In particular, it implies that in this snippet:

int main ( int argc, char* argv[] )
{
    std::string * program = new std::string(argv[0]);  // Bad!
    delete program;
}

there is unneeded dynamic memory allocation. The program requires more typing (!) and introduces the risk of forgetting to deallocate the memory. It does this with no apparent benefit.

Why you should use automatic storage as often as possible

Basically, the last paragraph sums it up. Using automatic storage as often as possible makes your programs:

• faster to type;
• faster when run;
• less prone to memory/resource leaks.

Bonus points

In the referenced question, there are additional concerns. In particular, the following class:

class Line {
public:
    Line();
    ~Line();
    std::string* mString;
};

Line::Line() {
    mString = new std::string("foo_bar");
}

Line::~Line() {
    delete mString;
}

Is actually a lot more risky to use than the following one:

class Line {
public:
    Line();
    std::string mString;
};

Line::Line() {
    mString = "foo_bar";
    // note: there is a cleaner way to write this.
}

The reason is that std::string properly defines a copy constructor. Consider the following program:

int main ()
{
    Line l1;
    Line l2 = l1;
}

Using the original version, this program will likely crash, as it uses delete on the same string twice. Using the modified version, each Line instance will own its own string instance, each with its own memory and both will be released at the end of the program.

Other notes

Extensive use of RAII is considered a best practice in C++ because of all the reasons above. However, there is an additional benefit which is not immediately obvious. Basically, it's better than the sum of its parts. The whole mechanism composes. It scales.

If you use the Line class as a building block:

 class Table
 {
      Line borders[4];
 };

Then

 int main ()
 {
     Table table;
 }

allocates four std::string instances, four Line instances, one Table instance and all the string's contents and everything is freed automagically.

Difference between malloc and std::allocatorT::allocate

Your quote of std::allocator<T>::allocate:

Allocates n * sizeof(T) bytes of uninitialized storage by calling ::operator new(std::size_t) or ::operator new(std::size_t, std::align_val_t)

Does not refer to the new expression that creates and initializes objects. But to the operator new which is called by the c++ runtime to allocate memory in case of the new expression.

The default operator new might internally look like:

void* operator new(std::size_t sz) {
    void *ptr = std::malloc(sz);
    if (ptr)
        return ptr;
    else
        throw std::bad_alloc{};
}

But that's implementation-dependent, it could internally use any method provided by the OS to allocate memory. For embedded systems, it might even be a function that manages preallocated memory.

And does allocate calls malloc by its implementation or how does it requests OS for block of raw memory

That can't be said as it is implementation-dependent, but for the common implementations, you probably could assume that malloc and allocate internally use the same system calls, but if allocate das this directly or using in indirection over malloc is also implementation dependent.

Why would I write custom allocators for STL containers when I could just overwrite new and delete?

Answering the two questions in-order:

Should I write custom allocator_traits to interface my allocators for the various STL containers?

Yes, for easy manipulations. Pretty soon in the implementation, situations such as controlling memory overlaps would arise. For example, while stress-testing the implementation at full capacity of individual allocators and figuring out an algorithm for re-allocation. In this regard, you would need to specialize the allocator_traits class for the allocators rather than implement its member types from scratch using new and delete operators.

The reason allocator_traits is used is because it facilitates easy handling of certain rules that need to be respected. Such rules occur all across memory management. [Refer here for three such rules during allocator construction.]

What tangible benefit I would gain from having separate allocators for STL containers?

Absolute control of how the master allocator assigns, re-assigns, copies, moves, and destructs memory (with added controls over quantifying/enhancing performance). Pretty cool, isn't it! If the default std allocator is used, you would loose this control and rely on a (albeit very good) default implementation of memory management.

memory management & std::allocator

• Am I correct in assuming the allocator is responsible for the memory management from the items? (And making sure it is declared from stack/freestore/heap/whatever)

No you are not. The allocator is just sugar coating over new and delete and in general responsible of deciding where the memory will be allocated. The responsibility of calling allocate, deallocate, construct and destruct is to its users (which means here, std::vector). From your point of view, it'll be automatic, which is what matters here after all.

• What does the std::allocator do? - Does it declare from the stack, or from the heap?

std::allocator is mandated to allocate using ::operator new(size_t), thus it depends on the definition of the global new operator. Generally, this means the heap. The stack is for object with automatic storage duration.

• (follow up from previous question): if I copy an item declared in the stack to the datastructure is it still declared in the heap?

If you copy an item, then a copy is allocated where you copy it. Here it means copying an item from the stack to the heap. You then have two copies of the object, meaning that changes on one copy are not reflected on the other.

Beware though, that we are talking about the default copying mode, that is a shallow copy. If you copy an object, it'll get copied all fine; if you copy a pointer, only the pointer will be copied, not the data pointed to.

Why using new operator instead of std::vector?

You are right. Naked new is evil.

It's main purpose is now being the low-level plumbing underneath the high-level constructs. All the vectors and make_uniques and such end up calling new deep in the standard library.

Also, the low level parts predate the high level ones. Before smart pointers, new was the only option in many cases. In fact, std::make_unique was only introduced in C++14, so even C++11 needs to call new even when using unique_ptr for resource clean-up.

Why not to inherit from std::allocator

A lot of people are going to post in this thread that you should not inherit from std::allocator because it doesn't have a virtual destructor. They'll talk about polymorphism and slicing and deleting via pointer-to-base class, none of which are permitted by the allocator requirements as detailed in section 17.6.3.5 [allocator.requirements] of the standard. Until someone demonstrates that a class derived from std::allocator fails to meet one of those requirements, it's simple cargo cult mentality.

That said, there is little reason to derive from std::allocator in C++11. C++11's overhaul of allocators introduced the traits template std::allocator_traits to sit between an allocator and its users and provide reasonable defaults for many of the required features via template metaprogramming. A minimal allocator in C++11 can be as simple as:

template <typename T>
struct mallocator {
  using value_type = T;

  mallocator() = default;
  template <class U>
  mallocator(const mallocator<U>&) {}

  T* allocate(std::size_t n) {
    std::cout << "allocate(" << n << ") = ";
    if (n <= std::numeric_limits<std::size_t>::max() / sizeof(T)) {
      if (auto ptr = std::malloc(n * sizeof(T))) {
        return static_cast<T*>(ptr);
      }
    }
    throw std::bad_alloc();
  }
  void deallocate(T* ptr, std::size_t n) {
    std::free(ptr);
  }
};

template <typename T, typename U>
inline bool operator == (const mallocator<T>&, const mallocator<U>&) {
  return true;
}

template <typename T, typename U>
inline bool operator != (const mallocator<T>& a, const mallocator<U>& b) {
  return !(a == b);
}

EDIT: Proper use of std::allocator_traits isn't fully present in all standard libraries yet. For example, the sample allocator above doesn't work correctly with std::list when compiled with GCC 4.8.1 - the std::list code complains about missing members since it hasn't been updated yet.

---

Related Topics