Найти значения, которые повторяются ровно один раз в векторе - PullRequest
Новая
       9

Найти значения, которые повторяются ровно один раз в векторе

0 голосов
/ 11 апреля 2020

У меня есть тетраэдрическое я sh как вектор точек (std::array<double, 3>) и вектор тетраэдров (std::array<int, 4>). Я хочу проверить, принадлежит ли конкретная вершина границе me sh.

Для этого каждый тетраэдр определяет 4 грани ([0,1,2], [0,1,3], [1,2,3] и [0,2,3]). Лицо [0,1,2] считается равным лицу [0,2,1] или любой другой перестановке. Лицо - это граница, если она существует только один раз во всем мне sh. Внутренние лица появляются дважды. Вершина является границей, если она принадлежит граничной грани.

Мой план состоит в том, чтобы создать вектор всех граней (std::array<int, 3>), а затем удалить записи, которые появляются дважды. Я хочу удалить обе записи, если они появляются дважды, а не только повторную. Кроме того, компаратор равенства должен уметь обнаруживать эквивалентность двух граней с учетом возможных перестановок.

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

1 Ответ

1 голос
/ 11 апреля 2020

Все сводится к созданию функций сравнения, которые обрабатывают перестановки значений в контейнере как равные.

Концепция для этого заключается в следующем:

  • Скопируйте значения из контейнеров какими бы они ни были, в std::vector
  • Затем сортируйте std::vector s
  • Затем используйте существующую функцию сравнения из std::vector

Как Например, я создал обобщенную c лямбду, которая будет выполнять эту задачу. Пожалуйста, смотрите: 

auto cmpPermLess = [](const auto& c1, const auto& c2) -> bool { 
    std::vector v1(c1.begin(), c1.end());
    std::vector v2(c2.begin(), c2.end());
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    return v1 < v2;
};

Аналогичный подход можно использовать и для других сравнений.

Конечно, вы также можете определить простые другие операторные перегрузки или функции сравнения. Но механизм всегда один и тот же. Скопируйте параметры в std::vector s, затем отсортируйте их, а затем сравните std::vectors.

Теперь я покажу некоторый код драйвера для проверки всего этого: 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <array>
#include <iterator>

// A generic Lambda for comparing containers and ignoring permutations
// Less than
auto cmpPermLess = [](const auto& c1, const auto& c2) -> bool { std::vector v1(c1.begin(), c1.end());
    std::vector v2(c2.begin(), c2.end());
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    return v1 < v2;
};
// Equal 
auto cmpPermEqual = [](const auto& c1, const auto& c2) -> bool {    std::vector v1(c1.begin(), c1.end());
    std::vector v2(c2.begin(), c2.end());
    std::sort(v1.begin(), v1.end());
    std::sort(v2.begin(), v2.end());
    return v1 == v2;
};

// Example for Face definition
using Face = std::array<int, 3>;

// Example for a less than operator for Face
bool operator<(const Face& f1, const Face& f2) { return cmpPermLess(f1, f2); };

// Some test code for syntax check.
int main() {

    // Define a vector with Faces
    std::vector<Face> vf{ {0,1,2},{0,1,3},{1,2,0},{3,1,0},{1,2,3},{0,3,1},{1,3,0}};

    std::cout << "\n\nOriginal Vector:\n";
    for (const Face& f : vf) std::cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';

    // And some standalong faces
    Face f1{ 2,1,0 }, f2{ 0,1,3 };

    // Check less than operator 
    if (f1 < f2) {
        std::cout << "\n\nF1 is less then F2\n";
    }

    // Check comparator for usage in algorithms
    std::sort(vf.begin(), vf.end(), cmpPermLess);

    std::cout << "\n\nSorted vector:\n";
    for (const Face& f : vf) std::cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';


    // And check COmparator for usage in other containers
    std::set<Face, decltype(cmpPermLess)> sf(vf.begin(),vf.end());

    std::cout << "\n\nSet with unique elements:\n";
    for (const Face& f : sf) std::cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';

    // Check comparator for usage in algorithms
    std::sort(vf.begin(), vf.end(), cmpPermLess);

    std::cout << "\n\nSorted vector:\n";
    for (const Face& f : vf) std::cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';

    // Now the vector is sorted. Search doubles and delete them
    for (std::vector<Face>::iterator it = std::adjacent_find(vf.begin(), vf.end(), cmpPermEqual); 
        it != vf.end(); 
        it = std::adjacent_find(vf.begin(), vf.end(), cmpPermEqual)) {

            vf.erase(it, it + 2);
    }

    std::cout << "\n\nDoubles eliminated:\n";
    for (const Face& f : vf) std::cout << f[0] << ' ' << f[1] << ' ' << f[2] << '\n';

    return 0;
};

В конце Из функции main вы также увидите, как мы можем исключить двойные числа. И оба. Мы сортируем вектор и затем используем std::adjacent_find, чтобы увидеть, есть ли у нас 2 двойных, один под другим. Если так, мы стираем их обоих. Это мы повторяем до тех пор, пока больше не будет двойников.

...