adding to vector of vector<int>, check if element already present
I have a vector<vector<int> > that I am adding data to,
Code:
vector<vector<int> > new_set_of_paths;
// to each path1[i], add a neighbor of last_vertex
for(j=0; j<last_vertex_delta; j++) {
current_neighbor = vertex_list[last_vertex_in_path].neighbor_numbers[j];
new_set_of_paths[path_count].push_back( current_neighbor );
path_count ++;
}
I need to do two things.:
1. check if "current_neighbor" is already a member of new_set_of_paths[path_count][i,j,k]
2. if it is already a member, delete new_set_of_paths[path_count] from the vector<vector<int>>, slide up the remaining elements, re-size, etc.
I'm sure I could do this by looping, checking, copying, etc, but I'm sure an algorithm would be better. I sure I could locate using find or find_if, but when I have done this before, I was deleting the element, but in this case, I need to delete the entire vector. This is complicated because the vector is stored in another vector.
I have tried,
Code:
vector<vector<int> > new_set_of_paths;
vector<int>::iterator path_iterator;
// to each path1[i], add a neighbor of last_vertex
for(j=0; j<last_vertex_delta; j++) {
current_neighbor = vertex_list[last_vertex_in_path].neighbor_numbers[j];
// search path to see if new vertex is already present
path_iterator = find(new_set_of_paths[path_count].begin(),
new_set_of_paths[path_count].end(),
current_neighbor);
cout << "current_neighbor " << current_neighbor << endl;
cout << "path_iterator " << path_iterator << endl;
new_set_of_paths[path_count].push_back( current_neighbor );
path_count ++;
}
but this doesn't compile. I am getting
Code:
In function `std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > add_vertex_to_path(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >&, const int&)':
src/src_client_main/internal_hbond_get_path.cpp:287: error: no match for 'operator<<' in 'std::operator<< [with _Traits = std::char_traits<char>](((std::basic_ostream<char, std::char_traits<char> >&)(&std::cout)), ((const char*)"path_iterator ")) << path_iterator'
Any suggestions?
LMHmedchem
Re: adding to vector of vector<int>, check if element already present
The problem, in plain English, is that the output stream has no idea how to output a path_iterator.
Code:
cout << "path_iterator " << path_iterator << endl;
Regards,
Paul McKenzie
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
Paul McKenzie
The problem, in plain English, is that the output stream has no idea how to output a path_iterator.
Code:
cout << "path_iterator " << path_iterator << endl;
Regards,
Paul McKenzie
Yes, I forgot to make the output a pointer.
This sort of gets me going,
Code:
vector<vector<int> > new_set_of_paths;
vector<int>::iterator path_iterator;
vector<int> check_path;
for(j=0; j<last_vertex_delta; j++) {
current_neighbor = vertex_list[last_vertex_in_path].neighbor_numbers[j];
if(path_length > 2) {
check_path = new_set_of_paths[path_count];
// search path to see if new atom is already part of path
path_iterator = find(check_path.begin(),
check_path.end(),
current_neighbor);
cout << "last_atom_in_path " << last_atom_in_path << endl;
cout << "current_neighbor " << current_neighbor << endl;
cout << "path_iterator " << * path_iterator << endl;
cout << endl;
}
if(path_iterator == 0) {
new_set_of_paths[path_count].push_back( current_neighbor );
path_count ++; //
}
check_path.clear();
}
I don't seem to know how to evaluate if the iterator indicates that it found a match. I can't do, if(path_iterator == 0), or if(*path_iterator == 0), and I also tried if(path_iterator > check_path.end()) and a few similar things. I can't seem to find a reference that shows how to evaluate an iterator. The * iterator value prints as 0 when a match isn't found, but I can't seem to get the syntax for working that into the conditional.
LMHmedchem
Re: adding to vector of vector<int>, check if element already present
What is "path_count"? Where does it come from? Also, why do you need to keep a count? Why are you not iterating over a range instead of trying to "hand_count" using path_count?
In other words:
Code:
for_each(new_set_of_paths.begin(),
new_set_of_paths.end(), whatever);
The "whatever" can be ironed out later, but is this what your major loop (which you didn't show us) consist of?
Regards,
Paul McKenzie
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
LMHmedchem
I don't seem to know how to evaluate if the iterator indicates that it found a match.
Use std::find_if(), not std::find().
Then you check the return iterator is equal to check_path.end(). If it is, then the item was not found.
Regards,
Paul McKenzie
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
Paul McKenzie
Use std::find_if(), not std::find().
Then you check the return iterator is equal to check_path.end(). If it is, then the item was not found.
Regards,
Paul McKenzie
Find_if returns an iterator to an element if that element returns as true from some second function, right? That second function would have to test equality against the elements in the vector being checked, but I'm not sure what that would look like.
LMHmedchem
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
Paul McKenzie
What is "path_count"? Where does it come from? Also, why do you need to keep a count? Why are you not iterating over a range instead of trying to "hand_count" using path_count?
In other words:
Code:
for_each(new_set_of_paths.begin(),
new_set_of_paths.end(), whatever);
The "whatever" can be ironed out later, but is this what your major loop (which you didn't show us) consist of?
Regards,
Paul McKenzie
I am looping on all the neighbors of a vertex as a means of building a path (in the graph sense). The number of branches at a vertex is equal the the number of neighbors-1, since you don't want to go backwards. I need to loop on the number of neighbors, but I am always creating one less path then the number of neighbors. This means I can't use the loop iterator to assign where in new_set_of_paths[] the new path will be added. This code is repeated for each branch point, so the total number of paths of a given length (starting from a given vertex) is something that needs to accumulate if the data is to be assigned in the way I set it up. Keeping an independent count is the first thing that came to mind for doing this.
I am sure there are other ways to do this, and I'm sure you will notice a conspicuous lack of algorithms, iterators, objects, and functors in my code. I never seem to get much past containers and do loops. I only have a bit more to get this working, more or less, and then I will post a longer version of the algorithm for comment.
LMHmedchem
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
LMHmedchem
Find_if returns an iterator to an element if that element returns as true from some second function, right? That second function would have to test equality against the elements in the vector being checked, but I'm not sure what that would look like.
LMHmedchem
Looking at your code again, you can use std::find. The issue is this:
Quote:
I don't seem to know how to evaluate if the iterator indicates that it found a match. I can't do, if(path_iterator == 0), or if(*path_iterator == 0), and I also tried if(path_iterator > check_path.end())
You compare the iterator to end(). You do not compare to 0, or compare of the iterator is > end().
Code:
SomeIterator = std::find(container.begin(), container.end(), whatever);
if ( SomeIterator != container.end() )
{
// the item exists, and it is *SomeIterator
}
else
{
// the item doesn't exist
}
Iterators are not guaranteed to be integral values, so you can't compare them to 0 or use operator > to compare "greater". Even if the iterator is an integral type, there is no guarantee that the last item in the sequence is "greater than" another item. For example, std::deque() is more or less a data structure broken up in chunks, but acts like an array, so you can't compare using "greater than".
That leaves us with one thing -- comparing if the iterator is equal or not equal some other iterator and that is what the code in red does.
Regards,
Paul McKenzie
Re: adding to vector of vector<int>, check if element already present
Thanks, I'm making some progress. I am working under the assumption that I can use the individual row of my vector<vector<int>> as I would any container,
Code:
path_iterator = find(new_set_of_paths[path_count].begin(),
new_set_of_paths[path_count].end(),
current_neighbor);
meaning that I don't have to copy out the data into a regular vector<int>.
It is working more or less, but I need to remove rows of the <vector<int>> that I'm not going to add to. Right now, it is crashing because the rows are still there. This code searches the current row of new_set_of_paths[] to see if a vertex is already present in the path. If the vertex is not already there, it is added, if not it is skipped.
Code:
vector<vector<int> > new_set_of_paths;
if(new_set_of_paths.size() != 0) {
// iterator for vector search
vector<int>::iterator path_iterator;
// to each path1[i], add a neighbor of last_atom
for(j=0; j<last_vertex_delta; j++) {
// lookup value of next neighbor to possibly add
current_neighbor = vertex_list[last_vertex_in_path]neighbor_numbers[j];
// check to make sure that any added vertex is not already in the path
// prevents moving backwards and through ring closures
path_iterator = find(new_set_of_paths[path_count].begin(),
new_set_of_paths[path_count].end(),
current_neighbor);
// new verticies are added to path_temp[path_count] because not all
// verticies are added and the total is cumulative over all branches
if(path_iterator != new_set_of_paths[path_count].end()) {
cout << "don't add " << current_neighbor << endl;
} else {
cout << "do add " << current_neighbor << endl;
new_set_of_paths[path_count].push_back( current_neighbor );
path_count ++; //
}
}
}
I need to add code to the don't add part of the conditional that would remove new_set_of_paths[path_count] row from the new_set_of_paths vector. It's more complex than that, because I actually don't want removal in every case, but I do need to figure out the syntax for removal when I do need it.
I have tried,
Code:
int erase_at = path_count-1;
new_set_of_paths.erase(new_set_of_paths.begin()+erase_at);
but I'm not sure that's right. I need to work a bit on when to do this and when not to because I'm sure it will go boom if I don't pay attention to that. I know erase can foul up iterator values, but I'm not sure it that is an issue here or not.
LMHmedchem
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
LMHmedchem
It is working more or less, but I need to remove rows of the <vector<int>> that I'm not going to add to. Right now, it is crashing because the rows are still there.
OK. One question:
Can you determine by scanning the vector what needs to be removed without removing anything? In other words, instead of trying to go through each element, checking, and then removing (using erase), can you go through the entire vector, know which elements you want to remove, and "mark" them as elements you want to remove without actually erasing them?
If so, then use
1) std::remove_if() / vector::erase() combination if all you want to do is erase the items from the vector
OR
2) std::stable_partition() / vector::erase() if you want to do something to the removed items before erasing them.
By scanning the vector and rearranging the vector so that the items to remove are at the end of the vector, instead of trying to go one-by-one erasing them makes the code much more stable. But you need to determine if scanning the entire vector first is possible with what you want to do.
Regards,
Paul McKenzie
Re: adding to vector of vector<int>, check if element already present
What I need to remove is an entire vector from a vector<vector<int>>. I guess this could be thought of as a single element of the vector<vector<int>>.
for example, where
new_set_of_paths.size() = 2
new_set_of_paths[0][17, 19, 21]
new_set_of_paths[1][17, 19, 20]
current_neighbor = 21;
I am checking current_neighbor against the values in new_set_of_paths[0] and new_set_of_paths[1]. If 21 is found in either vector, than that vector needs to be removed,
new_set_of_paths.size() = 1
new_set_of_paths[0][17, 19, 20]
new_set_of_paths[1] needs to be deleted and new_set_of_paths needs to be renumbered, etc.
I think this is the last thing I need to do to get the code working in the general sense. I will post it once I get that far. If you would like to see more at this point, let me know.
LMHmedchem
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
LMHmedchem
What I need to remove is an entire vector from a vector<vector<int>>. I guess this could be thought of as a single element of the vector<vector<int>>.
Given your description, I wrote this test program:
Code:
#include <vector>
#include <algorithm>
typedef std::vector<int> IntVect;
typedef std::vector<IntVect> IntVect2D;
struct PathRemover
{
PathRemover(int val) : m_val(val) {}
bool operator()(const IntVect& v) const
{
// if m_val is in this vector, mark it to be removed
return std::find(v.begin(), v.end(), m_val) != v.end();
}
int m_val;
};
int main()
{
// Test data
int data1[] = {17, 19, 21};
int data2[] = {17, 19, 20};
// Here is our 2d vector
IntVect2D new_set_of_paths(2);
// Set our test data
new_set_of_paths[0] = IntVect(data1, data1 + 3);
new_set_of_paths[1] = IntVect(data2, data2 + 3);
// remove the item with 21 in it.
new_set_of_paths.erase(std::remove_if(new_set_of_paths.begin(), new_set_of_paths.end(), PathRemover(21)), new_set_of_paths.end());
}
At the end, you will see that the path with 21 is removed.
Regards,
Paul McKenzie
Re: adding to vector of vector<int>, check if element already present
I am having some issues compiling. I am getting the following error,
Code:
In function `std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > add_atoms_to_path(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >&, const int&)':
src/src_client_main/internal_hbond_get_path.cpp:255: error: expected `,' or `...' before '&' token
src/src_client_main/internal_hbond_get_path.cpp:256: error: ISO C++ forbids declaration of `IntVect' with no type
src/src_client_main/internal_hbond_get_path.cpp: In member function `bool add_atoms_to_path(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >&, const int&)::PathRemover::operator()(int) const':
src/src_client_main/internal_hbond_get_path.cpp:258: error: `v' undeclared (first use this function)
src/src_client_main/internal_hbond_get_path.cpp:258: error: (Each undeclared identifier is reported only once for each function it appears in.)
src/src_client_main/internal_hbond_get_path.cpp: In function `std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > add_atoms_to_path(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >&, const int&)':
src/src_client_main/internal_hbond_get_path.cpp:347: error: no matching function for call to `remove_if(__gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> >*, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > >, __gnu_cxx::__normal_iterator<std::vector<int, std::allocator<int> >*, std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > > >, add_atoms_to_path(std::vector<std::vector<int, std::allocator<int> >, std::allocator<std::vector<int, std::allocator<int> > > >&, const int&)::PathRemover)'
With my line numbering,
Code:
struct PathRemover // 252
{ // 253
PathRemover(int val) : m_val(val) {} // 254
bool operator()(const IntVect& v) const // 255
{ // 256
// if m_val is in this vector, mark it to be removed // 257
return std::find(v.begin(), v.end(), m_val) != v.end(); // 258
} // 259
// 260
int m_val; // 261
}; // 262
new_set_of_paths.erase(std::remove_if(new_set_of_paths.begin(), // 345
new_set_of_paths.end(), // 346
PathRemover(current_neighbor)), // 347
new_set_of_paths.end()); // 348
It seems the issue is primarily with the v. vector in the struct.
LMHmedchem
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
LMHmedchem
I am having some issues compiling. I am getting the following error,
The code I posted compiles successfully in Comeau C++ and Visual Studio 2010.
Where are these lines?
Code:
typedef std::vector<int> IntVect;
typedef std::vector<IntVect> IntVect2D;
I used typedefs, because it's easier to deal with rather than those long definitions.
Regards,
Paul McKenzie
Re: adding to vector of vector<int>, check if element already present
Quote:
Originally Posted by
Paul McKenzie
The code I posted compiles successfully in Comeau C++ and Visual Studio 2010.
Where are these lines?
Code:
typedef std::vector<int> IntVect;
typedef std::vector<IntVect> IntVect2D;
I used typedefs, because it's easier to deal with rather than those long definitions.
Regards,
Paul McKenzie
You're right, it does compile. I was trying to put the struct in a .h file, but I don't think I had all the includes and the typedefs in the right place.
This seems to be working and giving me the output I want, so I will post a more complete version of what I'm trying to get done.
LMHmedchem
