Привет All

map<int, CMayClass> m_map;
В проге использую map.
Мне нужно, зная порядковsй номер в map-е
получить CMayClass?

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

А>map<int, CMayClass> m_map;
А>В проге использую map.
А>Мне нужно, зная порядковsй номер в map-е
А>получить CMayClass?

1. Использовать std::advance, которая сводится к многократному инкременту итератора
2. Перепроектировать свою программу: мап не для этого предназначен.

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

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

А>>map<int, CMayClass> m_map;
А>>В проге использую map.
А>>Мне нужно, зная порядковsй номер в map-е
А>>получить CMayClass?

К>1. Использовать std::advance, которая сводится к многократному инкременту итератора
К>2. Перепроектировать свою программу: мап не для этого предназначен.

А для чего предназначен map? Вот такой вот философско-теоретический вопрос...

Мне почему-то кажется что конструкция типа
template dictionary<K,V> которая эффективно является имплементацией array<pair<K,V>> и hash_table<K, unsigned int> ( или avltree<K, unsigned int>)
гораздо полезнее чем голый stl::map.

Примерно в 90% случаях лично я использую map как symbol table.
Т.е. индекс элемента в dictionary::array<pair<K,V>> есть
целочисленный symbol по которому можно легко достать и ключ (имя) и значение.
Соответсвенно можно легко найти и индекс и значение по ключу.

Да, имплементация map как hash_table<K, unsigned int> и array<pair<K,V>> имеет при поиске по ключу небольшой overhead в виде
одного дополнительного перехода по индексу, но зато куча дополнительных удобств.

И foreach для std::map вельми тоскливая процедура...

Андрей.

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

CS>А для чего предназначен map? Вот такой вот философско-теоретический вопрос...

CS>Мне почему-то кажется что конструкция типа
CS>template dictionary<K,V> которая эффективно является имплементацией array<pair<K,V>> и hash_table<K, unsigned int> ( или avltree<K, unsigned int>)
CS>гораздо полезнее чем голый stl::map.

наверное, vector<pair<const K, V> >, а не array?

CS>Примерно в 90% случаях лично я использую map как symbol table.
CS>Т.е. индекс элемента в dictionary::array<pair<K,V>> есть
CS>целочисленный symbol по которому можно легко достать и ключ (имя) и значение.
CS>Соответсвенно можно легко найти и индекс и значение по ключу.

CS>Да, имплементация map как hash_table<K, unsigned int> и array<pair<K,V>> имеет при поиске по ключу небольшой overhead в виде
CS>одного дополнительного перехода по индексу, но зато куча дополнительных удобств.

CS>И foreach для std::map вельми тоскливая процедура...

map — это сортированный контейнер, в отличие от hash_map.
Твоя конструкция отсортирует элементы vector<pair<K,V>> в порядке их добавления.

Кроме того, map сохраняет итераторы при операциях добавления-удаления. В отличие от vector.

Так что — определяешься с требованиями к контейнеру:
* скорость вставки, удаления
* скорость доступа по ключу, по индексу, последовательно
* упорядоченность — по ключу / по времени вставки / не нужна
* сохраняемость — да / нет
и конструируешь из имеющегося.

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

CS>>А для чего предназначен map? Вот такой вот философско-теоретический вопрос...

Это я так повторяю вопрос. На этот раз с точки зрения практического программизма.

CS>>Мне почему-то кажется что конструкция типа
CS>>template dictionary<K,V> которая эффективно является имплементацией array<pair<K,V>> и hash_table<K, unsigned int> ( или avltree<K, unsigned int>)
CS>>гораздо полезнее чем голый stl::map.

К>наверное, vector<pair<const K, V> >, а не array?

У меня массив это array, а не вектор. Но имя не принципиально.

Еще раз dictionary это:

dictionary<K,V> 
{
  hash_table<K, unsigned int> index; // или avltree<K, unsigned int> - кому что надо
  array<pair<K,V>>            data;
// основные операции 
  bool exist(K);
  V&   operator [](K);
  K    key(unsigned int);
  V&   value(unsigned int);
}

(const модификаторы опущены)

К>map — это сортированный контейнер, в отличие от hash_map.

Так... давай пальцем показывай где сказано что map это сортированный контейнер.
Насколько мне помнится это не так. Уникальный — да. Сортированный — не обязательно — зависит от импл.

К>Твоя конструкция отсортирует элементы vector<pair<K,V>> в порядке их добавления.
Да, это т.н. естественный порядок. И это просто здорово что он есть!
Есть еще порядок следования ключей, но это совершенно иная "пестня". И достаточно редко кому нужная.

К>Кроме того, map сохраняет итераторы при операциях добавления-удаления. В отличие от vector.

А вот это вообще грустная импликация.
Итератор он для итерирования, а не для организации bookmarks.
Иметь несколько итераторов на одном множестве — такой дизайн мне нравится.

Или я опять не в общей струе? (3 см.сл.)

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

К>>map — это сортированный контейнер, в отличие от hash_map.

CS>Так... давай пальцем показывай где сказано что map это сортированный контейнер.
CS>Насколько мне помнится это не так. Уникальный — да. Сортированный — не обязательно — зависит от импл.

Стандарта под рукой нет, но в книге Остена написано, что map — это sorted associative container.
(Mattew H. Austern. Generic Programming and the STL. Addison Wessley, 1999. страница 466).

К>>Твоя конструкция отсортирует элементы vector<pair<K,V>> в порядке их добавления.
CS>Да, это т.н. естественный порядок. И это просто здорово что он есть!
CS>Есть еще порядок следования ключей, но это совершенно иная "пестня". И достаточно редко кому нужная.

Нужная, не нужная, однако зафиксированная в свойствах контейнера. А раз зафиксированная — значит, востребованная.

К>>Кроме того, map сохраняет итераторы при операциях добавления-удаления. В отличие от vector.

CS>А вот это вообще грустная импликация.
CS>Итератор он для итерирования, а не для организации bookmarks.

Вставка/удаление в векторе инвалидирует все итераторы после точки вставки. Поэтому операции над векторами нереентерабельны.
А вставка/удаление в списке, множестве и мапе — не инвалидирует.

template<class Cont>
void LetkaYenka(Cont& c) // 2 шага вперёд, 1 назад
{
  Cont::iterator i = c.begin(); // вот тебе итерирование, и никаких закладок
  while(true)
  {
    if(i != c.end()) cout << *(i++);
    if(i != c.end()) cout << ", " << *(i++);
    cout << endl;
    c.pop_front(); // оппа
  }
}

CS>Иметь несколько итераторов на одном множестве — такой дизайн мне нравится.

Если ты имеешь в виду несколько итераторов одного домена (т.е. на одном экземпляре контейнера std::map) — то это вообще свойство любых forward iterator'ов. В отличие от input и output iterator, которых не требуется (а то и запрещается) клонировать.
Если же доступ к контейнеру можно осуществлять разными способами, например — в порядке добавления и в порядке сортировки — то это тоже нормальное явление. STL-ные контейнеры имеют по два домена итераторов — прямой и обратный порядок. Почему бы не ввести ещё один, если твой контейнер это умеет?

---

В качестве предмета для медитации — рекомендую всё ту же книгу Остена.
Не знаю, есть ли она в русском переводе, но вполне возможно, что есть.

А вот и Стандарт.

23.1.2. Associative containers.

1) Associative containers provide an ability for fast retrieval of data based on keys. The library provides four basic kinds of associative containers: set, multiset, map, multimap.

8) The insert members shall not affect the validity of iterators and references to the container, and the erase members shall invalidate only iterators and references to the erased elements.

9) The fundamental property of associative containers is that they iterate through containers in the non-descending order of keys where non-descending is defined by the comparsion that was used to construct them.
For any two dereferenceable iterators i and j such that distance from i to j is positive, value_comp(*j,*i)==false.