Uniquer

[Igors]

Добрый день

Есть контейнер возрастающих значений кратных 10, напр

vec[0] = 60
vec[1] = 70
vec[2] = 80
vec[3] = 100
vec[4] = 110
vec[5] = 1000
vec[6] = 1100

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

50, 90, 120..9990, 1010..1090. 1110...

Др словами ф-ция вставляет в контейнер наименьшее уникальное значение кратное 10 и >= min

Спасибо

[RedDog]

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

[Igors]

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

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

[RedDog]

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

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

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

[Igors]

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

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

Код

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 нужен не всегда. С др стороны не хочется усложнять код. В общем, прошу блеснуть техникой 

[RedDog]

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

[Igors]

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

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

template <class ForwardIterator, class Generator>
  void generate (ForwardIterator first, ForwardIterator last, Generator gen);

Generate values for range with function
Assigns the value returned by successive calls to gen to the elements in the range [first,last).

The behavior of this function template is equivalent to:

template <class ForwardIterator, class Generator>
  void generate ( ForwardIterator first, ForwardIterator last, Generator gen )
{
  while (first != last) {
    *first = gen();
    ++first;
  }
}

Не вижу как это вообще связано с темой
   

[RedDog]

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

[Igors]

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

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

[RedDog]

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

[Igors]

Первоначально задача была заполнить дырки "от забора и до обеда". С шагом в 10.

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

При такой постановке, перегенерация от и до с шагом, была предложена выше.

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

Ну или задача поставлена была не полностью.

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

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

[RedDog]

Процитирую себя:

писать "аналог" БД и заводить индексы, того, чего нет

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

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

[Igors]

Процитирую себя:

писать "аналог" БД и заводить индексы, того, чего нет

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

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

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

[RedDog]

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

[ViTech]

Просто мне интересно насколько оптимально это решение и можно ли его улучшить не особо раздувая при этом код - вот об этом я хотел поговорить

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