Russian Qt Forum

Добрый день

Есть исходный контейнер таких структур

C++ (Qt)
struct Cube {
 int x, y, z;  // уникальный ключ(и)
 ...
};
 

Нужно для заданного ключа (x0, y0, z0) найти все элементы c разницей по x, y, z не более чем +1 и не менее -1. Не гарантируется что  элемент с ключом (x0, y0, z0) есть. Можно создавать любые доп контейнеры и структуры (1 или более). Конечно можно использовать напр std::set и выполнить 27 поисков, но это как-то "недостойно программиста"  :)  А как по-умному?

Спасибо

Присоединяюсь к вопросу. Проблема чуть проще, но такого же типа.

Получилось, но "в общем виде" не дотянулся. Псевдокод

C++ (Qt)
template <class Key, class Container>
void FindMultiRecursive( 
	const Container & data,	// data container
	const Key & loKey,		// min key to search
	const Key & hiKey,		// max key to search
	SInt32 beg, SInt32 end )	// search range indices
{
	 while (end - beg > 1) {
		SInt32 mid = (beg + end) / 2;
		const Key & midKey = data[mid];
		if (midKey < loKey)
			beg = mid;
		else
			if (midKey > hiKey)
				end = mid;
			else {
				// here is most interesting
				// ...
				//
				FindMultiRecursive(data, loKey, midLoKey, beg, mid);
				FindMultiRecursive(data, midHiKey, hiKey, mid, end);
				return;
			}
	}		
}
 

Смысл в том что искомый диапазон лежит внутри индексов поиска, схема

Key[beg]------------- loKey --------- hiKey ----------Key[end]

Когда поиск попадает между 2 искомыми ключами, выбираются 2 новых ключа из искомого диапазона и крутим рекурс

А результат работы этой функции где смотреть?
Я так понял, что ключи в контейнере отсортированы?

Результат (найденные элементы) записывается там где "..."  :)
Да

Я беру коллекцию из элементов Cube и куда ее тут? Как ее сортируем?

Наверное Вы говорите о наборе ключей для которых надо найти элементы в (большом) контейнере data. У меня такого нет - просто 1 ключ и разница +/- 1. Ну как бы набор искомых задан аналитически. Поэтому "куда" решается по задаче. В любом случае по искомому ключу необходимо находить следующий и предыдущий искомый - в том же порядке сортировки что и для data.