Rgd: Vector Iterator to get Index Position

Question

This is my iterator position code

struct node {
int nodeid;
vector<fingerTable> fTable;
vector<string> data;
};

vector<node> cNode;

vector<node>::iterator position = find(cNode.begin(),cNode.end(), id);

I got about 100 objects, i am trying to find the index/element/position of e.g nodeid "80" assuming that my object is all sorted in ascending order by nodeid.

my concern is speed and memory usage, i was previously using

for(int i=0;i<cNode.size();i++)
{
//if logic-- match nodeid with the nodeid input.. then assign the i to an integer..
}

but now i am trying to use and iterator, i heard its faster.. any suggestion on getting it fix or is there a better way to find my vector index by its value "nodeid"

i know map is a good std container for my case but i a bit run out of time to do the changes so i got to stick with vector..

vector<node>::iterator position = find(cNode.begin(),cNode.end(), id);

Error output when i try compile the iterator line above.

In member function ‘void chord::removePeer(int)’:
testfile.cpp:532:69: error: no matching function for call to ‘chord::find(std::vector<chord::node>::iterator, std::vector<chord::node>::iterator, int&)’
testfile.cpp:532:69: note: candidate is:
testfile.cpp:177:5: note: int chord::find(int, int, bool)
testfile.cpp:177:5: note:   no known conversion for argument 1 from ‘std::vector<chord::node>::iterator {aka __gnu_cxx::__normal_iterator<chord::node*, std::vector<chord::node> >}’ to ‘int’

@billz i did include , id is an integer, its is unique , distinct and only appear once in the whole vector. its sorted by ascending — user2017011, Feb 17 '13 at 08:34
This question looks a lot like [How can I get vector's index by its data in C++?](http://stackoverflow.com/q/14914985/78845) from 11 hours ago, to which [I replied "`std::find()` runs in linear time (O(n)), the same as your `for`-loop."](http://stackoverflow.com/a/14917460/78845). If you want to run in sub-linear time, use `std::lower_bound()`. — johnsyweb, Feb 17 '13 at 08:54

score 1 · Accepted Answer · answered Feb 17 '13 at 08:44

1

You have a vector of objects. Each object contains an int. You're trying to "find" the object in that vector which has a given value in that int. But the compiler doesn't understand this, because the STL only describes how to find values in containers. And how could it be otherwise? If you had an object containing two ints, which one would be compared?

Since you said the use of std::find() was for better performance than the old-school for-loop, you can stop trying now and just go back to that. The performance will be basically the same either way, and you said already that you're out of time. So just use what you had working, because it's not a performance problem.

If you insist on using iterators, you could use std::find_if() with a custom predicate you'd define, like this:

struct HasId {
    HasId(int id) : _id(id) {}
    bool operator()(node const& n) const { return n.nodeid == _id; }
private:
    int _id;
}

std::find_if(cNode.begin(), cNode.end(), HasId(id));

This way, we have provided enough information to let the STL find the element we're interested in, without creating a temporary node to search for.

answered Feb 17 '13 at 08:44

John Zwinck

239,568
38
324
436

hi , with the find if case, how do i get the return result as the vector[Index] which the Index is what i am seeking for. – user2017011 Feb 17 '13 at 08:51
1

`find_if()` returns an iterator. If it's called `iter` then you can say `*iter` to dereference it and get the same as cNode[index]. If you want to know which index you found, do `iter - cNode.begin()`. – John Zwinck Feb 17 '13 at 08:55
1

why do you need the index? – Thomas Feb 17 '13 at 08:55
@JohnZwinck sorry for asking again. how do i create an iterator for this find if and then do the *iter, do i create an iter of integer type. thanks. I try using the following vector::iterator iter; , then iter = std::find_if(cNode.begin(), cNode.end(), HasId(id)); – user2017011 Feb 17 '13 at 09:02
Please read the second paragraph of my answer: you're better off going back to the code you had that didn't use iterators. There's no benefit in this stuff for you now. – John Zwinck Feb 17 '13 at 09:07
@user2017011: What do you mean by "do i create an iter of integer type"? – johnsyweb Feb 17 '13 at 21:12

score 0 · Answer 2 · answered Feb 17 '13 at 08:43

cNode is a vector of node type but you pass in id(int type), you need an implicit conversion function to convert id to node object:

struct node {
   int nodeid;
   vector<fingerTable> fTable;
   vector<string> data;

    node(int id)
    : nodeid(nodeid)
    {
    }
};

bool operator==(const node& lhs, const node& rhs)
{
  return lhs.nodeid == rhs.nodeid;
}

Now you could call std::find with integer type on node vector:

std::vector<node>::iterator position = std::find(cNode.begin(),cNode.end(), id);

which is equal to:

std::vector<node>::iterator position = std::find(cNode.begin(),cNode.end(), node(id));

With C++11 you could write lambda with std::find_if as alternative way:

auto pos = std::find_if(cNode.begin(), cNode.end(), 
           [id](const node& n){ return n.nodeid == id; } );

score 0 · Answer 3 · edited May 23 '17 at 10:32

nNode is a vector, std::find searches for a value not a key. Use something like std::map<int,node> to find your node.

int id = 0;

typedef std::map<int,node> NodeMap;
NodeMap cNode;

NodeMap::iterator position = cNode.find(id);

If you are doing lots of inserts/deletes, and keeping stuff sorted, choose an appropriate container like map or set.

This is basically C++ How to speed up my prog design again.

if you change node to:

struct node {
    vector<fingerTable> fTable;
    vector<string> data;
};

and change from vector to map

map<int,node> cNode;

then your addPeer really only does this:

void chord::addPeer(int id)
{
    std::map<int, node>::iterator 
    pos = cNode.insert( std::make_pair(id, node() ) ).first;;

    if( pos != cNode.end() )
    {
        ++pos;
        vector<string> data = pos->second.data;
        pos->second.data.clear();
        dataShift( data, fIndex-1 );
    }
}//end addPeer

The only remaining question is what does dataShift do and does it need the index for that?

Rgd: Vector Iterator to get Index Position

3 Answers3

Linked