Слияние 2 сортированных контейнеров

[Igors]

Добрый день

Делаю интерактивный редактор типа "кисти" которая красит точки на "холсте" (в терминах Верес(а))  . Возникла такая задачка: даны 2 контейнера структур сортированных по возрастанию

Код

C++ (Qt)
typedef std::pair <int, double> TPair;
typedef std::vector <TPair> TVec;
 

Гарантируется уникальность first (ключа) в обоих исходных. В первом все second (значения) ненулевые. Нужно получить контейнер также сортированный,

Код

C++ (Qt)
TVec Merge( const TVec & src1, const TVec & src2 );
 

правила

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

- если эл-т с одним и тем же ключом есть в обоих - то принимается значение из второго (операция замещения) и эл-т включается в выходной  

- если эл-т с таким ключом (и ненулевым значением) только в первом или только во втором - он включается в выходной со своим значением.

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

------

Edit: еще лучше не возвращать контейнер, а модифицировать первый

Код

C++ (Qt)
void Merge( TVec & src1, const TVec & src2 );

Первый - исходные данные (потенциально большие), второй - что юзер натюкал мышей. Часто второй всего неск значений (а то и одно), поэтому хотелось бы отделаться только изменениями в первом (если такая возможность есть). Ну ладно, то "optional", реализация первоначального тоже интересна

[m_ax]

Набросал на коленке (немного изменённый std::merge..)

Код

C++ (Qt)
struct my_predicate
{
    template <class T>
    bool operator()(const T & a) const
    {
        return (a.second != 0);
    }
 
    template <class T>
    bool operator()(const T & a, const T & b) const
    {
        return b.first <= a.first;
    }
};
 
 
template <class Iterator, class Container, class Predicate>
void merge_if(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              Container & result, Predicate pred)
{
    while (true)
    {
        if (first1 == last1)
        {
            std::copy_if(first2, last2, std::back_inserter(result), pred);
            return;
        }
 
        if (first2 == last2)
        {
            std::copy(first1, last1, std::back_inserter(result));
            return;
        }
 
        if (!pred(*first2))
        {
            ++first2;
            continue;
        }
 
        if (pred(*first1, *first2))
            result.push_back(*first2++);
        else
            result.push_back(*first1++);
    }
}
 

Не проверял, но идея, думаю, понятна..

[Igors]

Проверяем кончился ли один из контейнеров, если да - копируем хвост второго. Хорошо, а дальше

Код

C++ (Qt)
        if (!pred(*first2))
        {
            ++first2;
            continue;
        }
 

Пример:
Первый: (1, 0.6) (2, 0.1) ...
Второй: (2, 0.0) ...

В итоге эл-т (2, 0.1) успешно проскочил (а не должен был)

[m_ax]

В итоге эл-т (2, 0.1) успешно проскочил (а не должен был)

Не страшно) Есть предикат, а его уже можно научить и это проверять)

[Igors]

Не страшно) Есть предикат, а его уже можно научить и это проверять)

А можно увидеть процесс его обучения? Ведь сейчас до нужного ф-ционала еще далеко

[Bepec]

offtop: Объяснив с "моей" терминологией вы четко обрисовали задачу. Однако, это уже прогресс

[m_ax]

Не страшно) Есть предикат, а его уже можно научить и это проверять)

А можно увидеть процесс его обучения? Ведь сейчас до нужного ф-ционала еще далеко

Ой далекоооо)

Ну, например, как то так (не проверял: это уже вопрос десятый, главное идея..):

Код

C++ (Qt)
struct my_stepper
{
    template <class T>
    bool operator()(const T & a) const
    {
        return (a.second != 0);
    }
 
    template <class Iter, class Container>
    bool operator()(Iter & in1, Iter & in2, Container & c) const
    {
        if (in2->second == 0) {
            key = in2->first;
            ++in2;
            return false;
        }
 
        if (key)
        {
            if (in1->first == *key) {
                ++in1;
                return false;
            }
        }
 
        auto it = std::back_inserter(c);
 
        *it++ = (in2.first <= in1.first) ? *in2++ : *in1++;
 
        return true;
    }
 
private:
    boost::optional<int> key;
};
 
 
template <class Iterator, class Container, class Stepper>
void merge_if(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              Container & result, Stepper stepper)
{
    while (true)
    {
        if (first1 == last1)
        {
            std::copy_if(first2, last2, std::back_inserter(result), stepper);
            return;
        }
 
        if (first2 == last2)
        {
            std::copy_if(first1, last1, std::back_inserter(result), stepper);
            return;
        }
 
        stepper(first1, first2, result);
    }
}
 

[Igors]

Вот картинка чтобы оживить обсуждение. Точки (узлы сетки) хранятся как пары *индекс + значение" которое показано цветом. Черные точки не хранятся (background). Юзер тыкает "кистью" которая может быть достаточно большой. Если кисть "жесткая" то все точки попавшие в радиус захвата получают цвет кисти (или удаляются из контейнера если кисть черная). Если кисть "мягкая" то результат размазывается/интерполируется от центра к краю. Формализуя это приходим к правилам поста #1  

[Igors]

Код

C++ (Qt)
    template <class Iter, class Container>
    bool operator()(Iter & in1, Iter & in2, Container & c) const
    {
        if (in2->second == 0) {
            key = in2->first;
            ++in2;
            return false;
        }
...
 

Пример: второй контейнер  (1, 0) (2, 0)... эл-т с индексом 1 не будет удален (из первого)

[m_ax]

Пример: второй контейнер  (1, 0) (2, 0)... эл-т с индексом 1 не будет удален (из первого)

Пфф.. Если нужна предыстория по всем нулевым ключам, то можно заменить boost::optional на обычный set, например.

Код

C++ (Qt)
struct my_stepper
{
    template <class T>
    bool operator()(const T & a) const
    {
        return (a.second != 0) && (keys.find(a.first) == keys.end());
    }
 
    template <class Iter, class Container>
    bool operator()(Iter & in1, Iter & in2, Container & c) const
    {
        if (in2->second == 0) {
            keys.insert(in2->first);
            ++in2;
            return false;
        }
 
        if (keys.find(in1->first) != keys.end())
        {
            ++in1;
            return false;
        }
 
        auto it = std::back_inserter(c);
 
        if (in2->first == in1->first)
        {
            *it++ = *in2++;
            ++in1;
            return true;
        }
 
        *it++ = (in2->first < in1->first) ? *in2++ : *in1++;
 
        return true;
    }
 
private:
    mutable std::set<int> keys;
};
 
 
template <class Iterator, class Container, class Stepper>
void merge_if(Iterator first1, Iterator last1,
              Iterator first2, Iterator last2,
              Container & result, Stepper stepper)
{
    while (true)
    {
        if (first1 == last1)
        {
            std::copy_if(first2, last2, std::back_inserter(result), stepper);
            return;
        }
 
        if (first2 == last2)
        {
            std::copy_if(first1, last1, std::back_inserter(result), stepper);
            return;
        }
 
        stepper(first1, first2, result);
    }
}
 

Но это всё детали конкретной реализации Вашего steppera.  

Основная здесь мысль в том, что этот подход сейчас достаточно гибок. Если завтра Вам придёт в голову написать ещё десяток правил для слияния, то достаточно лишь написать свои пользовательские stepperы при этом ничего не меняя в самой функции merge_if.
Более того, она будет работать с любым контейнером..      

[Igors]

Пфф.. Если нужна предыстория по всем нулевым ключам, то можно заменить boost::optional на обычный set, например.

Что значит "Пфф.. если нужна"? Не надо мне одолжений делать, условия знаете - стало быть нужна. И чего вот так, без раздумий, тулить ассоциативный контейнер? Это удовольствие дорогое. Не лучше ли так

Код

C++ (Qt)
template <class Iter, class Container>
void Step(Iter & in1, Iter & in2, Container & c) 
{
  if (in1->first < in2->first)  // ключ в первом меньше
    c.push_back(*in1++);    // добавляем из первого и продвигаем его
 
  else {    // ключ в первом НЕ меньше
    if (in2->second)  c.push_back(*in2);     // добавляем из второго если не ноль
    if (in1->first == in2->first) ++in1;        // двигаем первый если ключи равны
    ++in2;                      // всегда двигаем второй 
  }
} 
 

Но это неоптимально. Пример: юзер выбрал всего одну точку и меняет ее значение напр с 0.1 на 0.5. Чего же перемалывать весь контейнер? Ведь он сортирован, возможно пресловутое log(N). Как это сделать не плодя частных случаев?

[Bepec]

Без частных случаев - перемалывать весь контейнер

[m_ax]

Пример: юзер выбрал всего одну точку и меняет ее значение напр с 0.1 на 0.5. Чего же перемалывать весь контейнер? Ведь он сортирован, возможно пресловутое log(N). Как это сделать не плодя частных случаев?

Не понял? Есть два контейнера, нужно слить их в третий.. Это уже как минимум ~ N.. О каком логарифме идёт речь?   

[Igors]

Не понял? Есть два контейнера, нужно слить их в третий.. Это уже как минимум ~ N.. О каком логарифме идёт речь?

Edit: еще лучше не возвращать контейнер, а модифицировать первый

Код

C++ (Qt)
void Merge( TVec & src1, const TVec & src2 );

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

[m_ax]

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

Хотите быстрый поиск (logN), придётся использовать контейнер с random access доступом.. Но, вот если юзер тыкнет мышью и изменит значение на 0.0, то затраты на "выковыривание" этой точки из первого контейнера (вектора) перекроют затраты на поиск..
Короче, оно того стоит?