multiset

[Christopher Pisz]

Reading on multiset.

Am I to understand correctly that a multiset doesn't have a key/value,
but in fact just has "elements", which are the themselves the keys?

So then, a multiset is just like a vector, but sorted for fast finds?

Are there any other differences?

When does an iterator to a multiset become invalid?

 

[Victor Bazarov]

Reading on multiset.

Am I to understand correctly that a multiset doesn't have a key/value,
but in fact just has "elements", which are the themselves the keys?

So then, a multiset is just like a vector, but sorted for fast finds?

Are there any other differences?

It's more expensive from the memory standpoint. The iterators are
bidirectional, not random-access. Values stored in the set are
immutable. To change a value you need to remove the old one and
reinsert the new one. And the set's iterators are basically both const.

When does an iterator to a multiset become invalid?

Like with other standard associative containers, when the object to
which iterator points, is deleted from the container. IIRC.

V

 

[MikeWhy]

Reading on multiset.

Am I to understand correctly that a multiset doesn't have a key/value, but
in fact just has "elements", which are the themselves the keys?

So then, a multiset is just like a vector, but sorted for fast finds?

Are there any other differences?

When does an iterator to a multiset become invalid?

Multiset is a very close relative of multimap. Both are built on red-black
tree, a balanced binary tree. Insertion and deletion from the rbtree
invalidates iterators.

 

[Jorgen Grahn]

Multiset is a very close relative of multimap. Both are built on red-black
tree, a balanced binary tree. Insertion and deletion from the rbtree
invalidates iterators.

That doesn't match what the old STL docs say; do you have any
references?

Multiset has the important property that inserting a new element
into a multiset does not invalidate iterators that point to
existing elements. Erasing an element from a multiset also does
not invalidate any iterators, except, of course, for iterators
that actually point to the element that is being erased.

-- http://www.sgi.com/tech/stl/multiset.html

/Jorgen

 

[MikeWhy]

That doesn't match what the old STL docs say; do you have any
references?

Multiset has the important property that inserting a new element
into a multiset does not invalidate iterators that point to
existing elements. Erasing an element from a multiset also does
not invalidate any iterators, except, of course, for iterators
that actually point to the element that is being erased.

-- http://www.sgi.com/tech/stl/multiset.html

Thanks for the correction. That's almost certainly still correct, even
without looking up a reference. I had in mind concurrency issues with reads
while the list is being modified. This is a different problem altogether:
ensuring that no iterators can be referencing the element being erased.

 

[Juha Nieminen]

Thanks for the correction. That's almost certainly still correct, even
without looking up a reference. I had in mind concurrency issues with reads
while the list is being modified. This is a different problem altogether:
ensuring that no iterators can be referencing the element being erased.

Traversing the tree in one thread while another is modifiying it will certainly
cause malfunction, but I don't think dereferencing an iterator (ie. reading the
element pointed by that iterator) would misbehave even if another thread is modifying
the tree at the same time (except in the case where the other thread is removing
said element, of course). set/map nodes do not move in RAM when new elements are
inserted or removed from it; ie. their addresses stay the same and hence iterators
to them will work ok as long as they exist.

Same goes for std::list. std::deque is a bit more complicated.