Last updated：2026-10-12

STL empty base optimization EBO¶

0.Introduction¶

EBO is short for Empty Base Optimization.

This section starts from empty classes, moves into the STL internals, then testing, then implementing an EBO of our own, comparing performance, testing again, and finally summarizing.

1.Empty class¶

Define an empty class: a class with no member variables, no inheritance, and no data elements.

class Empty{
public:
    void print() {
        std::cout<<"I am Empty class"<<std::endl;
    }
};

Since it is empty, what is its sizeof?

std::cout<<sizeof(Empty)<<std::endl; //1

The result is 1. It is empty — so why isn't it 0?

Because an empty class can still be instantiated, and every instance has a unique address in memory. To achieve this, compilers usually implicitly add one byte to an empty class, so that after instantiation the empty class gets a unique address in memory. That is why the size above is 1.

Based on the answer above, you can probably derive another question: why should two different objects have different addresses?

Now here is an example:

class Empty{
public:
    void print() {
        std::cout<<"I am Empty class"<<std::endl;
    }
};
template < typename T >
bool isSame( T const & t1, T const & t2 )
{
    return &t1 == &t2;
}

Let's test it:

int main() {
    Empty a,b;
    assert(!isSame(a,b));  // 编译通过，a与b的地址不同

    Empty *p=new Empty;
    Empty *q=new Empty;
    assert(!isSame(p,q)); // 编译通过，a与b的地址不同
    return 0;
}

The above tested that two different objects have different addresses. Now consider the following scenario:

Empty a,b;
// 在同一地址具有两个对象将意味着在使用指针引用它们时将无法区分这两个对象。
Empty *p1=&a;
p1->print();

At this point you will find that if a's address were the same as b's address, then having two objects at the same address would mean the two objects could not be distinguished when referencing them with pointers. Hence two different objects have different addresses.

2.Empty base optimization¶

Now let's compare the following two usages. The first: a class contains another class as a member and obtains the contained class's functionality through it.

class notEbo  {
    int i;
    Empty e;
    // do other things
};

The other directly uses inheritance to obtain the base class's member functions and other functionality.

class ebo:public Empty {
    int i;
    // do other things
};

Next, a test:

std::cout<<sizeof(notEbo)<<std::endl;
std::cout<<sizeof(ebo)<<std::endl;

Output:

8 
4

In the first case, due to byte alignment, what originally occupied only 1 byte is padded to a multiple of 4, ending up as 8 bytes.

Comparing the two, we find that in the second case the base class's functionality is obtained through inheritance, and this optimization that produces no extra size is called EBO (Empty Base Optimization).

Next, let's return to the STL source code and see how it is used there!

3.The world of EBO in the STL¶

Containers such as deque, rb_tree, and list all depend on memory management; each of these containers contains the corresponding memory management and inherits the following classes via _xx_impl:

std::allocator<_Tp>
__gnu_cxx::bitmap_allocator<_Tp>
__gnu_cxx::bitmap_allocator<_Tp>
__gnu_cxx::__mt_alloc<_Tp>
__gnu_cxx::__pool_alloc<_Tp>
__gnu_cxx::malloc_allocator<_Tp>

So what does this have to do with our EBO?

In fact, the base classes listed above that get inherited are all memory-management EBO (empty base) classes.

Inside every container, the usage is to call each memory management's rebind<_Tp>::other.

For example, the red-black tree source structure:

typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
        rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
struct _Rb_tree_impl : public _Node_allocator
{
// do somethings
};

Next let's look at the source structure inside the memory-management classes listed above, taking allocator as an example:

template<typename _Tp>
class allocator: public __allocator_base<_Tp>
{
     template<typename _Tp1>
     struct rebind { typedef allocator<_Tp1> other; };
};

See it? The passed-in memory allocator is obtained via rebind<_Tp>::other — exactly the ones mentioned before.

std::allocator<_Tp>
__gnu_cxx::bitmap_allocator<_Tp>
__gnu_cxx::bitmap_allocator<_Tp>
__gnu_cxx::__mt_alloc<_Tp>
__gnu_cxx::__pool_alloc<_Tp>
__gnu_cxx::malloc_allocator<_Tp>

With all that understood, let's run a test:

void print() {
    cout<<sizeof(std::allocator<int>)<<" "<<sizeof(std::allocator<int>::rebind<int>::other)<<endl;
    cout<<sizeof(__gnu_cxx::bitmap_allocator<int>)<<" "<<sizeof(__gnu_cxx::bitmap_allocator<int>::rebind<int>::other)<<endl;
    cout<<sizeof(__gnu_cxx::new_allocator<int>)<<" "<<sizeof(__gnu_cxx::new_allocator<int>::rebind<int>::other)<<endl;
    cout<<sizeof(__gnu_cxx::__mt_alloc<int>)<<" "<<sizeof(__gnu_cxx::__mt_alloc<int>::rebind<int>::other)<<endl;
    cout<<sizeof(__gnu_cxx::__pool_alloc<int>)<<" "<<sizeof(__gnu_cxx::__pool_alloc<int>::rebind<int>::other)<<endl;
    cout<<sizeof(__gnu_cxx::malloc_allocator<int>)<<" "<<sizeof(__gnu_cxx::malloc_allocator<int>::rebind<int>::other)<<endl;
}

Let's test whether these sizeof values are 1. The tested output is as follows:

This shows that the memory-management implementations adopt inheritance and use the empty base optimization to keep the size occupied by containers as small as possible.

4.Using EBO, manually implement a simple memory allocation and deallocation¶

First define a class whose sizeof(class)=1 which, like the STL, uses allocate and deallocate internally for memory management.

class MyAllocator {
public:
    void *allocate(std::size_t size) {
        return std::malloc(size);
    }

    void deallocate(void *ptr) {
        std::free(ptr);
    }
};

The first way of memory management: embed a memory-management class

template<class T, class Allocator>
class MyContainerNotEBO {
    T *data_ = nullptr;
    std::size_t capacity_;
    Allocator allocator_;   // 嵌入一个MyAllocator
public:
    MyContainerNotEBO(std::size_t capacity)
            : capacity_(capacity), allocator_(), data_(nullptr) {
        std::cout << "alloc malloc" << std::endl;
        data_ = reinterpret_cast<T *>(allocator_.allocate(capacity * sizeof(T))); // 分配内存
    }

    ~MyContainerNotEBO() {
        std::cout << "MyContainerNotEBO free malloc" << std::endl;
        allocator_.deallocate(data_);
    }
};

The second way: use empty base optimization and obtain the memory-management functionality through inheritance

template<class T, class Allocator>
class MyContainerEBO
        : public Allocator {    // 继承一个EBO
    T *data_ = nullptr;
    std::size_t capacity_;
public:
    MyContainerEBO(std::size_t capacity)
            : capacity_(capacity), data_(nullptr) {
        std::cout << "alloc malloc" << std::endl;
        data_ = reinterpret_cast<T *>(this->allocate(capacity * sizeof(T)));
    }

    ~MyContainerEBO() {
        std::cout << "MyContainerEBO free malloc" << std::endl;
        this->deallocate(data_);
    }
};

Start testing:

int main() {
    MyContainerNotEBO<int, MyAllocator> notEbo = MyContainerNotEBO<int, MyAllocator>(0);
    std::cout << "Using Not EBO Test sizeof is " << sizeof(notEbo) << std::endl;
    MyContainerEBO<int, MyAllocator> ebo = MyContainerEBO<int, MyAllocator>(0);
    std::cout << "Using EBO Test sizeof is " << sizeof(ebo) << std::endl;

    return 0;
}

Test results:

alloc malloc
Using Not EBO Test sizeof is 24
alloc malloc
Using EBO Test sizeof is 16
MyContainerEBO free malloc
MyContainerNotEBO free malloc

We find that the EBO-based design is indeed much better than the embedded design. With that, this section is complete.