Обновить элемент stl списка списков - PullRequest
Новая
       16

Обновить элемент stl списка списков

1 голос
/ 28 января 2020

Я работаю со списком из списка векторов целых (std::list<std::list<std::vector<int>>> z(nlevel)).

У меня может быть что-то вроде: 

{ {1} {2} {3} }
{ {1 2} {2 1} {1 3} }
{ {1 2 3} {2 1 3} {1 2 4} }

Мне нужно удалить неуникальную комбинацию целых чисел, поэтому, например, второй элемент списка выше должен стать 

{ { 1 2 } {1 3} }

Это большой объект, поэтому я пытаюсь обновить каждый элемент внешнего списка по ссылке. Я пробовал что-то вроде: 

lit = z.begin();
for (i = 0; i < nlevel; i++) {
    distinct_z(*lit, primes);
    lit++;
}

, где distinct_z - это функция для поиска уникальных векторных комбинаций по ссылке, но, похоже, это не влияет на список z. Примечание: distinct_z отлично работает в другой части моего кода, где я уже работаю с i-м элементом списка. Я предоставил distinct_z ниже. Он включает в себя некоторые уникальные типы данных из пакета R cpp в R, но, надеюсь, понятен. По сути, я использую логарифмическую сумму простых чисел для определения неуникальных комбинаций целых чисел, потому что порядок целых чисел не имеет значения. Повторим, что distinct_z работает в другой части моего кода, где я передаю фактический список векторов целых чисел. Кажется, проблема в том, что я пытаюсь передать что-то с помощью итератора. 

void distinct_lz(std::list<std::vector<int>> &lz,
                      const IntegerVector &primes) {
  int i, j, npids = lz.size();

  NumericVector pids(npids);
  std::list<std::vector<int>>::iterator lit = lz.begin();
  int z_size = lit -> size();
  for(i = 0; i < npids; i++) {
    for (j = 0; j < z_size; j++) {
      // cprime = primes[lit -> at(j)];
      // pids[i] += log(cprime);
      // cprime = primes[lit -> at(j)];
      pids[i] += log(primes[lit -> at(j)]);
    }
    lit++;
  }
  LogicalVector dup = duplicated(round(pids, 8));
  lit = lz.begin();
  for(i = 0; i < npids; i++) {
    if(dup(i) == 1) {
      lz.erase(lit);
    }
    lit++;
  }
}

Каков наилучший подход для выполнения того, что я хочу?

Справочная информация: структура данных, вероятно, кажется излишне сложный, но я перечисляю все связанные подграфы, начиная с вершины, используя подход в ширину. Итак, учитывая текущий подграф, я вижу, какие другие вершины связаны, чтобы создать набор новых подграфов и повторить. Первоначально я делал это, используя список векторов целых, но удаление повторов было смехотворно медленным из-за того, что мне пришлось копировать текущий объект, если я удалил часть вектора. Этот подход намного быстрее, хотя структура более сложная.

Редактировать: Вот решение, которое в основном делает то, что я хочу, хотя это приводит к некоторому нежелательному копированию. Я обновил distinct_z, чтобы вернуть копию объекта вместо изменения ссылки, а затем заменил элемент на lit. 

  lit = z.begin();
  for (i = 0; i < nlevel; i++) {
    (*lit) = distinct_z(*lit, primes);
    lit++;
  }

1 Ответ

1 голос
/ 29 января 2020

В C ++ существует хорошо известная идиома, известная как erase-remove idiom для удаления элементов из контейнера STL. В основном это включает в себя перетаскивание нежелательных элементов в конец контейнера, а затем стирание нежелательного хвоста.

Мы можем использовать функцию предиката (например, лямбду), чтобы выбрать элементы, которые мы хотим стереть, и использовать функции из <algorithm> , В вашем случае мы используем набор множеств (std::<set<int>>) для хранения уникальных комбинаций. Преобразуйте каждый вектор в списке в набор целых чисел и удалите его, если раньше его не видели. 

#include <set>
#include <list>
#include <vector>
#include <algorithm>
#include <iostream>

void distinct_lz(std::list<std::vector<int>>& lz)
{
    std::set<std::set<int>> unqiueNums;

    lz.erase(std::remove_if(lz.begin(), lz.end(),
        [&unqiueNums](std::vector<int>& v) {
            std::set<int> s{ v.cbegin(), v.cend() };
            if (unqiueNums.find(s) != unqiueNums.end())
                return true;
            else
            {
                unqiueNums.insert(s);
                return false;
            }
        }), lz.end());

}

int main()
{
    std::list<std::vector<int>> lv = { {1, 2}, {2, 1}, {1, 3}, {3,4} };
    distinct_lz(lv);
    for (auto &v: lv)
    {
        for( auto n: v)
        {
            std::cout << n << " ";
        }

        std::cout << "\n";
    }
}

Вывод:

1 2 1 3 3 4

Рабочая версия здесь .

...