Простой (?) поиск

[Igors]

Если объектов десятки-сотни миллионов, тогда ...

Ну вот, опять пошли "анализы" А можно просто "решить задачу" без всяких "если"? Неужели она и вправду настолько сложна, что надо ловчить, привлекать БД и.т.п ? Не аерю. По меньшей мере один вариант есть - в мапе пройтись по всем объектам с одинаковым именем (кода не больше)

[RedDog]

По меньшей мере один вариант есть - в мапе пройтись по всем объектам с одинаковым именем (кода не больше)

И смысл мапы при условии, что у всех объектов будет одинаковое имя?
ps: это частный случай, того что я написал.

[ViTech]

Ну вот, опять пошли "анализы" А можно просто "решить задачу" без всяких "если"? Неужели она и вправду настолько сложна, что надо ловчить, привлекать БД и.т.п ? Не аерю. По меньшей мере один вариант есть - в мапе пройтись по всем объектам с одинаковым именем (кода не больше)

Нельзя . Т.е. можно, но это решение не будет одинаково эффективным для множества разных "если". Если элементов около сотни. Если элементов сотни миллионов. Если можно/нельзя использовать многопоточность. Если быстродействие важнее расходов по памяти. Если наоборот. Напишите одно решение, которое будет одинаково эффективно работать хотя бы для всех тех "если", которые я перечислил .

[SimpleSunny]

Так а чем вариант с QMap <QMap... не подошел? Поиск правда не совсем 2мя строками, но...

Код

C++ (Qt)
QMap <QString, QMap <int, QMap <bool, Data*>>> byName;
QMap <QString, Data*> anyType;
 
Data* findObject(QString name, int type, bool visible)
{
    auto byType = byName.find(name);
    //has name
    if (byType != byName.end())
    {
        auto byVisibility = byType->find(type);
        //has type
        if (byVisibility != byType->end())
        {
            auto object = byVisibility->find(visibility);
            //has visible
            if (object != byVisibility->end())
                return *object;
            //no visible
            else
                return byVisibility[!visibility];
        }
        //no type
        else
        {
            return anyType[name];
        }
    }
 
    //no name
    return nullptr;
}

И заполнять обратным перебором как-то так

Код

C++ (Qt)
void insert(QString name, int type, bool visible, Data *value)
{
    anyType[name] = value;
    byName[name][type][visible] = value;
}

[RedDog]

Так а чем вариант с QMap <QMap... не подошел?

Не выполнится условие "первый в оригинальном массиве"

[Racheengel]

1. Проиндексировать все объекты по именам:
QMap<QString, QList<int> >

где в список для каждого уникального имени заносить порядковый номер объекта в оригинальном массиве.

2. При поиске, если имя в мапе найдено, то взять массив индексов и далее "в лоб" только по нему.
Ну а иначе объект не найден.

Вроде несложно, не?

[SimpleSunny]

Так а чем вариант с QMap <QMap... не подошел?

Не выполнится условие "первый в оригинальном массиве"

Почему это?

[RedDog]

Почему это?

Потому что во второй мапе ключ это тип, а не индекс в оригинальном массиве

[Igors]

Напишите одно решение, которое будет одинаково эффективно работать хотя бы для всех тех "если", которые я перечислил .

Да не вопрос

Код

C++ (Qt)
struct Node {
	QString GetName( void ) const;
	int		GetType( void ) const;
	bool	GetVisibility( void ) const;
};
 
typedef QPair<QString, int> TKey;	// name + index
typedef QPair<int, int>		TAux;	// id (as bool) + visible  (as bool)
typedef QMap<TKey, Node *>	TFindMap;
 
TFindMap BuildFindMap( const QVector<Node *> & nodes )
{
	TFindMap fmap;
	for (int i = 0; i < nodes.size(); ++i)
		fmap[TKey(nodes[i]->GetName(), i)] = nodes[i];
 
	return fmap;
}
 
Node * FindNode( const TFindMap & fmap, const QString & name, int type )
{
	TKey key(name, -1);
	TFindMap::const_iterator it = fmap.lowerBound(key);
	Node * bestNode = 0;
	TAux bestAux(-1, -1);
	while (it != fmap.end()) {
		if (it.key().first != name) break;
		Node * node = it.value();
		TAux curAux((node->GetType() == type) ? 1 : 0,
					 node->GetVisibility() ? 1 : 0);
		if (curAux > bestAux) {
			bestNode = node;
			bestAux = curAux;
			if (bestAux.first && bestAux.second) break;
		}
		++it;
	}
	return bestNode;
}
 

Как это улучшить? И что там за дичь с эл-тами которые сами контейнеры? Может лучше на чистом "С" потренироваться,  чтобы контейнерами так не ляпать?

Нельзя . Т.е. можно, но это решение не будет одинаково эффективным для множества разных "если". Если элементов около сотни. Если элементов сотни миллионов. Если можно/нельзя использовать многопоточность. Если быстродействие важнее расходов по памяти. Если наоборот.

Ну конечно играть роль "эксперта" приятно  , но в очередной раз замечаю (и/или замечу): углубление в детали проекта часто/обычно работает в минус. Проект живет своей жизнью и выводы могут быстро оказаться устаревшими. Напр пока я помню проект с макс 50К объектами, но в связи с недавним переводом на 64 запросто может быть уже и 200-300К. Также оценить "кратность" непросто даже в среднем проекте. Да, объектов может быть и сотка, но  поиск зовется для каждой ячейки в таблице. Только убедиться в этом - неск дней разрывания кода, часто чужого. Так может за это время просто сделать "нормально"?  

[SimpleSunny]

Почему это?

Потому что во второй мапе ключ это тип, а не индекс в оригинальном массиве

Для каждой комбинации (имя,тип,видимость) хранится только лучшее соответствие, поэтому все подходит под заданные условия.

[ViTech]

Напишите одно решение, которое будет одинаково эффективно работать хотя бы для всех тех "если", которые я перечислил .

Да не вопрос

Код

C++ (Qt)
...
 

Ещё какой вопрос. Вот сидит пользователь, постоянно изменяет данные в контейнере с парой-тройкой сотен тысяч элементов. Иногда(очень редко) ищет  элемент по заданным условиям, смотрит на него, и продолжает дальше изменять данные. В предложенном решении каждый раз формируется дополнительный TFindMap (+ память, + время), хотя в лучшем случае нужный элемент найдётся в исходном контейнере менее чем за один проход, в худшем - один проход и ещё немного по наиболее подходящим элементам. И где в Вашем решении хоть какая-нибудь эффективность?  На кой нужен дополнительный TFindMap? Оно не эффективно ни по одному критерию из тех, что я приводил. Это плохое решение, переделывайте .

[Igors]

[Ещё какой вопрос. Вот сидит пользователь, постоянно изменяет данные в контейнере с парой-тройкой сотен тысяч элементов. Иногда(очень редко) ищет  элемент по заданным условиям, смотрит на него, и продолжает дальше изменять данные.

Все происходит совсем не так Юзер может выбрать любое кол-во объектов и записать их установки в файл, потом этот файл надо как-то загрузить (возможно в совсем др сцене) - вот придумали/установили такие правила загрузки по умолчанию. Кстати "установки" - те самые curve(s) с которыми Вы уже знакомы 

В предложенном решении каждый раз формируется дополнительный TFindMap (+ память, + время), хотя в лучшем случае нужный элемент найдётся в исходном контейнере менее чем за один проход, в худшем - один проход и ещё немного по наиболее подходящим элементам. И где в Вашем решении хоть какая-нибудь эффективность?

Отчаянное желание придраться   

На кой нужен дополнительный TFindMap?

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

Оно не эффективно ни по одному критерию из тех, что я приводил. Это плохое решение, переделывайте .

Щас, разбежался 

[ViTech]

Отчаянное желание придраться 

Хотите сказать, что для моего варианта использования Ваше решение является очень эффективным и я всего лишь придираюсь?

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

А откуда товарищам знать, что всё происходит не так, как я описал, а "совсем не так"? Сколько ещё страниц в теме нужно исписать, чтобы выяснить что и как у Вас происходит? Если Вас, конечно, интересует эффективное решение задачи, а не "универсальное академическое среднее по больнице" .

[deMax]

Академическое - это БД. Для случая когда непонятен текущий объем и непонятна масштабируемость. Если что, всегда можно перескочить на другую БД. или купить сервера помощнее.

[Igors]

Академическое - это БД.

Ой    Крайность обратная "прямому перебору".

А откуда товарищам знать, что ..

Да все товарищи правильно поняли как и положено профессиональным программистам. Если данные "не лезут в память" то описание с этого и начинается. Если я об этом не упомянул - значит этой проблемы нет. Так же и с изменением данных "на лету", это совсем др задача. Стало быть речь идет о самой банальной ситуации - построить структуры для поиска один раз, и затем искать многократно. Ну и чего тратить время и место на совершенно ненужные "выяснения" (хз чего) ?

Возвращаясь к теме. Практически пробежка по всем объектам с одинаковым именем вполне устраивает. Если юзер назначил всем одинаковые имена - значит сам "злобный Буратино", пусть страдает. Просто стало интересно как же так - все ключи есть, а быстрого поиска .. строго говоря нет. Приходится или перебирать диапазон или городить ужасные структуры (что еще хуже). Вот если бы тип был bool - тогда получается, а так нет. И похоже это нормально.

Еще рассматривал такой вариант:  ключи = имя + visible + тип, А на поиске (псевдокод)

Код

C++ (Qt)
lowerBound(TKey(name, true, type))  // если найдено (name + type) - возвращаем, иначе 
lowerBound(TKey(name, false, type))  // если найдено (name + type) - возвращаем, иначе
// лучший из 2 

Возможно это точнее, хотя возни побольше