Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Языки программирования > С/С++
Перезагрузить страницу Как map, но с двумя Key
Закрытая тема
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
imported_Driver imported_Driver вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2003
По умолчанию Как map, но с двумя Key - 15.04.2003, 01:57

map подходящая вещь, но поиск нужен по двум ключам ( 1. int 2. set<int> )
Как бы это сделать?
  (#2 (permalink)) Старый
Влад Влад вне форума
Специалист
 
Сообщений: 3,884
Сказал(а) спасибо: 1
Поблагодарили 25 раз(а) в 25 сообщениях
Регистрация: 27.06.2002
Адрес: Санкт-Петербург
По умолчанию 15.04.2003, 11:57

Ни один ассоциативный контейнер не может иметь двух ключей. Ключ может быть один и только один.

В твоем случае, рассмотри возможность применения ключа вида pair<int, set<int> >.
  (#3 (permalink)) Старый
imported_Driver imported_Driver вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2003
По умолчанию 15.04.2003, 20:00

Цитата:
Originally posted by Влад
[b]В твоем случае, рассмотри возможность применения ключа вида pair<int, set<int> >.
Рассматривал. Мне нужно два независимых ключа и поиск нужен по каждому отдельно.

Вот как я решил сделать:
Код:
template <class Key, class T>
class doublemap : public map<Key, T>
{
private:
  map<int, map<Key, T>::iterator> second_key;
public:
  pair<map<Key, T>::iterator, bool> insert(const pair<Key, T> & x,
        int num)
        {
          if ( second_key.find(num) != second_key.end() )
            return make_pair(map<Key, T>::end(), false);
          pair<map<Key, T>::iterator, bool> ins = map<Key, T>::insert(x);
          if (ins.second) second_key.insert(make_pair(num, ins.first));
          return ins;
        }
  map<Key, T>::iterator find(int num)
        { return second_key.find(num)->second; }
  map<Key, T>::iterator find(Key key)
        { return map<Key, T>::find(key); }
};
Тип второго ключа здесь задан жестко (int), это у меня вроде порядкового номера элемента.
Такая структура не позволит зная первый ключ (Key) определить second_key, но мне это сейчас и не нужно.
А вообще для полноценного контейнера с двумя ключами пришлось бы объявлять
Код:
map<map<Key, T>::iterator, int> reverse_second_key;
в котором хранить "перевернутую" копию second_key, ну и написать соответствующие функции поиска.
Или есть другие варианты?
  (#4 (permalink)) Старый
Влад Влад вне форума
Специалист
 
Сообщений: 3,884
Сказал(а) спасибо: 1
Поблагодарили 25 раз(а) в 25 сообщениях
Регистрация: 27.06.2002
Адрес: Санкт-Петербург
По умолчанию 16.04.2003, 17:53

Что-то мне твой контейнер не очень нравится... Например, представь, как будет работать примерно такой код (это очень грубый пример):
Код:
doublemap<Key,T>  dm;

dm.insert(pair<Key,T>(key1, t1), 1);
dm.insert(pair<Key,T>(key2, t2), 2);
dm.insert(pair<Key,T>(key3, t3), 3);
// работаем с элементами...
// некоторые элементы больше не нужны, удаляем их:
dm.erase(key2);  // мы знаем только их key

// ... в другом месте кода:
for( int i=1; i < dm.size(); ++i)
{
    map<Key,T>::iterator it = dm.find(i);
    if (it != dm.end()) // элемент существует?
        что-то делаем с элементом.....
}
  (#5 (permalink)) Старый
imported_Driver imported_Driver вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2003
По умолчанию 16.04.2003, 20:29

Согласен, не заметил. Просто мне не нужно было удалять
Но это можно исправить легко (хотя и некрасиво)
Код:
  map<Key, T>::iterator find(int num)
        {
          map<Key, T>::iterator it = second_key.find(num)->second;
          return map<Key, T>::find(it->first);
        }

  pair<map<Key, T>::iterator, bool> insert(const pair<Key, T> & x,
        int num)
        {
          map<int, map<Key, T>::iterator>::iterator it;
          if ( ( it=second_key.find(num) ) != second_key.end() ) { 
          // второй ключ есть
            if ( map<Key, T>::find(it->second->first) !=
                 map<Key, T>::end() ) // и есть первый
              return make_pair(map<Key, T>::end(), false);
            else // первого нет
              second_key.erase(num);
          }
          pair<map<Key, T>::iterator, bool> ins = map<Key, T>::insert(x);
          if (ins.second) second_key.insert(make_pair(num, ins.first));
          return ins;
        }
(а памяти нам не жалко )

Цитата:
Originally posted by Влад
[b]Что-то мне твой контейнер не очень нравится
Предложи свой, простой и красивый
Ads.
  (#6 (permalink)) Старый
imported_Driver imported_Driver вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2003
По умолчанию 17.04.2003, 10:46

Код, который я вчера написал, безобразен.
Там побочные эффекты возникают.
Этот контейнер действительно не годится для удаления из него элементов.
  (#7 (permalink)) Старый
imported_Driver imported_Driver вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2003
По умолчанию 17.04.2003, 22:51

Я уже всех, наверное, достал своим контейнером
Вроде сейчас получился нормальный.
Код:
template < class Key, class T, class Key2 >
class doublemap : public map< Key, pair<T,Key2> >
{
private:
  typedef map< Key, pair<T,Key2> > BaseMap;
  typedef map<Key2, BaseMap::iterator> InternalMap;
  InternalMap second_key;
public:
  pair<BaseMap::iterator, bool> insert(const pair<Key, pair<T,Key2> > & x)
        {
          if ( second_key.find(x.second.second) != second_key.end() )
            return make_pair(BaseMap::end(), false);
          pair<BaseMap::iterator, bool> ins = BaseMap::insert(x);
          if (ins.second)
            second_key.insert(make_pair(x.second.second, ins.first));
          return ins;
        }
  BaseMap::iterator find(const Key & key)
        { return BaseMap::find(key); }
  BaseMap::iterator find(const Key2 & key2)
        {
          InternalMap::iterator it = second_key.find(key2);
          if ( it == second_key.end() ) return BaseMap::end();
          return it->second;
        }
  BaseMap::size_type erase(const Key & key)
        {
          BaseMap::iterator it = BaseMap::find(key);
          if (it == BaseMap::end()) return 0;
          second_key.erase(it->second.second);
          BaseMap::erase(it); //через итератор, наверное, быстрее удалять
          return 1;
        }
  BaseMap::size_type erase(const Key2 & key2)
        {
          InternalMap::iterator it = second_key.find(key2);
          if (it == second_key.end()) return 0;
          BaseMap::erase(it->second->first);
          second_key.erase(it);
          return 1;
        }
  void clear()
        {
          second_key.clear();
          BaseMap::clear();
        }
};
Остальные функции дописать будет, по-моему, нетрудно.
Критикуйте!
  (#8 (permalink)) Старый
Влад Влад вне форума
Специалист
 
Сообщений: 3,884
Сказал(а) спасибо: 1
Поблагодарили 25 раз(а) в 25 сообщениях
Регистрация: 27.06.2002
Адрес: Санкт-Петербург
По умолчанию 18.04.2003, 13:14

Как будто неплохо, по крайней мере, в реализованных функциях-членах не остается недействительных итераторов. Именно с ними были связаны побочные эффекты в первоначальной реализации. Не забудь про все версии insert и erase. Должно получиться.

Желаю успехов!
  (#9 (permalink)) Старый
imported_Driver imported_Driver вне форума
Member
 
Сообщений: 15
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 06.04.2003
По умолчанию 19.04.2003, 14:24

Спасибо!
Ads
Закрытая тема

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
как работать с двумя винчестерами vierd Любые вопросы от новичков 3 19.10.2011 00:58
Проблема с двумя хардами Fessmaster Накопители 0 16.07.2011 15:27
работа с двумя мониторами :tyz Мониторы 5 22.01.2011 17:57
Проблема с двумя DVD Владька Материнские платы 7 19.12.2010 15:16
Проблема с двумя Жесткими. Николаич Накопители 49 21.05.2010 01:16
Работа с двумя таблицами freeway C++ Builder 1 11.05.2007 20:57
Работа с двумя USB портами bagir Железо. Написание драйверов 4 13.06.2006 11:23
Работа с двумя exe файлами Rashad C++ Builder 19 30.01.2006 17:59
Отчет с двумя столбцами Alina Delphi 3 11.03.2005 00:09
XSL - работа с двумя XML файлами zoon XML & WML 1 01.12.2004 14:18
Отладка с двумя мониторами Duck Visual C++ 0 16.08.2004 16:05
Как работать с двумя файлами и двумя функциями dyv С/С++ 11 17.05.2004 12:16



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов