Упаковка массива

[spectre71]

Делаем индекс который сортируем и чистим как надо итд.
Если нужен исходный массив, то оставляем его как есть, если нет, то чистим (то что не вошло в наш индекс).

Все так, вот только проблемы с "и.т.д"  Мне тоже все понятно (может лучше было даже запостить в раздел С/С++). Но почему-то когда я начинаю "реализовывать" - не очень красиво получается, и трудности/проблемы наползают одна на другую 

Пока проблема не понятна, вроде все просто.
Описывай задачу подробнее не вдаваясь сильно в предметную область.

[Igors]

Пока проблема не понятна, вроде все просто.
Описывай задачу подробнее не вдаваясь сильно в предметную область.

Ну если все просто, то никто не мешает написать ф-цию

Код

C++ (Qt)
template <class T1, class T2>
void PackContainer( T1 & vec, T2 & remapIndex )
{
 ...
}
 

Все что надо описано в посте #1, не требуется знания доп. деталей, др. классов и. т.п. Вот только ф-ция не очень получается 

[spectre71]

Пока проблема не понятна, вроде все просто.
Описывай задачу подробнее не вдаваясь сильно в предметную область.

Ну если все просто, то никто не мешает написать ф-цию

Код

C++ (Qt)
template <class T1, class T2>
void PackContainer( T1 & vec, T2 & remapIndex )
{
 ...
}
 

Все что надо описано в посте #1, не требуется знания доп. деталей, др. классов и. т.п. Вот только ф-ция не очень получается 

Естественно что ничего не получится. Раз не определен оператор "==" то нечего фильтровать!

- в общем случае нет оператора == (хотя можно рассчитывать на оператор < при сортировке). Пример: если 2 точки (x. y) или (x, y, z) отстоят друг от друга на расстояние меньше заданного (напр 1.0e-5) то их надо слить. Здесь возникают подлянки: напр. если есть "цепочка" точек, то легко удалить все кроме первой, но это будет неверно

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

При введении оператора "==" для двумерного случая вы нарушите требование к линейной упорядоченности(которая была определена в #4), пример:
Пусть delta = 2, тогда для точек A(0, 0), B(3, 0), , С(0, 1) мы получаем:
1) для операции "<=": A<=B<=C
2) для операции "==": A!=B и A==C
3) поскольку A<=B и A!=B => A<B
4) поскольку A==C => C<B.
5) Но из (1) и (4) получаем противоречие B<=C и B>C

Так что для данной модели данных описанный(желаемый) вами способ фильтрации не подойдет.

[Igors]

Естественно что ничего не получится. Раз не определен оператор "==" то нечего фильтровать!
...
С другой строны вполне возможно определить оператор "==" как написано выше, т.е точки равны если расстояние между ними не перевышает delta.

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

Код

C++ (Qt)
#define XY_TOLERANCE  1.0e-5f
inline bool CanMerge( const Point2D & p0, const Point2D & p1 )
{
  return (p1 - p0).length() < XY_TOLERANCE;
}
 

Да, придется выписать CanMerge для каждого типа, но это нормально, template требует жертв 

[spectre71]

Естественно что ничего не получится. Раз не определен оператор "==" то нечего фильтровать!
...
С другой строны вполне возможно определить оператор "==" как написано выше, т.е точки равны если расстояние между ними не перевышает delta.

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

Код

C++ (Qt)
#define XY_TOLERANCE  1.0e-5f
inline bool CanMerge( const Point2D & p0, const Point2D & p1 )
{
  return (p1 - p0).length() < XY_TOLERANCE;
}
 

Да, придется выписать CanMerge для каждого типа, но это нормально, template требует жертв 

1) Прежде чем пытаться сделать template, не понятно кому и для чего нужный, необходимо разобраться с самой системой данных и алгоритмами!
2) Ваш CanMerge в плане проблемы отсутствия линейной упорядоченности  равносилен приведенному мной "==". Даже более строго - оба варианта системы изоморфны
3) 2D систему можно сделать линейно упорядоченной по оперции "<=", но введение операции "==" (CanMerge, кластеров, итп.) основанной на расстоянии между точеками всегда приведет к нарушению линейной упорядоченности
4) Не получится отсортировать имеющиеся у вас данные(описанная система) таким образом, чтобы объединить(отфильтровать) их за линейное время O(n) (n кол-во элементов).

[Igors]

1) Прежде чем пытаться сделать template, не понятно кому и для чего нужный, необходимо разобраться с самой системой данных и алгоритмами!
2) Ваш CanMerge в плане проблемы отсутствия линейной упорядоченности  равносилен приведенному мной "==". Даже более строго - оба варианта системы изоморфны
3) 2D систему можно сделать линейно упорядоченной по оперции "<=", но введение операции "==" (CanMerge, кластеров, итп.) основанной на расстоянии между точеками всегда приведет к нарушению линейной упорядоченности
4) Не получится отсортировать имеющиеся у вас данные(описанная система) таким образом, чтобы объединить(отфильтровать) их за линейное время O(n) (n кол-во элементов).

1) Я никогда не стал бы городить template "ради спортивного интереса". Но здесь деваться некуда - реально надо. Ограничимся лишь 1 примером: есть 2D точки (x, y) и 3D (x, y, z). Для обоих задача та же самая (пост #1). Так что мне 2 ф-ции писать? Или "конвертировать 2D в 3D а потом обратно"?    А всего типов данных с десяток наберется, так что, с каждым "извиваться"? Ну расскажу я откуда они берутся, а что это изменит? Я должен обработать данные что мне дали а не те что "мне хочется".

2) и 3) Но ведь никто не предлагал использовать CanMerge для упорядочивания. Там все хорошо со скромным оператором <

4) За линейное или как - задача отфильтровать за разумное время (понятно квадратичный перебор умрет).

[spectre71]

Я никогда не стал бы городить template "ради спортивного интереса". Но здесь деваться некуда - реально надо. Ограничимся лишь 1 примером: есть 2D точки (x, y) и 3D (x, y, z). Для обоих задача та же самая (пост #1). Так что мне 2 ф-ции писать? Или "конвертировать 2D в 3D а потом обратно"?    А всего типов данных с десяток наберется, так что, с каждым "извиваться"? Ну расскажу я откуда они берутся, а что это изменит? Я должен обработать данные что мне дали а не те что "мне хочется".

ОК

2) и 3) Но ведь никто не предлагал использовать CanMerge для упорядочивания. Там все хорошо со скромным оператором <
4) За линейное или как - задача отфильтровать за разумное время (понятно квадратичный перебор умрет).

ОК

======================
Теперь вопросы.

1) Вам известен устраивающий вас алгоритм для обработки каждого типа данных?
2) Если положительный (1)!
  Этот алгоритм один для всех типов которые вы используете?

[Igors]

1) Вам известен устраивающий вас алгоритм для обработки каждого типа данных?
2) Если положительный (1)!
  Этот алгоритм один для всех типов которые вы используете?

Да, алгоритм один - иначе разговор о template беспочвенен/некорректен. Начало очевидно - сортируем указатели (или индексы). Дальше надо "прореживать" - вот тут дело хитрое. Сортировка поставит указатели "как хочет" а нам надо сохранить порядок следования при удалении. И это не все.

Код:

bool test = CanMerge(vec[i], vec[j]); // j > i

Если test = true, все ясно, i-й и j-й элемент слить можно. Но если test = false, это совсем НЕ значит что с i-м элементом "уже разобрались". Он может сливаться напр с j+1 элементом (ключу сортировки это не противоречит)

А на первый взгляд - простая задачка 

[spectre71]

1) Вам известен устраивающий вас алгоритм для обработки каждого типа данных?
2) Если положительный (1)!
  Этот алгоритм один для всех типов которые вы используете?

Да, алгоритм один - иначе разговор о template беспочвенен/некорректен. Начало очевидно - сортируем указатели (или индексы). Дальше надо "прореживать" - вот тут дело хитрое. Сортировка поставит указатели "как хочет" а нам надо сохранить порядок следования при удалении. И это не все.

Я не даром написал: "2) Если положительный (1)!"
И написал "обработки", а не сортировки или другой предварительной подготовке! Разговор шел об алгоритме решения задачи от и до!
Вам не известен алгоритм для решения вашей задачи. Какой может быть разговор о templates.
Templates - это не расширение алгоритмических возможностей. Это удобство.
И как это ни странно, templates применять надо с осторожностью и не часто! Как бы не кричали любители templates.

Код:

bool test = CanMerge(vec[i], vec[j]); // j > i

Если test = true, все ясно, i-й и j-й элемент слить можно. Но если test = false, это совсем НЕ значит что с i-м элементом "уже разобрались". Он может сливаться напр с j+1 элементом (ключу сортировки это не противоречит)

А на первый взгляд - простая задачка 

А про это я писал! Так не получиться.
Вы можете спокойно унифицированно прореживать одномерные массивы разных типов.
Но, нельзя свести в общем n-мерный к (n-1)-мерному случаю.

Возможно, стоит начать сначала, забыть пока про templates, и разобраться с алгоритмом. А когда он будет определен, тогда и можно будет вернуться к templates.