CODEWITHSUNDEEP
c++searchstl
unnamed
unnamed

Reputation: 856

How to get the min value of an object in a list (C++)

I've a question to ask.

So, I have a structure call Node as shown below:

struct Node
{
    int xKoor, yKoor;

    Node *parent;                                                                   
    char nodeId;                                                                    

    float G;
    float H;
    float F;

    Node(int x, int y, int id, Node * par)
    {
        xKoor = x;
        yKoor = y;
        nodeId = id;
        parent = 0;
    }

    Node(int x, int y, char id)                                                     
    {
        xKoor = x;
        yKoor = y;
        nodeId = id;
    }
};

And I have list that contains elements of this structure:

list<Node*> OPEN;

This list's size varies in time.

What I need to do is to find the Node object which has the minimum F value, then pop out that object from the list.

So, I tried to write a function as shown below:

void enKucukFliNodeBul(list<Node*> OPEN)
{

    list<Node*>::iterator it = OPEN.begin();

    for(it = OPEN.begin(); it != OPEN.end(); it++)
    {
        if(it._Ptr->_Myval->F < it._Ptr->_Next->_Myval->F)
        {

        }
    }
}

But I'm stuck. I'm new to STL. How can I solve this?

My best regards...

Upvotes: 0

Views: 3610

Answers (3)

billz
billz

Reputation: 45410

use std::min_element algirithm and overload Compare function

bool compareF(Node *lhs, Node *rhs) 
{
 return lhs->F < rhs->F; 
}

if you are using C++03:

std::<Node*>::itertor ter = std::min_element(OPEN.begin(),OPEN.end(), compareF);

if you are using C++11:

auto iter = std::min_element(OPEN.begin(),OPEN.end(), compareF);

To sort the list, you can call OPEN.sort(compareF); to sort your list with compareF function

Upvotes: 2

juanchopanza
juanchopanza

Reputation: 227390

You can use std::min_element with a suitable comparison function for this.

bool nodeComp(const Node* lhs, const Node* rhs) {
  return lhs->F < rhs->F;
}


#include <algorithm> // for std::min_element

list<Node*>::iterator it = std::min_element(OPEN.begin(), OPEN.end(), nodeComp);

This assumes that list<Node*> is std::list<Node*>, in which case you should be aware that std::list itself is a linked list.

Other useful operations, based on your comments:

Remove a minimum value node from the list and delete it:

OPEN.erase(it);
delete *it; //

You may need to perform other operations, if your nodes depend on each other.

Sort the list:

OPEN.sort(nodeComp);

Upvotes: 6

nurettin
nurettin

Reputation: 11736

Try adding this:

bool compare_node_F(Node* n1, Node* n2)
{
  return n1-> F< n2-> F;
}

#include <list>
#include <algorithm>
#include <cstdlib>
#include <iostream>

int main()
{
  std::list<Node*> nodes;
  for(int i= 100; i--;)
  {
    Node* n= new Node(42, 42, 42);
    n-> F= i;
    nodes.push_back(n);
  }
  std::list<Node*>::iterator min_element_iter= std::min_element(nodes.begin(), nodes.end(), compare_node_F);
  std::cout<< "Min F: "<< (*min_element_iter)-> F<< '\n';
  for(std::list<Node*>::iterator d= nodes.begin(); d!= nodes.end(); ++ d)
    delete *d;
}

Upvotes: 1

Related Questions