Why Does the C++ Stl Not Provide Any "Tree" Containers

Why does the C++ STL not provide any tree containers?

There are two reasons you could want to use a tree:

You want to mirror the problem using a tree-like structure:

For this we have boost graph library

Or you want a container that has tree like access characteristics
For this we have

• std::map (and std::multimap)
• std::set (and std::multiset)

Basically the characteristics of these two containers is such that they practically have to be implemented using trees (though this is not actually a requirement).

See also this question:
C tree Implementation

C++ STL: Why allocators don't increase memory footprint of containers?

Your allocator is not being used.

By default, std::set receives std::allocator<int>, but it needs to allocate some kind of nodes, not ints. It uses std::allocator_traits::rebind to get a different allocator for its internal node type.

Pre-C++20 std::allocator has a rebind member type, which you inherit, and which std::allocator_traits::rebind finds. That rebind points to std::allocator, so that's what you get.

Starting from C++20, there's no rebind in std::allocator, so std::allocator_traits::rebind falls back to directly modifying the first template parameter of your allocator, and since it's not a template, you get a compilation error.

A possible solution is to make your allocator a template, and to provide your own rebind (which can be malformed, then the template parameter will be replaced automatically):

template <typename T>
struct MyAllocator : public std::allocator<T>
{
    char dummy[1024];
    struct rebind {}; // Malformed `rebind` to hide the inherited one, if any.
};

Then 1072 is printed for me.

Why there is no supported iterators for some STL containers (Stack, Queue, Priority Queue)?

The three are not classic containers, but rather container adaptors. They do not need to support the iteration. A quote from the "C++ Programming Language" book:

Container adaptors provide specialized access to underlying
containers.

They are:

intended to be used only through their specialized interfaces. In particular, the STL
container adaptors do not offer direct access to their underlying container. They do not offer iterators or subscripting.

C++ STL - Containers implementation

Is it a Pointer to an object, or the object itself, that is constructed in the nodes allocated memory?

In Boost.Intrusive, the element type of the container is the node. In order to make it compatible with the container, you have to modify your element type so that it includes data members required by the container - either by inheriting from a base class (e.g. list_base_hook, see here) or by adding a special data member (e.g. list_member_hook). This is why they are called intrusive containers. In comparison, the standard containers do not require you to modify your classes and instead wrap them in container nodes, if necessary.

When the node in the std::list holds an object and the intrusive container holds a node in their object, how does that lead to better locality?

In std::list each container node (which contains your element) is allocated separately, in its own dynamic memory allocation. The node contains pointers to the previous and the next elements in the list. Since each node is allocated separately, their locality depends on the memory allocator used, but generally you can assume that different nodes are located at arbitrary locations in memory, possibly distant and not in order. Additionally, traversing the list requires to dereference a pointer to the next element on each iteration, which typically hampers memory caching algorithms in the CPU.

In boost::intrusive::list, the container does not impose any memory allocation strategy on the user. It is possible to have a single memory region for multiple or all elements of the intrusive container, which makes them more closely packed and possibly ordered in memory. This requires more work from the user, of course. List iteration still requires pointer dereferencing and hurts prefetcher in the CPU, but if container elements are closely packed, chances are high that each next node will be in a cache line that was already fetched from memory for the previous element(s).

Another thing to note is that intrusive containers are much more useful when you need to store element in multiple containers at once. With standard containers, you have to use pointers to refer to the element from each container. For example:

// Element type
class Foo {};

std::list< std::shared_ptr< Foo > > list;
std::map< int, std::shared_ptr< Foo > > map;

In this example, you have at least one allocation for a Foo object, one allocation for the list node and one allocation for the map node. Each of these allocations is arbitrarily located in memory. Accessing the element either via list or via map requires an additional level of indirection.

With intrusive containers, you can reduce this to just one allocation and no extra indirection:

// List hook
typedef boost::intrusive::list_base_hook<> FooListHook;
// Map/set hook
typedef boost::intrusive::set_base_hook<
    boost::intrusive::optimize_size< true >
> FooSetHook;

// Node type
class Foo :
    public FooListHook,
    public FooSetHook
{
    ...
};

boost::intrusive::list< Foo, boost::intrusive::base_hook< FooListHook > > list;
boost::intrusive::set< Foo, boost::intrusive::base_hook< FooSetHook >, ... > set;

In this case, neither list nor set does memory allocation of their own, all the necessary data is already within the Foo node, which you allocate yourself. Iterating through either of the containers automatically fetches both hooks and Foo contents (at least partially) into cache, which makes memory accesses faster. There are other benefits to this approach as well, like the ability to switch between the two containers' iterators without expensive element lookup.

Is there still a need to provide default constructors to use STL containers?

This quote is from the C++ Programming Language, Special edition , 2005 by Bjarne Stroustrup in section 16.3.4:

If a type does not have a default constructor, it is not possible to create a vector with elements of that type, without explicitly providing the value of each element.

So it was indeed a standard requirement. It was also required that (section 17.1.4) :

To be an element of a container, an object must be of a type that allows the container implementation to copy it. The container may copy it using a copy constructor or an assignment; in either case the result of the copy must be an equivalent object.

So yes, there were "official" constructor requirementsand the library implementation were supposed to be interchangeable and not add other requirements. (Already in the very first proposal for STL in 1995, the authors tried as much as possible to clearly indicate specifications and narrow down the implementation dependent flexibility.)

You therefore had to provide a default constructor in the case where you declared other constructors:

If a user has declared a default constructor, that one will be used; otherwise, the compiler will try to generate one if needed and if the user hasn't declared other constructors.

Nowadays, this requirement is relaxed. Since C++11:

The requirements that are imposed on the elements depend on the actual operations performed on the container.

So you can define a vector for a class without default constructor, if it doesn't make sense. This for example perfectly works (online demo):

class MyClass {
public: 
    MyClass(int x) {}
};
int main() {
    vector<MyClass> v; 
    MyClass test{1}; 
    v.push_back(test);
}

But it works only as long as you don't use any operation that would need the default constructor. For instance v.resize(6); would fail to compile.

Data structures equivalents of STL containers

Concering the C++ standard library containers, the standard itself tries not to say too much about implementation. However, the very specific constraints on complexity of insertion, removal, look-up, range insertion and so on, mean that most implementations use the same types of data structures for the containers. Concerning some of your examples:

• std::list : doubly linked list
• std::set, std::multiset, std::map, std::multimap: self-balancing
  binary trees, typically red-blacktrees.
• hash_*: C++11 provides unordered_set, unordered_map and multi
  siblings. These are hash tables.
• bitset: fixed-size array

I believe the STL follows these implementations.

---

Related Topics