изменит ли он адрес значения существующего ключа при вставке новых ключей?

В моем коде будет вставка или удаление в std::map, но не изменение значения существующего ключа. изменит ли он адрес значения существующего ключа при вставке/удалении новых ключей?

int main()
{

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

    return 0;
}

и результат всегда один и тот же... Так что на старые ключи это просто не повлияет？ Кстати, а как насчет unordered_map?


c++ dictionary std stdmap unordered
person scirocc    schedule 13.05.2020    source источник
comment
Я предполагаю, что это связано с реализацией, которая не определена в стандарте. На сайте cppreference указано, что Maps are usually implemented as red-black trees, что объясняет, как правило, адреса не должны меняться.   -  person Damien    schedule 13.05.2020
comment
Я не уверен насчет адреса значения ключа, но, возможно, это поможет вам узнать, что итераторы к объектам на карте остаются действительными, когда другие элементы вставляются/стираются. См. этот ответ.   -  person StefanKssmr    schedule 13.05.2020
comment
@StefanKssmr Спасибо за ваши советы, это очень полезно!   -  person scirocc    schedule 13.05.2020
comment
@ Дэмиен, спасибо, чувак!   -  person scirocc    schedule 13.05.2020

Ответы (2)


arrow_upward
3
arrow_downward

Адрес существующих элементов не изменяется при вставке или удалении других элементов. Другими словами, ссылки на элементы не становятся недействительными, если только этот конкретный элемент не удален.

Это верно для всех контейнеров на основе узлов, которые включают ассоциативные контейнеры (карта, набор, неупорядоченные варианты, их несколько вариантов) и связанные списки. Это неверно для дека, вектора или строки на основе массива.

Итераторы неупорядоченных ассоциативных контейнеров могут стать недействительными при вставке в случае повторного хеширования; это не влияет на адрес.

person eerorika    schedule 13.05.2020
comment
из-за этого правила. Если я запускаю поток, выполняющий вставку, а в другом потоке я делаю std::map.find(), могу ли я получить правильный итератор? Или во время процесса поиска мне просто нужно добавить блокировку и разблокировать когда поиск закончится, я получу правильный итератор. - person scirocc; 13.05.2020
comment
@scirocc Если вы изменяете контейнер (т.е. вставляете), вы должны синхронизировать доступ (т.е. находить). - person eerorika; 13.05.2020

arrow_upward
2
arrow_downward

На основе std::map<Key,T,Compare,Allocator>::operator[] ни итераторы, ни ссылки не становятся недействительными:

[…]Возвращает ссылку на значение, сопоставленное с ключом, эквивалентным ключу, выполняя вставку, если такой ключ еще не существует.[…]Итераторы или ссылки не становятся недействительными.

Для std::unordered_map<Key,T,Hash,KeyEqual,Allocator>::operator[] итераторы могут стать недействительными, но не ссылки:

Возвращает ссылку на значение, сопоставленное с ключом, эквивалентным ключу, выполняя вставку, если такой ключ еще не существует. [...] Если вставка происходит и приводит к перефразированию контейнера, все итераторы становятся недействительными. В противном случае итераторы не затрагиваются. Ссылки не аннулируются.

person t.niese    schedule 13.05.2020