Re: взаимозависимый typedef - C/C++

Здравствуйте, vvv104, Вы писали:

V>собственно хочется что-то типа такого:

V>

V>        typedef std::map<my_key, my_list::iterator> my_map;
V>        typedef std::list<std::pair<my_val, my_map::iterator> > my_list;

V>

V>Как бы сделать?

почитай про boost multi index container -- возможно он пможет

Здравствуйте, zaufi, Вы писали:

Z>Здравствуйте, vvv104, Вы писали:

V>>собственно хочется что-то типа такого:

V>>

V>>        typedef std::map<my_key, my_list::iterator> my_map;
V>>        typedef std::list<std::pair<my_val, my_map::iterator> > my_list;

V>>

V>>Как бы сделать?

Z>почитай про boost multi index container -- возможно он пможет

Это тот что типа мапы но с несколькими ключами? Это не совсем то, что мне нужно. Хочется иметь последовательный доступ по мапе и в то же время быстрый поиск по ключу.

Здравствуйте, vvv104, Вы писали:

V>>>

V>>>        typedef std::map<my_key, my_list::iterator> my_map;
V>>>        typedef std::list<std::pair<my_val, my_map::iterator> > my_list;

V>>>

Допустим определил, как добавлять собираешся?

V>Это тот что типа мапы но с несколькими ключами? Это не совсем то, что мне нужно. Хочется иметь последовательный доступ по мапе и в то же время быстрый поиск по ключу.

Можно уточнение?
Чем не достаточно вот такое определение?

typedef std::list<my_val> my_list;
typedef std::map<my_key, my_list::iterator> my_map;

Здравствуйте, Caracrist, Вы писали:

C>Здравствуйте, vvv104, Вы писали:

V>>>>

V>>>>        typedef std::map<my_key, my_list::iterator> my_map;
V>>>>        typedef std::list<std::pair<my_val, my_map::iterator> > my_list;

V>>>>

C>Допустим определил, как добавлять собираешся?

легко.

std::pair<my_map::iterator, bool> elem = myMap.insert(make_pair(someKey, myList.end()));
if (elem.second)
{
    elem.first->second = myList.insert(myList.end(), make_pair(someVal, elem.first));
}
else
{
    elem.first->second->first = someVal;
}

то есть главным является map. Удаление также. Сначала смотрим в map, берем из него итератор на list удаляем из листа и потом из map.

V>>Это тот что типа мапы но с несколькими ключами? Это не совсем то, что мне нужно. Хочется иметь последовательный доступ по мапе и в то же время быстрый поиск по ключу.

C>Можно уточнение?
C>Чем не достаточно вот такое определение?
C>

C>typedef std::list<my_val> my_list;
C>typedef std::map<my_key, my_list::iterator> my_map;
C>

на самом деле my_val не определяющий (вообще можно его не рассматривать, а в исходном варианте заменить в листе пару на просто итератор из мапы). мне хочется также иметь my_key как массив, чтобы полный список всех ключей. итерировать по мапе не хочется по понятным причинам.

Здравствуйте, vvv104, Вы писали:

V>Здравствуйте, Caracrist, Вы писали:

V>легко.

V>

V>std::pair<my_map::iterator, bool> elem = myMap.insert(make_pair(someKey, myList.end()));
V>if (elem.second)
V>{
V>    elem.first->second = myList.insert(myList.end(), make_pair(someVal, elem.first));
V>}
V>else
V>{
V>    elem.first->second->first = someVal;
V>}

V>

myMap.insert — сделает не валидными все итераторы в листе.

Здравствуйте, vvv104, Вы писали:

Z>>почитай про boost multi index container -- возможно он пможет
V>Это тот что типа мапы но с несколькими ключами? Это не совсем то, что мне нужно. Хочется иметь последовательный доступ по мапе и в то же время быстрый поиск по ключу.

Представьте себе, мульти-индекс и это прекрасно умеет

Кстати говоря, что подразумевается под "последовательный доступ по мапе"?
Пробежаться по элементам в том порядке, как они были добавлены, или в каком угодно, лишь бы последовательно? Так в последнем случае можно вообще одной мапой обойтись.

typedef map<my_key, my_value> my_map;

my_map m;
m[1] = 10;
m[5] = 20;
m[3] = 30;
m[2] = 40;
m[4] = 50;
for(my_map::const_iterator i=m.begin(); i!=m.end(); ++i)
    cout << i->first << ":" << i->second << " ";
    // 1:10 2:40 3:30 4:50 5:20

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

Здравствуйте, Caracrist, Вы писали:

C>myMap.insert — сделает не валидными все итераторы в листе.

Неправда. Вставка в мап не инвалидирует ссылки и итераторы на её элементы. В отличие от вектора.

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

Здравствуйте, vvv104, Вы писали:

V>собственно хочется что-то типа такого:
V>

V>        typedef std::map<my_key, my_list::iterator> my_map;
V>        typedef std::list<std::pair<my_val, my_map::iterator> > my_list;
V>

V>Как бы сделать?

Про мульти-индекс уже говорили. Но если охота поупражняться самому, то прямо так вот "в лоб" не получится — нужно определить какую-то хотя бы одну собственную сущность. Например, можно заменить std::pair собственным классом, тогда все срастается:

#include <list>
#include <map>

template<typename KeyT, typename ValueT>
struct my_list_entry
{
  typedef std::list<my_list_entry> my_list;
  typedef std::map<KeyT, typename my_list::iterator> my_map;
  
  ValueT value;
  typename my_map::iterator position_in_map;
  
  my_list_entry(ValueT value) : value(value) {}
};

typedef const char* my_key;
typedef int my_value;

typedef std::list<my_list_entry<my_key, my_value> > my_list;
typedef std::map<my_key, my_list::iterator> my_map;

//Использование
int main()
{
  my_list list;
  my_map map;
  
  my_list::iterator position_in_list = list.insert(list.end(), 123);
  position_in_list->position_in_map = map.insert(std::make_pair("qwerty", position_in_list)).first;
}

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, vvv104, Вы писали:

Z>>>почитай про boost multi index container -- возможно он пможет
V>>Это тот что типа мапы но с несколькими ключами? Это не совсем то, что мне нужно. Хочется иметь последовательный доступ по мапе и в то же время быстрый поиск по ключу.

К>Представьте себе, мульти-индекс и это прекрасно умеет

К>Кстати говоря, что подразумевается под "последовательный доступ по мапе"?
К>Пробежаться по элементам в том порядке, как они были добавлены, или в каком угодно, лишь бы последовательно? Так в последнем случае можно вообще одной мапой обойтись.

в любом порядке достаточно.

К>

К>typedef map<my_key, my_value> my_map;

К>my_map m;
К>m[1] = 10;
К>m[5] = 20;
К>m[3] = 30;
К>m[2] = 40;
К>m[4] = 50;
К>for(my_map::const_iterator i=m.begin(); i!=m.end(); ++i)
К>    cout << i->first << ":" << i->second << " ";
К>    // 1:10 2:40 3:30 4:50 5:20
К>

Собственно инкремент итератора в мапе довольно дорогостоящая штука (если я все правильно понимаю).

Здравствуйте, vvv104, Вы писали:

V>Собственно инкремент итератора в мапе довольно дорогостоящая штука (если я все правильно понимаю).

Нет. Полный забег по мапу занимает O(n), т.е. в среднем O(1) на инкремент.
Хотя отдельные инкременты могут занимать и O(log n), но, во-первых, что такое log n? В самом трагичном случае это 31.

... << RSDN@Home 1.2.0 alpha 4 rev. 1237>>

	От:	vvv104
	Дата:	08.10.09 13:06
	Оценка:

	От:	zaufi
	Дата:	08.10.09 13:57
	Оценка:	1 (1)

	От:	vvv104
	Дата:	08.10.09 14:22
	Оценка:

От:	Caracrist	https://1pwd.org/
Дата:	08.10.09 14:40
Оценка:

	От:	vvv104
	Дата:	08.10.09 14:57
	Оценка:

	От:	Кодт
	Дата:	09.10.09 09:38
	Оценка: