Здравствуйте, shurik., Вы писали:
S>день добрый
S>возник такой вопрос: если я буду бежать итератором по мапе у меня гарантировано ключи будут идти в порядке возрастания (компаратор std::less)?
если компаратор тот же, что и в мапе, и реализация без багов — да.
Здравствуйте, Vamp, Вы писали:
J>>если компаратор тот же, что и в мапе, и реализация без багов — да. V>Надо же, никогда бы не подумал... Так в стандарте прописано?
Если про порядок обхода — то гаратия есть, смоти 23.1.2/9.
ЗЫ
2 jazzer: не совсем понятно, какой именно компаратор ты имеешь ввиду, говоря
Здравствуйте, Vamp, Вы писали:
J>>если компаратор тот же, что и в мапе, и реализация без багов — да. V>Надо же, никогда бы не подумал... Так в стандарте прописано?
А вы думали что он их в случайном порядке обходит?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vamp, Вы писали:
J>>если компаратор тот же, что и в мапе, и реализация без багов — да. V>Надо же, никогда бы не подумал... Так в стандарте прописано?
map — это обычное бинарное дерево (которое хитрым образом балансируется). соответственно все элементы упорядочены.
Здравствуйте, Bell, Вы писали:
B>2 jazzer: не совсем понятно, какой именно компаратор ты имеешь ввиду, говоря
"если компаратор тот же, что и в мапе"
?
В стандартных контейнерах определен тип key_compare и функция key_comp(), возвращающая внутренний компаратор контейнера.
И я имею в виду, что при проходе по такому контейнеру получится последовательность, упорядоченная этим самым компаратором, а для других компараторов ничего сказать нельзя.
Т.е. вот простейший тест на правильность реализации std::set (псведокод, в смысле, не компилил):
template<class C>
bool check_assoc_container_validity(const C& c)
{
typedef typename C::const_iterator It;
for ( It it = c.begin(), end = c.end(); it != end; ++it )
{
for ( It it2 = std::advance( it ); it2 != end; ++it2 )
{
if ( ! c.key_comp()( *it, *it2 ) )
return false;
}
}
return true;
}
так она будет работать только для контейнера, в котором лежат ключи (сет), чтоб работало для любого, надо написать
if ( ! c.key_comp()( extract_key<C>(*it), extract_key<C>(*it2) ) )
где extract_key — функция, которая для сета будет просто возвращать свой аргумент, а для мапа — .first:
_>map — это обычное бинарное дерево (которое хитрым образом балансируется). соответственно все элементы упорядочены.
Вопрос же не в реализации, а в стандартизации.
Здравствуйте, ant_katcin, Вы писали:
_>map — это обычное бинарное дерево (которое хитрым образом балансируется). соответственно все элементы упорядочены.
Однако, из этого не следует, что порядок обхода там поперечный С равным успехом мог быть восходящий и нисходящий (все три способа обхода требуют O(1) памяти и реализуются одинаково).
Здравствуйте, Vamp, Вы писали:
V>>А вы думали что он их в случайном порядке обходит? V>А почему бы и нет?
Так это же лишнюю работу надо проделать контейнеру, чтоб в случайном то порядке )
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, igna, Вы писали:
V>>А вы думали что он их в случайном порядке обходит? I>По названию вполне можно так подумать. Собственно map мог бы зваться ordered_map, а unordered_map — map.
И чем прикажете им отличаться?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали: I>>По названию вполне можно так подумать. Собственно map мог бы зваться ordered_map, а unordered_map — map. V>И чем прикажете им отличаться?
ну как в яве например, есть упорядоченная мапа на базе деревьев, есть неупорядоченная хэшмапа.
Здравствуйте, Alexander G, Вы писали:
AG>Здравствуйте, Vain, Вы писали: V>>И чем прикажете им отличаться? AG>Время поиска O(1) для unordered, O(log(n)) для ordered.
Каким образом, там же дерево?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Здравствуйте, Vain, Вы писали:
V>Каким образом, там же дерево?
С чего Вы взяли что в unordered дерево?
unordered_map или hash_map реализован через хеш-таблицу.
map применяется в случаях, когда нужен именно упорядоченный контейнер. Просто мапа — это unordered_map или hash_map.
Русский военный корабль идёт ко дну!
Re[9]: порядок элементов в std::map
От:
Аноним
Дата:
30.06.08 14:32
Оценка:
Здравствуйте, Alexander G, Вы писали:
V>>Каким образом, там же дерево? AG>С чего Вы взяли что в unordered дерево? AG>unordered_map или hash_map реализован через хеш-таблицу.
зачем вы пытаетесь hash и map вместе связать?