Форум программистов, компьютерный форум, киберфорум
C++
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.95/103: Рейтинг темы: голосов - 103, средняя оценка - 4.95
Evg
Эксперт CАвтор FAQ
 Аватар для Evg
21281 / 8305 / 637
Регистрация: 30.03.2009
Сообщений: 22,660
Записей в блоге: 30

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

19.03.2011, 13:18. Показов 21190. Ответов 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
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
19.03.2011, 13:18
Ответы с готовыми решениями:

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

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

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

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


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

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

2) Если стоит такая задача, то лучше использовать вектор или дек. Чтобы таки получилось использовать мапу, то ключем можно сделать время создания, а предикат сравнения использовать std::greater
0
 Аватар для TheAthlete
174 / 170 / 19
Регистрация: 31.08.2010
Сообщений: 575
20.03.2011, 12:06
Хотя можно реализовать таким вот образом:

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
 Аватар для Manjak
270 / 176 / 46
Регистрация: 12.03.2010
Сообщений: 494
20.03.2011, 12:13
Цитата Сообщение от Manjak Посмотреть сообщение
1) Мапа организована как красно-черное дерево, соответственно, ключи сортируются (сравнение осуществляэтся именно предикатом переданым в третьем параметре шаблона).

2) Если стоит такая задача, то лучше использовать вектор или дек. Чтобы таки получилось использовать мапу, то ключем можно сделать время создания, а предикат сравнения использовать std::greater
Не надо там по убыванию сортировать, очепятался
0
В астрале
Эксперт С++
 Аватар для ForEveR
8049 / 4806 / 655
Регистрация: 24.06.2010
Сообщений: 10,562
20.03.2011, 20:49
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
бжни
 Аватар для alex_x_x
2473 / 1684 / 135
Регистрация: 14.05.2009
Сообщений: 7,162
20.03.2011, 20:56
я думаю это невозможно, ибо в будущем стандарте появится unordered_map, где сами по названию понимаете
сейчас он есть в бусте и std::tr1
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
20.03.2011, 20:56
Помогаю со студенческими работами здесь

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

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Новые блоги и статьи
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США.
Programma_Boinc 26.12.2025
Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Нашел на реддите интересную статью под названием «Кто-нибудь знает, где получить бесплатный компьютер или. . .
Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка.
Programma_Boinc 23.12.2025
Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~
and_y87 14.12.2025
PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .
Как объединить две одинаковые БД Access с разными данными
VikBal 11.12.2025
Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.
Новый ноутбук
volvo 07.12.2025
Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro
Музыка, написанная Искусственным Интеллектом
volvo 04.12.2025
Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .
От async/await к виртуальным потокам в Python
IndentationError 23.11.2025
Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов
Argus19 22.11.2025
Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .
Сколько Государство потратило денег на меня, обеспечивая инсулином.
Programma_Boinc 20.11.2025
Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .
Ломающие изменения в C#.NStar Alpha
Etyuhibosecyu 20.11.2025
Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru