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

C++

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 47, средняя оценка - 4.94
Evg
Эксперт CАвтор FAQ
17951 / 6182 / 413
Регистрация: 30.03.2009
Сообщений: 16,974
Записей в блоге: 27
#1

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

19.03.2011, 13:18. Просмотров 6393. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.03.2011, 13:18
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Обход элементов std::map в порядке их создания (C++):

Вопрос по std::map - C++
В качестве хэш-таблицы для строк (AnsiString) я использовал std::map. От таблицы мне нужно было ещё и такое свойство: я хотел иметь...

переписать std::map - C++
Добрый вечер! Есть работающая программа, в которой используется map, все работало хорошо, но теперь немного изменились условия и объем...

std::string, std::fstream, ошибка кучи - C++
где то начало вылетать при операции += с локальной переменной std::string. Заменил на свой qString. Замечательно, то же самое... ошибка при...

Обход элементов формы - C++ Builder
Всем доброго времени суток. Знает ли кто-нибудь простой способ обхода всех дочерних элементов формы? Хочется попробовать сделать Enabled =...

Ошибка: E2034 Cannot convert 'int' to 'std::vector<std::vector<TRabbitCell,std::allocator<TRabbitCell>>... - C++ Builder
Есть двухмерный вектор: std::vector&lt;std::vector&lt;TRabbitCell&gt; &gt; *cells(5, 10); Пытаюсь заполнить его объектами класса...

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

7
TheAthlete
153 / 153 / 13
Регистрация: 31.08.2010
Сообщений: 535
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
17951 / 6182 / 413
Регистрация: 30.03.2009
Сообщений: 16,974
Записей в блоге: 27
20.03.2011, 11:14  [ТС] #3
TheAthlete, спасибо конечно, но ты написал то, что и так следует из документации, но не ответил ни на один из поставленных вопросов. Попробую сам на них ответить, т.к. пришло некоторое понимание


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

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

2) Если стоит такая задача, то лучше использовать вектор или дек. Чтобы таки получилось использовать мапу, то ключем можно сделать время создания, а предикат сравнения использовать std::greater
0
TheAthlete
153 / 153 / 13
Регистрация: 31.08.2010
Сообщений: 535
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
Manjak
269 / 175 / 7
Регистрация: 12.03.2010
Сообщений: 494
20.03.2011, 12:13 #6
Цитата Сообщение от Manjak Посмотреть сообщение
1) Мапа организована как красно-черное дерево, соответственно, ключи сортируются (сравнение осуществляэтся именно предикатом переданым в третьем параметре шаблона).

2) Если стоит такая задача, то лучше использовать вектор или дек. Чтобы таки получилось использовать мапу, то ключем можно сделать время создания, а предикат сравнения использовать std::greater
Не надо там по убыванию сортировать, очепятался
0
ForEveR
В астрале
Эксперт С++
7978 / 4737 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
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
alex_x_x
бжни
2447 / 1652 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
20.03.2011, 20:56 #8
я думаю это невозможно, ибо в будущем стандарте появится unordered_map, где сами по названию понимаете
сейчас он есть в бусте и std::tr1
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.03.2011, 20:56
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
8
Yandex
Объявления
20.03.2011, 20:56
Ответ Создать тему
Опции темы

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