Элементы в std :: map всегда остаются по одному адресу? - PullRequest
Новая
       41

Элементы в std :: map всегда остаются по одному адресу?

0 голосов
/ 27 января 2019

Возьмем следующую простую программу: 

struct Foo
{
    int x;
    int y;
    int z;
    string s;
};

int main()
{
    Foo f1 = { 42,21,11, "Hello world" };
    std::map<int, Foo> foomap;

    foomap[400] = f1;
    Foo* ptr = &foomap[400]; // cache a pointer to the element we just inserted.

    cout << ptr->x << " " << ptr->y << " " << ptr->z << " " << ptr->s << std::endl;

    // fill the map up with a bunch of other random items at random indices   
    for (int x = 0; x < 10000; x++)
    {
        int i = rand();
        Foo f = { rand(), rand(), rand(), "Another string" };

        if (foomap.find(i) == foomap.end())
        {
            foomap[i] = f;
        }
    }

    Foo* ptr2 = &foomap[400];

    cout << "f1 insert location has " << ((ptr == ptr2) ? "not changed" : "changed") << std::endl;
    cout << ptr->x << " " << ptr->y << " " << ptr->z << " " << ptr->s << std::endl;

    return 0;
}

Таким образом, вышеприведенная программа кэширует указатель на элемент на карте.Затем добавляет на карту намного больше элементов, а затем проверяет, изменился ли первый вставленный элемент.

Я был несколько удивлен, когда запустил его.Кэшированный указатель остается неизменным: 

42 21 11 Hello world
f1 insert location has not changed
42 21 11 Hello world

Я бы предположил, что по мере роста карты по отношению к количеству элементов в ней реализация может перемещать элементы - точно так же, как это делает std :: vector.

Итак, мой вопрос таков: гарантированно, что элементы, вставленные в карту, находятся по одному и тому же адресу, если она не удалена с карты или не заменена?Или это конкретная реализация?

1 Ответ

0 голосов
/ 27 января 2019

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

26.2.6 Ассоциативные контейнеры [associative.reqmts]
9Элементы insert и emplace не должны влиять на действительность итераторов и ссылок на контейнер, а элементы erase должны делать недействительными только итераторы и ссылки на стертые элементы.

...