common elements in array and vector

hello everybody
moving on my attempt to program A* pathfinding, i came to a question.
i have an array of 8 objects of a class called Node. this class have two int, "x" and "y"; and i also have a vector of Nodes, which contains the list of all closed nodes.
now i need to check each object in the array to find if its "x" and "y" match with any object in the vector.
this is part of the code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <vector>
#include <queue>

class Node{
public:
    int x, y;
    int f, g, h;
    Node* parent = nullptr;
};

int main(){
    std::vector<Node> closed_nodes;
    std::priority_queue<Node> open_nodes;
    //[...some code...]
    Node new_nodes[8];
    //[...populating the array...]
    for (size_t n=0; n<8; n++){
        //if new_nodes[n].x AND .y are found in any object of closed_nodes, compare the "f" value of both
    }
    return 0;
}


please, let me know if i forgot something or made something unclear. thanks in advance!
Last edited on
//if new_nodes[n].x AND .y are found in any object of closed_nodes, compare the "f" value of both

Do you mean
1
2
3
if(    new_nodes[n].x == closed_nodes.at(/*somewhere*/).x
    && new_nodes[n].y == closed_nodes.at(/*somewhere*/).y) {
    // check if new_nodes[n].f == closed_nodes.at(/*somewhere*/).f 
?

If so, it looks quite simple, doesn’t it? What am I missing?
yes, but /*somewhere*/ could be any element from the closed_nodes array. how to check all of them?

what i'm trying to do is check if my current new_node is already in the closed_node vector. what i got so far:
i changed the line "Node new_nodes[8];" to "std::Vector<Node> new_nodes(8);
1
2
3
4
5
            for (auto & n : new_nodes){
                if(std::find_if(closed_nodes.begin(), closed_nodes.end(), [n] (Node node){return n.x == node.x && n.y == node.y;})){
                    //its already in the closed_nodes vector.
                }
            }


but this returns me the following error:
could not convert ‘std::find_if<__gnu_cxx::__normal_iterator<Node*, std::vector<Node> >, aStar()::<lambda(Node)> >(closed_nodes.std::vector<Node>::begin(), closed_nodes.std::vector<Node>::end(), <lambda closure object>aStar()::<lambda(Node)>{(*(const Node*)(& n))})’ from ‘__gnu_cxx::__normal_iterator<Node*, std::vector<Node> >’ to ‘bool’
but this returns me the following error:

Shouldn’t it? ;-)

Please, have a look at “find_if()” prototype:
http://en.cppreference.com/w/cpp/algorithm/find
1
2
3
template< class InputIt, class UnaryPredicate >
InputIt find_if( InputIt first, InputIt last,
                 UnaryPredicate p );

. . .
Return value
Iterator to the first element satisfying the condition or last if no such element is found


An if statement checks if an expression is true or false and the compiler is informing you it can’t convert the returned iterator into a boolean value.

However, if you fancy some more hints...
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>
#include <vector>

class Node {
public:
    int x, y;
    int f, g, h;
    Node* parent;
    Node();
    Node(int x_arg, int y_arg, int f_arg,
         int g_arg, int h_arg, Node* parent_arg);
    friend std::ostream& operator<<(std::ostream& os, const Node& n)
    {
        return { os << "x: " << n.x << " y: " << n.y << " f: " << n.f << '\n' };
    }
};

Node::Node() : x {}, y {}, f {}, g {}, h {}, parent { nullptr } {}

Node::Node(int x_arg, int y_arg, int f_arg,
           int g_arg, int h_arg, Node* parent_arg)
           : x { x_arg }, y { y_arg }, f { f_arg },
             g { g_arg }, h { h_arg }, parent { parent_arg }
{}

inline bool operator==(const Node& l, const Node& r)
{
    return l.x == r.x && l.y == r.y;
}

int getRndInt(int min, int max);
Node createRndNode(int min, int max);

int main()
{
    constexpr std::size_t NEW_NODES_MAX { 8 };

    std::vector<Node> closed(getRndInt(5, 11));
    std::generate(closed.begin(), closed.end(),
                    []() -> Node { return createRndNode(10, 15); } );

    // For debug only:
    for(const auto& v : closed) { std::cout << "closed: " << v; }

    Node new_nodes[NEW_NODES_MAX];
    for(std::size_t i{}; i < NEW_NODES_MAX; ++i) {
        new_nodes[i] = createRndNode(10, 15);
        // For debug only:
        std::cout << "new_nodes: " << new_nodes[i];
    }

    for (const auto& n : new_nodes) {
        if(closed.end() == std::find_if(closed.begin(),
                                        closed.end(),
                                        [&n] (const Node& a) { return n == a; } ) ) {
            std::cout << "No matches up to here.\n";
        } else {
            std::cout << "One match found\n";
        }
    }
    return 0;
}

int getRndInt(int min, int max)
{
    static std::mt19937 eng { static_cast<unsigned>(
                                std::chrono::high_resolution_clock::now()
                                .time_since_epoch()
                                .count() ) };
    std::uniform_int_distribution<> dis(min, max);
    return dis(eng);
}

Node createRndNode(int min, int max)
{
    return Node(getRndInt(min, max), getRndInt(min, max), getRndInt(min, max), 
                getRndInt(min, max), getRndInt(min, max), nullptr);
}

If you don't mind sorting the array and the vector (or creating a sorted copy of them), and you're willing to write operator< for your Node class so that they can be sorted and compared , something like this perhaps, using std::set_intersection:

1
2
3
4
5
6
7
vector<Node> nodesInBothArrayAndVector;
std::set_intersection(arrayOfNodes, arrayOfNodes + arrayOfNodesSize,
                      vectorOfNodes.begin(), vectorOfNodes.end(),                  
                      std::back_inserter(nodesInBothArrayAndVector));

// Now nodesInBothArrayAndVector contains all the nodes you're looking for

Last edited on
thanks both of you, i think i'm getting close :D
i tried mixing Enoizat's answer with some more things i found. does this feel right?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
            for (auto &n : new_nodes){
                std::vector<Node>::iterator it = std::find_if(closed_nodes.begin(), closed_nodes.end(), [&n] (const Node &node) {return n.x == node.x && n.y == node.y;});
                if(it != closed_nodes.end()){
                    //n's x and y are found in any element in closed_nodes
                    if (n.f < it->f){
                        //and n's f is less than closed_nodes' element's f
                    }
                    else{
                        //n's f is not less than closed_nodes' element's f
                    }
                }
                else{
                    //n's x and y doesn't match any inside closed_nodes vector
                }
            }
Topic archived. No new replies allowed.