Имеет ли карта STL всегда одинаковое упорядочение при итерации с начала() до конца()?

Как мне кажется, из моего простого тестирования, но мне интересно, гарантировано ли это?Имеет ли карта STL всегда одинаковое упорядочение при итерации с начала() до конца()?

Есть ли условия, при которых заказ не будет гарантирован?

Редактировать: Случай, который меня особенно интересует, заключается в том, что если я заполню карту большим количеством записей, будет ли порядок итератора одинаковым для нескольких прогонов моего исполняемого файла? Что делать, если записи вставляются в другом порядке?

источник

2009-06-11 Jamie Cook

Если вам нужен гарантированный порядок элементов, разве вы не должны использовать структуру List, подобную структуре? Карта по определению не имеет порядка, так как значения размещаются в местах, определенных путем хэширования их ключей. – Gishu

Обратите внимание на разницу между порядком и порядком. Список, вектор и dequeue представляют собой контейнеры последовательностей. Набор и карта - это упорядоченные контейнеры. – Flame

Да, он поддерживает внутренний порядок, поэтому итерация по набору, который не меняется, всегда должен быть одинаковым. От here:

Внутренне элементы в карте сортируются от низшего к высшему ключа значение после определенного строгого слабого критерия упорядочения набора на строительства.

источник

2009-06-11 03:34:50

В glibc это красно-черное дерево. Хотя строгий заказ не входит в спецификацию STL, это стандарт де-факто. –

@Jeffamaphone И если ваш ключ является указателем на объект, вы можете получить какой-либо порядок в нескольких прогонах вашей программы .... хорошо, что объясняет, что тогда это не так :) –

@Jamie Cook: Технически, указатели aren 't действительные ключи (по крайней мере, с помощью стандартного std :: less compator), поскольку для указателей нет оператора

Будет ли карта STL давать тот же порядок с началом/концом, если он не изменился? Да. Однако, если вы измените карту, не зависните от того, что порядок остался прежним.

источник

2009-06-11 03:32:24 JaredPar

... но упорядочение неизмененных элементов остается неизменным - любые вставки или удаления будут отражаться в соответствующем месте в последовательности для определенного отношения упорядочения. Иными словами, изменения на карте изменят порядок итераций полностью предсказуемым образом. –

-2

В том же наборе данных при той же реализации STL, да. Насколько мне известно, не может быть одинаковым в разных реализациях.

источник

2009-06-11 03:32:31

Гарантируется, что он будет одинаковым во всей реализации, если компаратор обеспечивает действительный строгий слабый порядок - в противном случае все ставки отключены! –

Значит, это гарантировано, если это не так? :) –

std::map является отсортирован контейнера, так что, да, порядок гарантируется (такой же, как упорядочении вы используете неявно или явно в конструкторе). Do не рассчитывать на это для популярного (хотя еще не-станарда) hashmap, хотя - во многих случаях он имеет очень много преимуществ по цене std::map, но не предсказуемый порядок итераций!

источник

2009-06-11 03:37:36

В C++ 0x карта/набор, основанный на хеше, называется unordered_map/unordered_set. Совершенно ясно, что нас не заказывают. – Flame

станд :: карта отсортированный коллекция
и вы должны определить, меньше, чем оператор
представить м является отображением типа Т:

assert(m.size() > 1); 
for (std::map<T>::const_iterator i = m.begin(); i != m.end(); ++i) { 
    std::map<T>::const_iterator j = i + 1; 
    while (j != m.end()) { 
     assert(*i < *j); 
     ++j; 
    } 
}

источник

2009-06-11 04:41:12

Имеет ли карта STL всегда одинаковое упорядочение при итерации с начала() до конца()?

ответ

Смежные вопросы