Здравствуйте, shurik., Вы писали:

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

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

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

You will always get what you always got
  If you always do  what you always did

Здравствуйте, Vain, Вы писали:

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

По названию вполне можно так подумать. Собственно map мог бы зваться ordered_map, а unordered_map — map.

Здравствуйте, Alex Alexandrov, Вы писали:

AA>Здравствуйте, Кодт, Вы писали:

К>>Здравствуйте, ant_katcin, Вы писали:

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

К>>Однако, из этого не следует, что порядок обхода там поперечный С равным успехом мог быть восходящий и нисходящий (все три способа обхода требуют O(1) памяти и реализуются одинаково).

AA>O(1) ли? Вроде O(ln(N)), ибо как стек на высоту дерева нужен, нет?

Не обязательно, можно в узлах хранить паренты, тогда любой метод обхода будет О(1) по памяти.

день добрый

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

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

Здравствуйте, Vamp, Вы писали:

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

Здравствуйте, Vamp, Вы писали:

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

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

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

?

Здравствуйте, Vamp, Вы писали:

J>>если компаратор тот же, что и в мапе, и реализация без багов — да.
V>Надо же, никогда бы не подумал... Так в стандарте прописано?
А вы думали что он их в случайном порядке обходит?

Здравствуйте, 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:

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х

You will always get what you always got
  If you always do  what you always did

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

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

Здравствуйте, ant_katcin, Вы писали:

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

Однако, из этого не следует, что порядок обхода там поперечный С равным успехом мог быть восходящий и нисходящий (все три способа обхода требуют O(1) памяти и реализуются одинаково).

Здравствуйте, Vamp, Вы писали:

V>>А вы думали что он их в случайном порядке обходит?
V>А почему бы и нет?
Так это же лишнюю работу надо проделать контейнеру, чтоб в случайном то порядке )

Здравствуйте, igna, Вы писали:

V>>А вы думали что он их в случайном порядке обходит?
I>По названию вполне можно так подумать. Собственно map мог бы зваться ordered_map, а unordered_map — map.
И чем прикажете им отличаться?

Здравствуйте, Vain, Вы писали:
I>>По названию вполне можно так подумать. Собственно map мог бы зваться ordered_map, а unordered_map — map.
V>И чем прикажете им отличаться?
ну как в яве например, есть упорядоченная мапа на базе деревьев, есть неупорядоченная хэшмапа.

Здравствуйте, Vain, Вы писали:

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

Время поиска O(1) для unordered, O(log(n)) для ordered.

Здравствуйте, Alexander G, Вы писали:

AG>Здравствуйте, Vain, Вы писали:
V>>И чем прикажете им отличаться?
AG>Время поиска O(1) для unordered, O(log(n)) для ordered.
Каким образом, там же дерево?

Здравствуйте, Vain, Вы писали:

V>Каким образом, там же дерево?

С чего Вы взяли что в unordered дерево?

unordered_map или hash_map реализован через хеш-таблицу.

map применяется в случаях, когда нужен именно упорядоченный контейнер. Просто мапа — это unordered_map или hash_map.

Здравствуйте, Alexander G, Вы писали:

V>>Каким образом, там же дерево?
AG>С чего Вы взяли что в unordered дерево?
AG>unordered_map или hash_map реализован через хеш-таблицу.
зачем вы пытаетесь hash и map вместе связать?

Здравствуйте, Аноним, Вы писали:

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

Это не я, это в некоторых STL есть hash_map.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, ant_katcin, Вы писали:

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

К>Однако, из этого не следует, что порядок обхода там поперечный С равным успехом мог быть восходящий и нисходящий (все три способа обхода требуют O(1) памяти и реализуются одинаково).

O(1) ли? Вроде O(ln(N)), ибо как стек на высоту дерева нужен, нет?