Evg
Эксперт CАвтор FAQ
21275 / 8292 / 637
Регистрация: 30.03.2009
Сообщений: 22,656
Записей в блоге: 30
1

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

19.03.2011, 13:18. Показов 19713. Ответов 7
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Имеется ассоциативный массив и его заполнение:

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()). Так что вопрос снова актуален
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.03.2011, 13:18
Ответы с готовыми решениями:

Возможно ли создать контейнер std::map, в котором в качестве значения была бы ссылка на std::map?
Здравствуйте. Возможно ли создать контейнер std::map, в котором в качестве значения была бы...

Emplace в std::map. Как добавить элемент в std::map без копирования?
здравствуйте... есть ли способ не писать так: std::map&lt;int, char&gt; ksa;...

Очистка map и перевернутого std::map c std::greater
Написала я программу, которая заполняет два контейнера map. a,b. вывод программы такой 11 a:...

Std::map insert in while - добавление новых элементов в цикле
Задача - обьявить мапу, обьявить цикл и в цикле сначало проверять(если оно есть) содержимое мапы а...

7
174 / 170 / 19
Регистрация: 31.08.2010
Сообщений: 573
20.03.2011, 10:21 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).
0
Evg
Эксперт CАвтор FAQ
21275 / 8292 / 637
Регистрация: 30.03.2009
Сообщений: 22,656
Записей в блоге: 30
20.03.2011, 11:14  [ТС] 3
TheAthlete, спасибо конечно, но ты написал то, что и так следует из документации, но не ответил ни на один из поставленных вопросов. Попробую сам на них ответить, т.к. пришло некоторое понимание


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

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

2) Если стоит такая задача, то лучше использовать вектор или дек. Чтобы таки получилось использовать мапу, то ключем можно сделать время создания, а предикат сравнения использовать std::greater
0
174 / 170 / 19
Регистрация: 31.08.2010
Сообщений: 573
20.03.2011, 12:06 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;
}
Ничего другого в голову не приходит пока
0
270 / 176 / 46
Регистрация: 12.03.2010
Сообщений: 494
20.03.2011, 12:13 6
Цитата Сообщение от Manjak Посмотреть сообщение
1) Мапа организована как красно-черное дерево, соответственно, ключи сортируются (сравнение осуществляэтся именно предикатом переданым в третьем параметре шаблона).

2) Если стоит такая задача, то лучше использовать вектор или дек. Чтобы таки получилось использовать мапу, то ключем можно сделать время создания, а предикат сравнения использовать std::greater
Не надо там по убыванию сортировать, очепятался
0
В астрале
Эксперт С++
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
20.03.2011, 20:49 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;
}
Вообщем все, что нарушает возможность балансировки контейнера (а твой предикат это и делал) - убивает контейнер.
0
бжни
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
20.03.2011, 20:56 8
я думаю это невозможно, ибо в будущем стандарте появится unordered_map, где сами по названию понимаете
сейчас он есть в бусте и std::tr1
0
20.03.2011, 20:56
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.03.2011, 20:56
Помогаю со студенческими работами здесь

Не могу разобраться как обновить в std::map<std::string, вектор_структур>
Не могу разобраться как обновить вектор структур после его добавления в map без удаления и...

Стоит ли очищать в деструкторе std::map , std::vecotor?
У меня ещё один нубский вопрос :) Вот если в классе объявлены мапы и вектора, которые по ходу...

std::map, std::vector и порядок обхода коллекции
Здравствуйте, уважаемые! Вопрос следующий - если я сохраняю какие-то значения в map или вектор, то...

Std::unordered_multimap<std::string, int> map
Приветствую. Как можно получить только &quot;уникальный&quot; ключ в контейнере? ...


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2023, CyberForum.ru