Russian Qt Forum

Добрый день

Есть контейнер возрастающих значений кратных 10, напр
Нужна ф-ция которая бы "заполняла дырки" и возвращала заполненное значение не меньше фиксированного заданного min. Напр если min=50 то для контейнера выше ф-ция должна последовательно выдавать
Др словами ф-ция вставляет в контейнер наименьшее уникальное значение кратное 10 и >= min

Спасибо

проще перегенерить его заново от мин значения через какой нибудь std::generate

Думаю что нет, не проще. А откуда вообще берется такая задача? Может Вы с ней уже встречались?  :)

Бывают подобные задачи, например при вставке в БД, когда автоинкремент не совсем уместен.
Проще потому, что все равно "пустоты" надо как то проверять, а без беготни это никак не сделаешь, ну либо писать "аналог" БД и заводить индексы, того, чего нет, но это сомнительное решение.

Неужели все так сложно? Десяток-другой строчек - уже проблема? Может просто "сделать" вместо поиска каких-то альтернатив?  :) Я пошел по пути наименьшего сопротивления и задействовал ассоциативный контейнер

C++ (Qt)
struct Uniquer {
 
	Uniquer( int start, int increment) :
		mStart(start),
		mIncrement(increment)
	{
	}
 
	void Add( int value )
	{
		mSet.insert(value);
	}
 
	int Get( void )
	{
		auto it = mSet.lower_bound(mStart);
 
		while ((it != mSet.end()) && (mStart == *it)) {
			mStart += mIncrement;
			++it;
		}
 
		int result = mStart;
		mSet.insert(mStart);
		mStart += mIncrement;
		return result;
	}
 
// data
	std::set mSet;
	int mStart, mIncrement;
};
 

Что вполне устраивает для моих нужд. Но все-таки std::set - удовольствие достаточно дорогое, да и много лишних данных хранится при интенсивной генерации, может и lower_bound нужен не всегда. С др стороны не хочется усложнять код. В общем, прошу блеснуть техникой  :)

Теперь осталось посчитать разницу в сложности алгоритмов между этим и std::generate.
У последнего О(N), даже в самых сложных условиях, кода одна строка, памяти не надо вообще.

Я конечно понимаю что std - пуп земли, и облаять велосипедиста - дело святое, но причем тут std::generate  ??? Заглянем в справочник
Не вижу как это вообще связано с темой
   

Все верно, ресайзим старый контейнер под новые нужды, и заполняем его без пробелов с шагом 10 через генератор, который этот шаг и выдаёт.

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

Первоначально задача была заполнить дырки "от забора и до обеда". С шагом в 10.
При такой постановке, перегенерация от и до с шагом, была предложена выше.
Ну или задача поставлена была не полностью.

Так и есть - ведь каждая заполненная дырка и есть новое уникальное ID, о чем прозрачно намекает и название темы.

Ну такое предложение не стоит воспринимать серьезно :) Ага, помню ф-цию с похожим названием, авось подойдет - это ж типичное std::мЫшление  :)

Ну ладно, давайте "пополнее". Конечно можно генерировать уникальные ID тупенько увеличивая счетчик - и никакие контейнеры не нужны. Но вот хотим сделать иначе - диапазон ID от 100 до 200 (например) использовать для ID параметров/данных определенного типа, другой диапазон - для данных др типа и.т.д. Тут уже счетчиком не отделаться - нужно иметь контейнер созданных ID. И при генерации следующего "заполнять дырку" - вот и имеем задачу стартового поста. Ну и вообще-то "откуда берется задача" - в постановку не входит, товарищи с опытом сами видят откуда :)

Много раз наблюдаю этот эффект: задача (якобы) "непонятна", задаются вопросы. Хорошо, разъясняю, подробнее - так подробнее, здесь секретов нет. НО это никогда ни к чему не ведет :) Вопросы стихают, а интересных ответов/мыслей как не было - так и нету.

Процитирую себя:
И собственно в приведенном коде это и было реализовано.
Я не вижу других вариантов кроме как
1. полная беготня по контейнеру от... и ...до с проверками
2. индексация пропущенных или наоборот заюзанных элементов и по этой индексации заполнение нужного контейнера.

Но второй случай жрет память и при крайних значениях по сложности может вылиться в первый, а то и поболее.

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

Если Вы говорите о приведенном мной коде - то ни о каких индексах я там не помышлял. [/quote]
Это чисто вопрос названия, просто в моем текущем проекте подобные решения называются "индексаторами".

Тогда стоит указать критерии "оптимальности", а то у каждого они могут оказаться свои. Среди них могут быть: минимум времени разработчика, затраченное на решение задачи, минимум символов в исходном коде решения, не использовать std, использовать такие конструкции С++, чтобы читатели кода мозг сломали и т.п. :).

Еще важнее узнать кто будет оценивать решения. Если сам Igors, то вряд ли найдется решение лучше. :)

Ну вот, опять танцору что-то мешает :) Есть разные подходы к одной задаче - вот и хотелось бы их увидеть, выбирайте те критерии что Вам по душе. "Вообще без std" бы конечно особо интересно, но разве такие смельчаки найдутся?

Перед критериями оптимальности у меня сначала стоит фильтр: стоит ли вообще заниматься решением какой-то задачи. Так вот на текущий момент данная задача по этому фильтру не проходит, так что извиняйте :).

Увы, привычка "задирать носик" очень быстро приобретается с изучением std :'(
Если Ваш хвильтр стоит "до того" - то чего тогда эфир засорять?

Чтоб другие время зря не тратили. Оптимизирую Вашу задачу по времени разработчиков :).

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

Igors, на будущее, если ты хочешь, чтобы кто-то за тебя сделал работу, то хотя бы потрудись накидать приемочный тест. Задание сформулировано ужасно.
Вот пример, чтобы ты понял, что от тебя требуется:

C++ (Qt)
int addIfBothPositive(int a, int b)
 
void test() {
    assert (addIfPositive(1, 2) == 3);
    assert (addIfPositive(1, -2) == 1);
    assert (addIfPositive(1, 0) == 1);
    assert (addIfPositive(-1, 5) == -1);
    assert (addIfPositive(-1, -5) == -1);
}
 

Да неужели?
Как видим, речь идет о заполнении строго "по одному", а вовсе не "залить весь массив" - в последнем никакого смысла нет. Меньше надо сборками заниматься :)

Почему Вы полагаете что каждый создающий тему - школота и жадный лох, которому нужно только получить текст под copy/paste? Не надо так плохо думать о людях. Да и как-то неудобно называть этот десяток строк "работой".

Задачу я давно решил, и свое решение привел выше. Вот хочу обсудить его с коллегами - может есть др возможности, использование модных новых приемов и все такое. Как говорится "на будущее". Никак не пойму что тут плохого, и почему так взвивается  тыкалка  :)

Это что-то типа "TDD"? Ну и что проверяет этот тест, и какая от него польза? По-моему аж никакой  :)

Нет, это не TDD.
Польза от него большая, если человек не может сформулировать ТЗ достаточно ясно. Напиши приемочный тест на свою задачу и укажи время выполнения твоего решения, может тогда и будет кому-то интересно покопаться. А так, смысла в твоем топике никакого, только интернет засоряет.

Так функция должна последовательно выдавать значения (куда? по одному или скопом? в  результате одного вызова или нескольких?) и/или вставлять значения в контейнер (какой?)?


Польза такая, что снимает озвученные выше вопросы.

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

Ход мысли примерно такой "Я не понял - значит сформулировано плохо!". Пример
Необязательно, это могут быть короткие ноги. Т.е. сформулировано-то нормально, проблемы с "понималкой". Стоило немного подумать - и все бы стало ясно. Не захотели - ну это Ваше дело.

>Ход мысли примерно такой "Я не понял - значит сформулировано плохо!"
Как ты можешь видеть выше, не понял задание не только я. Тебе разве не кажется, что пролема не в моей понималке, а в твоем корявом ТЗ?
Если уж ты притащил что-то сюда, то будь добр, прояви уважение к коллегам и сделай все правильно.

Нет, мне совсем так не кажется :) Ладно, кто там чего не понял - это неинтересно, вернемся к теме.

В чем недостаток предложенного решения (пока, увы, одного). Бросается в глаза что хранение организовано туповато, напр { 10, 20, 30, 40, 50.. } Напрашивается хранить не int'ы, а пары (диапазоны) непрерывно возрастающих значений, напр { 10, 50 }. Насколько помню, так Qt хранит selection. Худший случай: непрерывных данных нет, ну расход памяти вдвое больше, переживу. Но т.к. они добавляются подряд, то экономия памяти будет значительна (а заодно и скорость lower_bound). Написать это самому конечно можно, но такое решение следует признать "нетехничным", контейнер диапазонов - задача 100% стандартная и общая, стало быть надо искать готовое решение.

Итак, где же нам хапнуть такой готовый класс?  По этой части я не силен. Ну в дусте наверняка есть - но пока там раскопаешь - проще застрелиться :'( В std - не знаю, когда-то видел std::ranges но оно вроде только С++ 20, да и то ли это - хз

В общем, прошу блеснуть эрудицией и широтой познаний  :)