Search code examples
c++setstdset

Does std::set store objects contiguously in memory?

Does std::set store objects in contiguous memory like std::vector?

I haven't been able to find this on the web, cppreference doesn't mention details on memory allocation. But I can't see why it couldn't use contiguous memory, hence my question.

Solution

  • Does std::set store objects in contiguous memory like std::vector?

    There is no guarantee that it does. Also in practice, it cannot because of the requirements of the container. Therefore no, it does not store objects in contiguous memory.

    I can't see why it couldn't use contiguous memory

    References to elements of the set must remain valid upon insertion to it as well as erasure (except for references to the erased element). This requirement is incompatible with contiguous memory.

    As far as I know, a balanced search tree is the only data structure that can implement std::set.