Russian Qt Forum

Добрый день

Есть 2 контейнера (возможно с разным числом эл-тов). Для каждого эл-та в первом нужно найти какой ему соответствует во втором по ключам (ID + Name) или наоборот (Name + ID), порядок ключей задается юзером. Ключи не уникальны. Порядок поиска

- находим с таким же ID и Name
- иначе находим хотя бы с таким же ID
- иначе просто берем первый неиспользуемый из 2-го контейнера

Найденный во втором эл-т не может использоваться для поиска других эл-тов. Нет ограничений на число проходов поиска - напр первый проход ищет "полное" совпадение, второй только первый ключ и.т.д.

Как это сделать "техничнее", по возможности избегая длинного и нудного кода? И еще: квадратичный перебор не запрещается (вряд ли эл-тов будет мульены), но все-таки хотелось бы без него (мы же приличные люди  :))

Спасибо

Не очень понятно, почему вы упомянули, что порядок ID и Name может быть разный? Разве это не независимые поля структурки?
Первый неиспользуемый == один из тех, что остались незаюзанными после маппинга?
Что делать, если неиспользуемых нет?

можно глянуть boost multi_index_container

Проще всего создать дополнительные индексы (мапы) для 2 контейнера.
Например что то типа

typedef QPair<QString,QString> id_name_index;
QMap<id_name_index, item_index> index_map;

В index_map сложим все индексы элементов второго контейнера, определяемые парой индексов. Далее "все элементарно".

Один вопрос только: что значит "берем первый неиспользуемый из 2-го контейнера"?

Поля независимые, порядок (приоритет) нахождения разный - противоречий нет
Да
Ничего. Да, в первом может быть 10, во втором только 5 (или наоборот). Ну значит 5 и остались незамаплнены, невозможного не требуется

Когда-то читал, не очень понимаю как он здесь может пригодиться

Я тоже попытался мудрить в этом духе, но потом вставил флажок прямо к ключ и if в оператор <  :)   

Скорее "тривиально"  :) Но увы - длинновато. Получается 3 прохода, на каждом эл-т ищется в std::set и удаляется если найден. Может есть что покруче?

Не понял - ну то и значит, первый (по порядку) которые еще не был замаплен на эл-т первого контейнерв

В set у вас храниться только id/имя? я бы второй массив, в два map с ключом по индексу и по имени засунул; а значение указатель на элемент во втором массиве и флаг использования. перебор ~ 3*n*log(n)
для каждого элемента в первом массиве находим через map соответствия, и так 3 прохода.

Можно для красоты в свой map обернуть, типа такого DuoMap<T1 key1, T2 key2, T value> и методы find(key1,key2), find(key1).

p.s. Еще можно таблицы в БД хранить, там своя оптимизация, вряд ли будет быстрее но кода будет меньше.

Ключ такой получился

C++ (Qt)
struct CMuteKey {
	CMuteKey( SInt32 numVer = 0, const QString & name = QString(),
			  SInt32 entryIndex = -1, bool nameFirst = false ) :
		mNumVer(numVer),
		mName(name),
		mEntryIndex(entryIndex),
		mNameFirst(nameFirst)
	{
	}
 
	bool operator < ( const CMuteKey & other ) const
	{
		if (mNameFirst) {
			SInt32 match = mName.compare(other.mName);
			if (match < 0) return true;
			if (match > 0) return false;
 
			if (mNumVer < other.mNumVer) return true;
			if (mNumVer > other.mNumVer) return false;
		}
		else {
			if (mNumVer < other.mNumVer) return true;
			if (mNumVer > other.mNumVer) return false;
 
			SInt32 match = mName.compare(other.mName);
			if (match < 0) return true;
			if (match > 0) return false;
		}
 
		return mEntryIndex < other.mEntryIndex;
	}
 
// data members
	SInt32	mNumVer;       // ID 
	QString mName;              //  Name
	SInt32	mEntryIndex;  //  index in second container
	bool   mNameFirst;            // sort order (true = name first)
};
 

Для первого контейнера - вектор таких ключей с mEntryIndex = -1 (не найдено). Для второго - std::set таких ключей с  mEntryIndex = i (индекс во втором). Ну и 3 прохода.