22

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.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
mfnx
  • 2,894
  • 1
  • 12
  • 28
  • 6
    Read `set::insert` requirements : https://en.cppreference.com/w/cpp/container/set/insert _"...No iterators or references are invalidated...."_ so it can't reallocate when it needs to expand like a `std::vector` does. – Richard Critten Jan 01 '20 at 19:02
  • Performance: you need to measure (depends on your hashing function)for your use-case see: https://channel9.msdn.com/Events/Build/2014/2-661 from __45:48__ – Richard Critten Jan 01 '20 at 19:06
  • 4
    See also [boost::flat_set](https://www.boost.org/doc/libs/1_72_0/doc/html/container/non_standard_containers.html#container.non_standard_containers.flat_xxx). – Caleth Jan 02 '20 at 09:33
  • 1
    Do you mean 'contiguous' as in "as the set is iterated, objects are stored in contiguous memory locations", or as in "all the objects are stored in one big chunk of memory (but in arbitrary order)"? – Pablo H Jan 02 '20 at 13:02
  • @PabloH I mean, just like std::vector. – mfnx Jan 02 '20 at 13:49
  • 1
    Generally, when you find yourself asking "is container A the same as container B", the answer is "no", otherwise there would only be container A (because what would be the purpose in having container B?). This doesn't apply to container _adaptors_ of course, but `std::set` is not one of those things, which is the key here. – Lightness Races in Orbit Jan 02 '20 at 18:34
  • @LightnessRacesBY-SA3.0 I see what you mean. Not sure if my question is equivalent to "is A the same as B?" though. – mfnx Jan 02 '20 at 19:11
  • @mfnx granted it's 50% ;) – Lightness Races in Orbit Jan 03 '20 at 12:36

2 Answers2

28

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.

eerorika
  • 232,697
  • 12
  • 197
  • 326
  • 1
    It could carve space for tree nodes out of large contiguous chunks, in case that's what the OP meant. (But no iterator invalidation rules out `insert` copying all the nodes into a new larger block to limit it to only *one* block, in case in-place realloc fails or (typical for C++) the allocator doesn't support such a realloc.) – Peter Cordes Jan 02 '20 at 12:28
15

It isnt excluded explicitly, though certain constraints for std::set make it impossible to use contiguous memory.

For example, set::insert has logarithmic complexity while vector::insert requires linear complexity to shuffle its entries. Also set::insert does not invalidate iterators. Both requirements cannot be realized with continguous memory.

Pete Becker
  • 74,985
  • 8
  • 76
  • 165
463035818_is_not_an_ai
  • 109,796
  • 11
  • 89
  • 185