How to search for an element in a 2D vector?

[Crouchinho]

Ok guys, I could sure use some help regarding this search methond in C++.

I have a 2D vector which i read from a text file. It looks like this:

000000000
000100001
000010000

The idea here is I have to search for the leftmost '1' in the highest possible row it is present in. I need to be able to find the first '1' in any type of text file like the one i have just shown.

so far, I have declared the iterators for the vector and tried to use the find_first_of function to find the first '1'. but to no avail. Could you please help me with this. Here's my code:

int a = 1;
	vector< vector<int> >::iterator start = block.begin();
	vector< vector<int> >::iterator end = block.end();
	for( ; start != end ; ++start){
		vector<int>::iterator rowst = start->begin();
		vector<int>::iterator rowen = end->end();
		for( ; rowst != rowen; ++rowst){
        rowst = find_first_of(block.begin(), block.end(),vector<int>,a);

		}
	}

Any help would be appreciated.

[iamthwee]

The idea here is I have to search for the leftmost '1' in the highest possible row it is present in.

Explain...

[Crouchinho]

The idea here is I have to search for the leftmost '1' in the highest possible row it is present in.

Explain...

lets say I have a text file as follows:

00000
01010
00011

In this textfile, The 2nd element in the second row contains the first occurence of '1'. I need to design my code in such a way that I shall be able to pick out that first occurence of the '1' and record its vertices. But I can't seem to get it. I hope this helps, please bear with me, I am new to this STL coding.

[iamthwee]

Um...

#include <iostream>
#include <string>
 
using namespace std;
 
int main()
{
  int lines = 3;
  string crap[] = {"0001010010", "01010010100", "010101010"};
  for ( int i = 0; i < lines; i++ )
  {
    for ( int j = 0; j < crap[i].length(); j++ )
    {
      if ( crap[i][j] == '1' )
      {
        cout << "Leftmost \"1\" found at row " << i + 1
              << " column " << j + 1 <<endl; 
 
        cin.get();
      }
    }
  }
  cin.get();
}

??

[Crouchinho]

Yes, that would probably work. But that code looks like its for a specific file. Now my assignment requires me to use the STL algortihms in order to search for the element. I was thinking of using the find_if algorithm, but somehow its is giviing me errors. Any idea on on how to the find_if algorithm?

[iamthwee]

Seems like overkill to me.

What is your assignment can you explain it from the beginning?

[Crouchinho]

Okay, here it is.

We are given a textfile which has a certain number of rows and columns (unspecified number, could be any size). The rows and columns are filled with random '1's and '0's. We have to figure out where the first '1' is and find a simple polygon of which consists of all the '1's in the table. We have to move counter-clockwise around the block to find the blocks containing '1's. we then have to output the vertices of the polygon.

I don't know how clear the program description is, let me know if you need more information.

[Dave Sinkula]

int a = 1;
      typedef std::vector< std::vector<int> >::iterator iter;
      for ( iter it = array.begin(), end = array.end(); it != end ; ++it )
      {
         typedef std::vector<int>::iterator iter2;
         iter2 found = std::find((*it).begin(), (*it).end(), a);
         if ( found != it->end()) 
         {
            std::cout << "row "   << (it - array.begin()) 
                      << ", col " << (found - (*it).begin()) << '\n';
            break;
         }
      }

[Crouchinho]

Thanks a lot Dave!

but I wanted to find out how necessary is this piece of code in the solution?

if ( found != it->end())          {            std::cout << "row "   << (it - array.begin())                       << ", col " << (found - (*it).begin()) << '\n';            break;         }

I am not quite sure what it does.

[iamthwee]

Post a sample text file.

[Dave Sinkula]

Thanks a lot Dave!

but I wanted to find out how necessary is this piece of code in the solution?

if ( found != it->end())          {            std::cout << "row "   << (it - array.begin())                       << ", col " << (found - (*it).begin()) << '\n';            break;         }

I am not quite sure what it does.

We're looping with iterators. For the moment I'll consider them to be pointers. When found isn't a pointer to the end, it points to the location in which a 1 was found. To translate from a pointer into an index, you subtract the found position from the start.

[edit]I tried to choose better names.

int key = 1;
      typedef std::vector< std::vector<int> >::iterator riter;
      for ( riter row = array.begin(), end = array.end(); row != end ; ++row )
      {
         typedef std::vector<int>::iterator citer;
         citer col = std::find(row->begin(), row->end(), key);
         if ( col != row->end() )
         {
            std::cout << "row "   << row - array.begin() 
                      << ", col " << col - row->begin() << '\n';
            break;
         }
      }

[Crouchinho]

heres a sample textfile:

3 4
0000
0100
0110

[iamthwee]

And what are you supposed to do, show the coords of all the '1's that join together so to speak?

Show me an example of another bigger file.

[Crouchinho]

yeah pretty much show the coords of all the '1's that form a polygon

so heres another sample file

5 7
0000000
0111100
0101000
0000000
0000000

The lines between the elements are the coordinates, so for this text file the output I am supposed to show is

[1,1],[3,1],[3,2],[2,2],[2,3],[3,3],[3,4],[2,4],[1,4]

[Dave Sinkula]

I don't quite understand the expected output.

int key = 1;
      typedef std::vector< std::vector<int> >::const_iterator riter;
      for ( riter row = array.begin(), end = array.end(); row != end ; ++row )
      {
         typedef std::vector<int>::const_iterator citer;
         citer col, begin = row->begin(), end = row->end();
         while ( (col = std::find(begin, end, key)) != end )
         {
            std::cout << '[' << row - array.begin() 
                      << ',' << col - row->begin() << "],";
            begin = col + 1;
         }
      }
      std::cout << '\n';

5, 7,
0, 0, 0, 0, 0, 0, 0,
0, 1, 1, 1, 1, 0, 0,
0, 1, 0, 1, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0,
[2,1],[2,2],[2,3],[2,4],[3,1],[3,3],

[Crouchinho]

The coordinates are supposed to be between the elements.

like say for the element 'a' in this sample:

000010
00a000
000000

The 'a' four coordinates around it. Its co-ordinates will be [1,2], [2,2], [2,3] and [1,3]

Its confusing I know. But I hope this helps. we have to find the co-ords around the polygon, however if the 1's are next to each other, their co-ords need not be recorded.

[Dave Sinkula]

Danke. I'm zero-based, so I see the highlighted points corresponding to [1,2],[2,2],[2,3],[1,3].

000010
00a000
000000