will it change the address of a existed key's value when inserting new keys?

Question

In my code,there will be inserting or deleting in a std::map,but not change the value of a existed key. will it change the address of a existed key's value when inserting/deleting new keys ?

int main()
{

    std::map<int,int> m;
    for(int i(0);i<100000;i++){
        m[i];
        std::cout<< &m[0]<<std::endl;
    }

    return 0;
}

and the result is always the same...So it just won't have influence on old keys？ By the way ,what about the unordered_map?

I guess it it related to the implementation, which is not defined in the standard. *cppreference* site details that `Maps are usually implemented as red-black trees`, which explains that *generally*, adresses should not change. — Damien, May 13 '20 at 09:52
I am not sure about the address of a key's value, but maybe it helps you to know that iterators to the objects in the map remain valid when other elements are inserted/erased. See this [answer](https://stackoverflow.com/a/54004916/8359552). — StefanKssmr, May 13 '20 at 09:59

eerorika · Accepted Answer · 2020-05-13T10:30:09.953

4

The address of existing elements do not change when other elements are inserted or removed. In other words, references to the elements are not invalidated unless that particular element is erased.

This is true for all node based containers which include the associative containers (map, set, unordered variants, multi variants of them) and linked lists. It is not true for the array based deque, vector nor string.

Unordered associative containers may have their iterators invalidated upon insertion in case of rehashing; this does not affect the address.

edited May 13 '20 at 10:30

answered May 13 '20 at 10:15

eerorika

232,697
12
197
326

due to that rule.If I start a thread doing inserting,and in another thread I do std::map.find(),can I get the correct iterator?Or during the finding process I just need to add a lock,and unlock it when the finding is over,then I will get the correct iterator. – scirocc May 13 '20 at 10:29
@scirocc If you modify the container (i.e. insert), then you must synchronise the access (i.e. find). – eerorika May 13 '20 at 10:31

score 2 · Answer 2 · answered May 13 '20 at 10:17

Based on std::map<Key,T,Compare,Allocator>::operator[] neither the iterators nor the references become invalid:

[…]Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist.[…]No iterators or references are invalidated.

For std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::operator[] the iterators may become invalid, but not the references:

Returns a reference to the value that is mapped to a key equivalent to key, performing an insertion if such key does not already exist. [...] If an insertion occurs and results in a rehashing of the container, all iterators are invalidated. Otherwise iterators are not affected. References are not invalidated.

will it change the address of a existed key's value when inserting new keys?

2 Answers2