порядок элементов в std::map
От: shurik.  
Дата: 26.06.08 12:34
Оценка:
день добрый

возник такой вопрос: если я буду бежать итератором по мапе у меня гарантировано ключи будут идти в порядке возрастания (компаратор std::less)?
Re: порядок элементов в std::map
От: jazzer Россия Skype: enerjazzer
Дата: 26.06.08 12:35
Оценка: 2 (1)
Здравствуйте, shurik., Вы писали:

S>день добрый


S>возник такой вопрос: если я буду бежать итератором по мапе у меня гарантировано ключи будут идти в порядке возрастания (компаратор std::less)?


если компаратор тот же, что и в мапе, и реализация без багов — да.
jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[2]: порядок элементов в std::map
От: Vamp Россия  
Дата: 26.06.08 13:06
Оценка:
J>если компаратор тот же, что и в мапе, и реализация без багов — да.
Надо же, никогда бы не подумал... Так в стандарте прописано?
Да здравствует мыло душистое и веревка пушистая.
Re[3]: порядок элементов в std::map
От: WolfHound  
Дата: 26.06.08 13:33
Оценка:
Здравствуйте, Vamp, Вы писали:

V>Надо же, никогда бы не подумал... Так в стандарте прописано?

Да.
... << RSDN@Home 1.2.0 alpha rev. 745>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[3]: порядок элементов в std::map
От: Bell Россия  
Дата: 26.06.08 13:37
Оценка:
Здравствуйте, Vamp, Вы писали:

J>>если компаратор тот же, что и в мапе, и реализация без багов — да.

V>Надо же, никогда бы не подумал... Так в стандарте прописано?
Если про порядок обхода — то гаратия есть, смоти 23.1.2/9.

ЗЫ
2 jazzer: не совсем понятно, какой именно компаратор ты имеешь ввиду, говоря

"если компаратор тот же, что и в мапе"

?
Любите книгу — источник знаний (с) М.Горький
Re[3]: порядок элементов в std::map
От: Vain Россия google.ru
Дата: 26.06.08 13:54
Оценка:
Здравствуйте, Vamp, Вы писали:

J>>если компаратор тот же, что и в мапе, и реализация без багов — да.

V>Надо же, никогда бы не подумал... Так в стандарте прописано?
А вы думали что он их в случайном порядке обходит?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[4]: порядок элементов в std::map
От: igna Россия  
Дата: 26.06.08 15:36
Оценка: +1
Здравствуйте, Vain, Вы писали:

V>А вы думали что он их в случайном порядке обходит?


По названию вполне можно так подумать. Собственно map мог бы зваться ordered_map, а unordered_map — map.
Re[3]: порядок элементов в std::map
От: ant_katcin Россия  
Дата: 27.06.08 05:59
Оценка:
Здравствуйте, Vamp, Вы писали:

J>>если компаратор тот же, что и в мапе, и реализация без багов — да.

V>Надо же, никогда бы не подумал... Так в стандарте прописано?

map — это обычное бинарное дерево (которое хитрым образом балансируется). соответственно все элементы упорядочены.
... << RSDN@Home 1.2.0 alpha 4 rev. 1091>>
Re[4]: порядок элементов в std::map
От: jazzer Россия Skype: enerjazzer
Дата: 27.06.08 13:06
Оценка:
Здравствуйте, 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:
template<class V, class ... T> extract_key(V&);

template<class ... T>
const typename std::set<T...>::key_type&
extract_key< std::set<T...> >( typename std::set<T...>::const_reference x ) { return x; }

template<class ... T>
const typename std::map<T...>::key_type&
extract_key< std::map<T...> >( typename std::map<T...>::const_reference x ) { return x.first; }

Это тоже, естественно, не компилил, так как нету под рукой компилятора с поддержкой С++0х

jazzer (Skype: enerjazzer) Ночная тема для RSDN
Автор: jazzer
Дата: 26.11.09

You will always get what you always got
  If you always do  what you always did
Re[4]: порядок элементов в std::map
От: Vamp Россия  
Дата: 27.06.08 13:34
Оценка:
V>А вы думали что он их в случайном порядке обходит?
А почему бы и нет?
Да здравствует мыло душистое и веревка пушистая.
Re[4]: порядок элементов в std::map
От: Vamp Россия  
Дата: 27.06.08 13:35
Оценка:
_>map — это обычное бинарное дерево (которое хитрым образом балансируется). соответственно все элементы упорядочены.
Вопрос же не в реализации, а в стандартизации.
Да здравствует мыло душистое и веревка пушистая.
Re[4]: порядок элементов в std::map
От: Кодт Россия  
Дата: 27.06.08 14:44
Оценка:
Здравствуйте, ant_katcin, Вы писали:

_>map — это обычное бинарное дерево (которое хитрым образом балансируется). соответственно все элементы упорядочены.


Однако, из этого не следует, что порядок обхода там поперечный С равным успехом мог быть восходящий и нисходящий (все три способа обхода требуют O(1) памяти и реализуются одинаково).
... << RSDN@Home 1.2.0 alpha rev. 655>>
Перекуём баги на фичи!
Re[5]: порядок элементов в std::map
От: Vain Россия google.ru
Дата: 29.06.08 12:49
Оценка:
Здравствуйте, Vamp, Вы писали:

V>>А вы думали что он их в случайном порядке обходит?

V>А почему бы и нет?
Так это же лишнюю работу надо проделать контейнеру, чтоб в случайном то порядке )
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[5]: порядок элементов в std::map
От: Vain Россия google.ru
Дата: 29.06.08 12:50
Оценка:
Здравствуйте, igna, Вы писали:

V>>А вы думали что он их в случайном порядке обходит?

I>По названию вполне можно так подумать. Собственно map мог бы зваться ordered_map, а unordered_map — map.
И чем прикажете им отличаться?
[In theory there is no difference between theory and practice. In
practice there is.]
[Даю очевидные ответы на риторические вопросы]
Re[6]: порядок элементов в std::map
От: dotidot Россия  
Дата: 29.06.08 16:36
Оценка:
Здравствуйте, Vain, Вы писали:
I>>По названию вполне можно так подумать. Собственно map мог бы зваться ordered_map, а unordered_map — map.
V>И чем прикажете им отличаться?
ну как в яве например, есть упорядоченная мапа на базе деревьев, есть неупорядоченная хэшмапа.
Re[6]: порядок элементов в std::map
От: Alexander G Украина  
Дата: 29.06.08 21:34
Оценка:
Здравствуйте, Vain, Вы писали:

V>И чем прикажете им отличаться?


Время поиска O(1) для unordered, O(log(n)) для ordered.
Русский военный корабль идёт ко дну!
Re[7]: порядок элементов в std::map
От: Vain Россия google.ru
Дата: 30.06.08 07:41
Оценка:
Здравствуйте, 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.]
[Даю очевидные ответы на риторические вопросы]
Re[8]: порядок элементов в std::map
От: Alexander G Украина  
Дата: 30.06.08 08:05
Оценка:
Здравствуйте, 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 вместе связать?
Re[10]: порядок элементов в std::map
От: Alexander G Украина  
Дата: 30.06.08 15:51
Оценка:
Здравствуйте, Аноним, Вы писали:

А>зачем вы пытаетесь hash и map вместе связать?


Это не я, это в некоторых STL есть hash_map.
Русский военный корабль идёт ко дну!
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.