3

The documentation for both containers say that emplace() function constructs elements in place, but how do they know the location of the new element before the element is constructed?

For example, unordered_set places elements according to their hash value. How does the unordered_set know the hash value of the element before it is constructed?

I thought maybe the emplace function is meant to take rvalues, calculate the position of the new element and just move the object, but then insert() can do the same thing.

Sweeney Todd
  • 880
  • 1
  • 11
  • 25

1 Answers1

1

Its unspecified precisely how it works in the spec, but generally what will happen is that a datastructure-internal node object (rb-tree node or hash bucket node which contains the value) will be constructed from the arguments, and then that node will be linked into the data structure (into the the rb-tree for set, into the hash bucket for unordered_set), and in the event that the value is already present (so not added), the node object will be destroyed.

Chris Dodd
  • 119,907
  • 13
  • 134
  • 226
  • So the data structure basically keeps a pointer to the object, rather than holding the object like std::vector does, is that correct? If that's the case, I have another question: In case of a rebalancing the tree/rehashing, I know that the iterators are invalidated, but what about the actual pointers to the elements? do they stay valid? – Sweeney Todd May 05 '19 at 18:27
  • 1
    @SweeneyTodd If you have another question, ask it as another question - or in this case just read https://stackoverflow.com/q/6438086/560648 (yes they do) – Lightness Races in Orbit May 05 '19 at 18:32
  • 1
    The data structures (binary trees for set, open hash table for unordered_set) involve lots of pointers to interal node objects. Read up on them to understand more -- [rb-tree](https://en.wikipedia.org/wiki/Red%E2%80%93black_tree), [open hash table with separate chaining](https://en.wikipedia.org/wiki/Hash_table#Separate_chaining). Don't get confused by the fact that 'open addressing' means 'closed hashing'. – Chris Dodd May 05 '19 at 18:38
  • 1
    @SweeneyTodd: "In case of a rebalancing the tree/rehashing, I know that the iterators are invalidated" -- this is false; per the spec (23.2.4.1.9): "The insert and emplace members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements." – Chris Dodd May 05 '19 at 18:41
  • @ChrisDodd I think that's for **std::set**. For **unordered_set**, "_If rehashing occurs due to the insertion, all iterators are invalidated._" stated it [here](https://en.cppreference.com/w/cpp/container/unordered_set/insert) . – Sweeney Todd May 05 '19 at 19:04