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

[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.

[Igors]

Templates - это не расширение алгоритмических возможностей. Это удобство.
И как это ни странно, templates применять надо с осторожностью и не часто! Как бы не кричали любители templates.

Ну может не стоит "агитировать большевика за революцию"? Мое мнение о template такое же  

Вам не известен алгоритм для решения вашей задачи. Какой может быть разговор о templates.

Известен (ведь как-то же я живу  )

- "встали" на элемент (base)

- идем по сортированному массиву вперед пока не останется элементов для слияния c base. Конкретно для 2D (3D) точки (ключа) условие конца

Код

vec[i].x - vec[base].x > TOLERANCE; // i > base
 

- после этого "диапазон слияния" определен. Разбирается с ним, сортируя диапазон (ну здесь очевидно, надо только не забыть про порядок и пере-индексацию)

А вот с template не ложится - а хотелось бы!

[spectre71]

Ну, если алгоритм определен и он подходит для всех соответствующих типов, то проблем нет. Просто у каждого типа необходимо определить методы которые использует алгоритм. Далее пишется шаблон алгоритма использующий общие методы(операторы) соответствующих типов.

Если уже есть реализация для некоторого типа, то проще всего отталкаваться от нее, просто сделать ее шаблонной. Подставляем вместо конкретных типов T1, T2, ... Определяям необходимые общие методы, реализовываем их для каждого типа(у кого они не реализованы). Далее, при необходимости, можно занимать оптимизациями алгоритма и интерфейса.

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

[Igors]

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

Видимо да, надо подучиться. Книжка не "Александреску" случайно? (много слышал но не читал). Буду признателен за ссылочку.

FYI: эта задача называется "weld vertices"

[spectre71]

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

Видимо да, надо подучиться. Книжка не "Александреску" случайно? (много слышал но не читал). Буду признателен за ссылочку.

FYI: эта задача называется "weld vertices"

Смотри сообщение в личке.

[Авварон]

а мне?

[spectre71]

а мне?

Кому еще, пишите в личку.