Find values which are repeated exactly once in a vector

I have a tetrahedral mesh as a vector of points (std::array<double, 3>) and a vector of tetrahedrons (std::array<int, 4>). I want to check if a particular vertex belongs to the boundary of the mesh.

For that, each tetrahedron defines 4 faces ([0,1,2], [0,1,3], [1,2,3] and [0,2,3]). The face [0,1,2] is considered equal as the face [0,2,1] or any other permutation. A face is a boundary if it only exists once in all the mesh. Internal faces appear twice. A vertex is a boundary if it belongs to a boundary face.

My plan is to create a vector of all the faces (std::array<int, 3>) and then remove the entries that appear twice. I want to remove both entries if they appear twice, not only the repeated one. Also, the equality comparator must be capable of detecting if two faces are equivalent, taking into account the possible permutations.

I am not sure how to proceed with this or if storing a vector with all the faces and then removing elements is the best solution. Any ideas would be very helpful.

Solution

It all boils down to create comparison functions that treat permutaions of values in a container as equal.

The concept for doing this is:

Copy the Values from the containers, whatever they are, into a std::vector
Then sort the std::vectors
Then use the existing compare function from the std::vector

As an example, I created a generic lambda that will do this task. Please see:

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;
};

A similar approach can be taken also for other comparisons.

Of course you can also define simple other operator overloads or comparison functions. But the mechanism is always the same. Copy parameters to std::vectors, then sort them, and then compare the std::vectors.

I will show now some driver code to test all this:

#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;
};

At the end, of the function main, you will see also how we can eliminated doubles. And, both of them. We sort the vector and then use std::adjacent_find, to see if we do have 2 doubles, one beneath the other. If so, we erase both of them. This we repeat, until there are no doubles any longer.