<Vector> Find function why is the return value wrong?

[Sims]

Hi,

I have a structure as follow

struct sIntStructure
{
int m_nNumber;
//
// A few more variables
//
}

And a sort class

class less_number : public std::binary_function< sIntStructure,
sIntStructure, bool>
{
public:
less_number(){};
bool operator()( sIntStructure const &lhs, sIntStructure const &Rhys ) const
{
return lhs.m_nNumber< rhs.m_nNumber;
}
};

And the vector itself.

typedef std::vector< sIntStructure , std::allocator<sIntStructure > >
sIntStructure_VECTOR;
sIntStructure_VECTOR m_stv;

//
// ...
//

Now if i am looking for a number i do something like

int FindNumber( int nNumber )
{
// Sort it first
std::sort( m_stv.begin(), m_stv.end(), less_number() );

// and then find it
sIntStructure st;
st.m_nNumber = nNumber;
std::vector< sIntStructure >::iterator i = std::lower_bound(
m_stv.begin(), m_stv.end(), st, less_number() );
if( i == m_stv.end() )
return-1;

if( nNumber != i->m_nNumber ) //
<<<<<<<<<<<<<<<< Needed?
return-1;

int ret = std::distance( m_stv.begin(), i );

return ret;
}

Am i doing something wrong?
Sometimes the line 'ret' value is incorrect, (and not equal to -1), but why?

I suspect that the Find function actually returns the nearest match, is that
true?
Is my code optimised enouth?

Regards,

Sims

 

[Cy Edmunds]

Hi,

I have a structure as follow

struct sIntStructure
{
int m_nNumber;
//
// A few more variables
//
}

And a sort class

class less_number : public std::binary_function< sIntStructure,
sIntStructure, bool>
{
public:
less_number(){};
bool operator()( sIntStructure const &lhs, sIntStructure const &Rhys ) const
{
return lhs.m_nNumber< rhs.m_nNumber;
}
};

And the vector itself.

typedef std::vector< sIntStructure , std::allocator<sIntStructure > >
sIntStructure_VECTOR;
sIntStructure_VECTOR m_stv;

Try to avoid using global variables if there is a reasonable alternative.

//
// ...
//

Now if i am looking for a number i do something like

int FindNumber( int nNumber )
{
// Sort it first
std::sort( m_stv.begin(), m_stv.end(), less_number() );

// and then find it
sIntStructure st;
st.m_nNumber = nNumber;
std::vector< sIntStructure >::iterator i = std::lower_bound(
m_stv.begin(), m_stv.end(), st, less_number() );
if( i == m_stv.end() )
return-1;

if( nNumber != i->m_nNumber ) //
<<<<<<<<<<<<<<<< Needed?
return-1;

int ret = std::distance( m_stv.begin(), i );

return ret;
}

Am i doing something wrong?
Sometimes the line 'ret' value is incorrect, (and not equal to -1), but why?

I suspect that the Find function actually returns the nearest match, is that
true?
Is my code optimised enouth?

Regards,

Sims

What you are trying to do is easy enough:

struct sIntStructure
{
int m_nNumber;
sIntStructure(int i_nNumber = 0) : m_nNumber(i_nNumber) {}
};

bool operator == (const sIntStructure &lhs, const sIntStructure &rhs)
{
return lhs.m_nNumber == rhs.m_nNumber;
}

// note: pass the vector as an argument, not as a global variable
int FindNumber(const std::vector<sIntStructure>&v, int nNumber)
{
typedef std::vector<sIntStructure> t_vec;
t_vec::const_iterator i = std::find(v.begin(), v.end(),
sIntStructure(nNumber));
if (i == v.end())
return -1; // error return: didn't find it
return int(i - v.begin()); // normal return
}

void try_it()
{
typedef std::vector<sIntStructure> t_vec;
t_vec m_stv;
m_stv.push_back(sIntStructure(45));
m_stv.push_back(sIntStructure(17));
m_stv.push_back(sIntStructure(67));
std::cout << FindNumber(m_stv, 17) << '\n'; // output: 1
}

Of course std::find works in linear time which isn't very fast. If you are
planning to do a lot of searches you should probably use std::map instead:

typedef std::map<int, sIntStructure> t_map;
t_map a_map;
a_map[45] = sIntStructure(45);
a_map[17] = sIntStructure(17);
a_map[67] = sIntStructure(67);
sIntStructure &si = a_map[17];

 

[John Harrison]

Am i doing something wrong?
Sometimes the line 'ret' value is incorrect, (and not equal to -1), but

why?

lower_bound returns the first element that is >= to what you are looking
for.

john