StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>No. It's not possible to implement <code>set</code> in such a way that you can do this.</p> <p>If you implement <code>set</code> in such a way that elements are stored in a single array, then when you add more elements, that array will inevitably need to be reallocated at some point. At that time, any references to existing elements will be invalidated.</p> <p>One of features of <code>set</code> is that it <em>guarantees</em> that references to elements will never be invalidated if you add (or remove) other elements. As stated in [associative.reqmts]:</p> <blockquote> <p>The <code>insert</code> and <code>emplace</code> members shall not affect the validity of iterators and references to the container, and the <code>erase</code> members shall invalidate only iterators and references to the erased elements.</p> </blockquote> <p>So it's <em>impossible</em> to implement <code>set</code> in such a way that all of the elements of the set are stored in a single array.</p> <p>Note that this has nothing to do with the efficiency requirements such as O(log n) insert/delete/lookup (if you squint really hard and allow for amortized O(log n) insertion time, at least), or maintaining sorted order, or anything like that. If it was just these, they could easily be handled with a data structure on top of the underlying elements, and the elements themselves could be stored in an array. It also doesn't even have anything to do with guarantees about <em>iterator</em> invalidation, since iterators are abstract.</p> <p>No, the only thing holding you back is the reference invalidation requirement.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload