Das Feststellen, ob zwei Vektoren zwei benachbarte Elemente enthalten, die gleich sind

Question

Ich habe ein Problem, das darin besteht zu bestimmen, ob zwei Vektorelemente enthalten, die gleich sind. Die Elemente können überall im Vektor sein, aber sie müssen benachbart sein.

FÜR MEHR BEISPIELE BEARBEITET

Zum Beispiel würden die folgenden zwei Vektoren bei Vergleich falsch zurückgeben.

Vektor 1 = [ 0, 1, 2, 3, 4, 6 ]

Vektor 2 = [ 1, 4, 2, 0, 5, 3 ]

Aber die folgenden beiden würden wahr zurückgeben:

Vektor 1 = [ 0, 1, 2, 3, 4, 5 ]

Vektor 2 = [ 4, 2, 1, 5, 0, 3 ]

weil das 1,2 im ersten Vektor mit dem 2,1 im zweiten Vektor übereinstimmen würde.

Wahr:

Vektor 1 = [ 0, 1, 2, 3, 4, 5 ]

Vektor 2 = [ 1, 4, 2, 0, 5, 3 ]

{5,0} ist ein Paar, trotz Rundumloop des Vektors (ich habe ursprünglich gesagt, dass dies falsch ist, vielen Dank, dass du das bemerkt hast, 'Vlad von Moskau').

Wahr:

Vektor 1 = [ 0, 1, 2, 3, 4, 5 ]

Vektor 2 = [ 4, 8, 6, 2, 1, 5, 0, 3 ]

{2,1} ist immer noch ein Paar, auch wenn sie sich nicht an derselben Position befinden

Die tatsächliche Anwendung besteht darin, dass ich ein Polygon (Gesicht) mit N Punkten in einem Vektor habe. Um zu bestimmen, ob eine Reihe von Polygonen ein 3D-Volumen vollständig einschließen, überprüfe ich jedes Gesicht, um sicherzustellen, dass jede Kante von einem anderen Gesicht geteilt wird (wobei eine Kante durch zwei benachbarte Punkte definiert ist).

Also enthält Face einen Vektor von Zeigern auf Punkte...

std::vector points_;

und um zu überprüfen, ob ein Face umgeben ist, enthält Face eine Memberfunktion...

bool isSurrounded(std::vector * neighbours)
{
    int count = 0;
    for(auto&& i : *neighbours)     // für jedes potenzielle Gesicht
        if (i != this)              // das nicht dieses Gesicht ist
            for (int j = 0; j < nPoints(); j++) // und für jeden Punkt in diesem Gesicht
                for (int k = 0; k < i->nPoints(); k++ ) // überprüfen, ob der Nachbarpunkt geteilt wird und ob der nächste Punkt (rückwärts oder vorwärts) auch geteilt wird
                    if ( ( this->at(j) == i->at(k) )        // Punkte sind gleich, prüfen Sie den nächsten und den vorherigen Punkt auch, um ein Paar zu bilden
                       && (    ( this->at((j+1)%nPoints()) == i->at((k+1)%(i->nPoints())) )
                            || ( this->at((j+1)%nPoints()) == i->at((k+i->nPoints()-1)%(i->nPoints())) )))
                        { count++; }
    if (count > nPoints() - 1) // Anzahl der Kanten = nPoints -1
        return true;
    else
        return false;
}

Nun, offensichtlich ist dieser Code schrecklich. Wenn ich in 2 Wochen darauf zurückkomme, werde ich ihn wahrscheinlich nicht verstehen. Angesichts des ursprünglichen Problems, wie würden Sie elegant die beiden Vektoren überprüfen?

Beachten Sie, wenn Sie den bereitgestellten Code entschlüsseln möchten. at(int) gibt den Punkt in einem Gesicht zurück und nPoints() gibt die Anzahl der Punkte in einem Gesicht zurück.

Vielen Dank.

Answer 1

Ich weiß, ich bin ein wenig spät dran damit, aber hier ist meine Meinung dazu:

Nicht in-situ:

#include 
#include 
#include 
#include 

template
class pair_generator {
public:
    explicit pair_generator(std::vector& cont)
    : cont_(cont)
    { }

    template
    bool operator()(T l, T r) {
        cont_.emplace_back(r, l);
        return true;
    }
private:
    std::vector& cont_;
};

template
struct position_independant_compare {

    explicit position_independant_compare(const Pair& pair)
    : pair_(pair)
    { }

    bool operator()(const Pair & p) const {
        return (p.first == pair_.first && p.second == pair_.second) || (p.first == pair_.second && p.second == pair_.first);
    }
private:
    const Pair& pair_;
};

template
using pair_of = std::pair;

template
std::ostream & operator <<(std::ostream & stream, const pair_of& pair) {
    return stream << '[' << pair.first << ", " << pair.second << ']';
}

int main() {
    std::vector
        v1 {0 ,1, 2, 3, 4, 5},
        v2 {4, 8, 6, 2, 1, 5, 0, 3};

    std::vector >
        p1 { },
        p2 { };

    // generate our pairs
    std::sort(v1.begin(), v1.end(), pair_generator>{ p1 });
    std::sort(v2.begin(), v2.end(), pair_generator>{ p2 });

    // account for the fact that the first and last element are a pair too
    p1.emplace_back(p1.front().first, p1.back().second);
    p2.emplace_back(p2.front().first, p2.back().second);

    std::cout << "pairs for vector 1" << std::endl;
    for(const auto & p : p1) { std::cout << p << std::endl; }

    std::cout << std::endl << "pairs for vector 2" << std::endl;
    for(const auto & p : p2) { std::cout << p << std::endl; }

    std::cout << std::endl << "pairs shared between vector 1 and vector 2" << std::endl;
    for(const auto & p : p1) {
        const auto pos = std::find_if(p2.begin(), p2.end(), position_independant_compare>{ p });
        if(pos != p2.end()) {
            std::cout << p << std::endl;
        }
    }
}

Beispiel-Ausgabe auf ideone

In-situ:

#include 
#include 
#include 
#include 
#include 

template
struct in_situ_pair
: std::iterator {

    using pair = std::pair;

    in_situ_pair(std::vector& cont, std::size_t idx)
    : cont_(cont), index_{ idx }
    { }

    pair operator*() const {
        return { cont_[index_], cont_[(index_ + 1) % cont_.size()] };
    }

    in_situ_pair& operator++() {
        ++index_;
        return *this;
    }

    bool operator==(const pair& r) const {
        const pair l = operator*();
        return  (l.first == r.first && l.second == r.second)
                || (l.first == r.second && l.second == r.first);
    }

    bool operator==(const in_situ_pair& o) const {
        return (index_ == o.index_);
    }

    bool operator!=(const in_situ_pair& o) const {
        return !(*this == o);
    }
public:
    friend bool operator==(const pair& l, const in_situ_pair& r) {
        return (r == l);
    }
private:
    std::vector& cont_;
    std::size_t index_;
};

template
using pair_of = std::pair;

template
std::ostream & operator <<(std::ostream & stream, const pair_of& pair) {
    return stream << '[' << pair.first << ", " << pair.second << ']';
}

namespace in_situ {
    template
    in_situ_pair begin(std::vector& cont) { return { cont, 0 }; }

    template
    in_situ_pair end(std::vector& cont) { return { cont, cont.size() }; }

    template
    in_situ_pair at(std::vector& cont, std::size_t i) { return { cont, i }; }
}

int main() {
    std::vector
        v1 {0 ,1, 2, 3, 4, 5},
        v2 {4, 8, 6, 2, 1, 5, 0, 3};

    for(std::size_t i = 0; i < v1.size(); ++i) {
        auto pos = std::find(in_situ::begin(v2), in_situ::end(v2), in_situ::at(v1, i));
        if(pos != in_situ::end(v2)) {
            std::cout << "common: " << *pos << std::endl;
        }
    }
}

Beispiel-Ausgabe auf ideone

Answer 2

Es gab viele großartige Antworten, und ich bin sicher, dass Leute, die nach dem allgemeinen Problem suchen, benachbarte Paare gleicher Elemente in zwei Vektoren zu finden, sie aufschlussreich finden werden. Ich habe beschlossen, meine eigene Frage zu beantworten, weil ich denke, dass eine sauberere Version meines Originalversuchs die beste Antwort für mich ist.

Da es anscheinend keine Kombination von std-Algorithmen gibt, die die Methodik vereinfachen, glaube ich, dass das Durchlaufen und Abfragen jedes Elements am prägnantesten und verständlichsten ist.

Hier ist der Algorithmus für den allgemeinen Fall:

std::vector vec1 = { 1, 2, 3, 4, 5, 6 };
std::vector vec2 = { 3, 1, 4, 2, 6, 5 };

// Schleife über die Elemente im ersten Vektor, auf der Suche nach einem gleichem Element im 2. Vektor
for(int i = 0; i < vec1.size(); i++) for(int j = 0; j < vec2.size(); j++)
    if ( vec1[i] == vec2[j] &&
        // ... Gefundene gleiche Elemente, jetzt prüfen ob das nächste Element mit dem nächsten oder vorherigen Element im anderen Vektor übereinstimmt
        ( vec1[(i+1) % vec1.size()] == vec2[(j+1) % vec2.size()]
        ||vec1[(i+1) % vec1.size()] == vec2[(j-1+vec2.size()) % vec2.size()] ) )
        return true;
return false;

Oder in meinem speziellen Fall, wo ich tatsächlich einen Vektor von Vektoren überprüfe und wo die Elemente nicht mehr ints sind, sondern Zeiger auf eine Klasse.

(Der operator[] der Face-Klasse gibt ein Element eines Vektors zurück, der zur Seite gehört).

bool isSurrounded(std::vector * neighbours)
{
    // Wir können überprüfen, ob jede Kante mit einer Kante in einer benachbarten Fläche übereinstimmt,
    // ... wenn jede Kante übereinstimmt, dann ist die Fläche umgeben
    // ... eine Kante wird durch zwei benachbarte Punkte im points_ Vektor definiert
    // ... daher überprüfen wir, ob zwei aufeinanderfolgende Punkte gleich sind...
    int count = 0;
    // für jede potenzielle Fläche, die nicht diese Fläche ist
    for(auto&& i : *neighbours) if (i != this)
        // ... über beide Vektoren iterieren und nach einem gleichen Punkt suchen
        for (int j = 0; j < nPoints(); j++) for (int k = 0; k < i->nPoints(); k++ )
            if ( (*this)[j] == (*i)[k] &&
                // ... gleiche Punkte wurden gefunden, überprüfen ob auch die nächsten oder vorherigen Punkte übereinstimmen
               (  (*this)[(j+1) % nPoints()] == (*i)[(k+1) % i->nPoints()]
               || (*this)[(j+1) % nPoints()] == (*i)[(k-1+i->nPoints()) % i->nPoints()] ) )
               // ... eine Kante wird geteilt
                { count++; }
    // Anzahl der Kanten = nPoints -1
    if (count > nPoints() - 1)
        return true;
    else
        return false;
}