Форум программистов, компьютерный форум CyberForum.ru

Обход элементов std::map в порядке их создания - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.94
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16934 / 5339 / 328
Регистрация: 30.03.2009
Сообщений: 14,339
Записей в блоге: 26
19.03.2011, 13:18     Обход элементов std::map в порядке их создания #1
Имеется ассоциативный массив и его заполнение:

C++
1
2
3
4
std::map<unsigned,string> arr;
arr[10] = "abc";
arr[7] = "def";
arr[20] = "ghi";
Теперь если я буду обходить этот массив при помощи итераторов, то обход будет производиться в порядке возрастания ключа массива: т.е. в данном случае обойдутся элементы в порядке 7, 10, 20

Мне хочется обойти массив в порядке создания его элементов, т.е. 10, 7, 20. Вот здесь я прочёл, что в шаблон можно подать некий третий параметр Compare

Compare: Comparison class: A class that takes two arguments of the key type and returns a bool. The expression comp(a,b), where comp is an object of this comparison class and a and b are key values, shall return true if a is to be placed at an earlier position than b in a strict weak ordering operation. This can either be a class implementing a function call operator or a pointer to a function (see constructor for an example). This defaults to less<Key>, which returns the same as applying the less-than operator (a<b).
1. Я правильно понимаю, что этот параметр шаблона влияет ТОЛЬКО на процесс занесения элементов в таблицу (ну и, как побочный эффект, влияет на порядок обхода через итераторы) и ничего больше другого не делает
2. Как описать этот Compare для моего случая? У меня слишком маленький опыт работы с Си++, и, читая документацию, совсем сломал мозги. По исходнику контейнера map я тоже понять ничего не могу - для меня это ещё слишком сложно

Добавлено через 20 минут
Наконец, понял, что за ошибку выдавал компилятор, когда я пытался сделать так, как показано в примерах у людей: я Compare подавал третьим параметром в шаблон при описании массива, но итератор был написан как раньше - с двумя параметрами.

Итого, получается что-то типа того:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class compare
{
  public:
    bool operator() (const unsigned x,const unsigned y) const { return true; }
};
 
std::map<unsigned,string> arr;
arr[10] = "abc";
arr[7] = "def";
arr[20] = "ghi";
 
std::map<unsigned,string,compare>::const_iterator iter;
for (iter = arr.begin(); iter != arr.end(); iter++)
  ...
Но всё-таки хотелось бы услышать ответ на вопрос номер 1.

Добавлено через 1 час 14 минут
Однако при таком раскладе неправильно работает чтение элементов массива (x = arr[7]) или проверка наличия элемента (arr.find(7) != arr.end()). Так что вопрос снова актуален
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
TheAthlete
 Аватар для TheAthlete
151 / 151 / 12
Регистрация: 31.08.2010
Сообщений: 529
20.03.2011, 10:21     Обход элементов std::map в порядке их создания #2
Привет! Compare относится прежде всего к ключу, и он определяет порядок сортировки по ключу. Т.е. ты можешь задать свой класс compare, который будет по своему сортировать именно ключ, а не значение.

В спецификации map написано:

C++
1
2
template < class Key, class T, class Compare = less<Key>,
           class Allocator = allocator<pair<const Key,T> > > class map;
где less<Key> - функциональный объект, который принимает два параметра, x и y, типа Key и возвращает true, если x < y; в противном случае возвращает false

Отсюда следует, что при занесении ключей и значений в карту, ключи сразу сортируются и хранятся там в отсортированном виде.

Еще ссылка удалена нашел объяснение всему этому

 Комментарий модератора 
Публикация ссылок на другие форумы запрещена правилами форума (п. 3.7).
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16934 / 5339 / 328
Регистрация: 30.03.2009
Сообщений: 14,339
Записей в блоге: 26
20.03.2011, 11:14  [ТС]     Обход элементов std::map в порядке их создания #3
TheAthlete, спасибо конечно, но ты написал то, что и так следует из документации, но не ответил ни на один из поставленных вопросов. Попробую сам на них ответить, т.к. пришло некоторое понимание


Цитата Сообщение от Evg Посмотреть сообщение
1. Я правильно понимаю, что этот параметр шаблона влияет ТОЛЬКО на процесс занесения элементов в таблицу (ну и, как побочный эффект, влияет на порядок обхода через итераторы) и ничего больше другого не делает
В моём примере с простой функцией сравнения конкретно в моём случае перестал работать оператор [] и метод find. А потому на этот вопрос ответ отрицательный

Цитата Сообщение от Evg Посмотреть сообщение
2. Как описать этот Compare для моего случая? У меня слишком маленький опыт работы с Си++, и, читая документацию, совсем сломал мозги. По исходнику контейнера map я тоже понять ничего не могу - для меня это ещё слишком сложно
В класс Compare нужно добавить каким-то образом информацию о порядке создания элементов. Например, это может быть ещё один map, ключ которого совпадает с ключом нашего map'а, а значение которого есть порядковый номер создания. Но такой вариант получается излишне громоздким. В моей задаче проще создать вектор из пар "ключ-значение" и добавить процедуру поиска значения по ключу.
Manjak
 Аватар для Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
20.03.2011, 11:34     Обход элементов std::map в порядке их создания #4
1) Мапа организована как красно-черное дерево, соответственно, ключи сортируются (сравнение осуществляэтся именно предикатом переданым в третьем параметре шаблона).

2) Если стоит такая задача, то лучше использовать вектор или дек. Чтобы таки получилось использовать мапу, то ключем можно сделать время создания, а предикат сравнения использовать std::greater
TheAthlete
 Аватар для TheAthlete
151 / 151 / 12
Регистрация: 31.08.2010
Сообщений: 529
20.03.2011, 12:06     Обход элементов std::map в порядке их создания #5
Хотя можно реализовать таким вот образом:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <map>
#include <string>
 
using std::cout;
using std::endl;
using std::map;
using std::string;
using std::make_pair;
 
int main() {
  map<unsigned, string> arr;
  map<unsigned, string>::iterator it;
 
  arr[10] = "abc";
  arr[7] = "def";
  arr[20] = "ghi";
 
  map<string, unsigned> arr2;
  map<string, unsigned>::iterator it2;
 
 
  cout << "Исходные значения" << endl;
  for (it = arr.begin(); it != arr.end(); ++it) {
    cout << it->first << " -> " << it->second << endl;
  }
 
  for (it = arr.begin(); it != arr.end(); ++it) {
    arr2.insert(make_pair(it->second, it->first));
  }
 
  cout << endl;
 
  cout << "Преобразованные значения" << endl;
  for (it2 = arr2.begin(); it2 != arr2.end(); ++it2) {
    cout << it2->first << " -> " << it2->second << endl;
  }
 
  return 0;
}
Ничего другого в голову не приходит пока
Manjak
 Аватар для Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
20.03.2011, 12:13     Обход элементов std::map в порядке их создания #6
Цитата Сообщение от Manjak Посмотреть сообщение
1) Мапа организована как красно-черное дерево, соответственно, ключи сортируются (сравнение осуществляэтся именно предикатом переданым в третьем параметре шаблона).

2) Если стоит такая задача, то лучше использовать вектор или дек. Чтобы таки получилось использовать мапу, то ключем можно сделать время создания, а предикат сравнения использовать std::greater
Не надо там по убыванию сортировать, очепятался
ForEveR
Модератор
Эксперт С++
 Аватар для ForEveR
7933 / 4715 / 318
Регистрация: 24.06.2010
Сообщений: 10,525
Завершенные тесты: 3
20.03.2011, 20:49     Обход элементов std::map в порядке их создания #7
Evg, Ну да. Аналогично будет некорректным код.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <map>
#include <string>
 
int main()
{
    std::locale().global(std::locale(""));
    std::map<unsigned,std::string> arr;
    arr[10] = "abc";
    arr[7] = "def";
    arr[20] = "ghi";
    std::map<unsigned, std::string>::iterator it=++arr.begin();
    const_cast<unsigned&>(it->first)=999999;
    it=arr.find(20);
    if(it == arr.end())
    {
        std::cerr<<"Кирдык контейнеру. Изменение значения убило балансировку\n";
        return 1;
    }
    else
        std::cout<<"Все корректно, но это только пока\n";
    return 0;
}
Вообщем все, что нарушает возможность балансировки контейнера (а твой предикат это и делал) - убивает контейнер.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2011, 20:56     Обход элементов std::map в порядке их создания
Еще ссылки по теме:

C++ Std::map и key_comp
Std::map::emplace C++
C++ Emplace в std::map. Как добавить элемент в std::map без копирования?
C++ Особенности std::map
Потокобезопасность std::map::end, std::list::end C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
20.03.2011, 20:56     Обход элементов std::map в порядке их создания #8
я думаю это невозможно, ибо в будущем стандарте появится unordered_map, где сами по названию понимаете
сейчас он есть в бусте и std::tr1
Yandex
Объявления
20.03.2011, 20:56     Обход элементов std::map в порядке их создания
Ответ Создать тему
Опции темы

Текущее время: 18:33. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru