Vector Searching

[Technocrat]

I have the following structures:

struct UTM
{
	string sLID;
	string sCanal;
	string sStation;
	string sOutlet;
	string sService;
	string sTypeCode;
	string sSize;
};

struct LM
{
	string sLID;
	string sStreetNumber;
	string sStreet;
	string sStreetSufix;
};

There are two vectors that uses those:
vector<UTM> vecUTM105AP;
vector<LM> vecLMBAREP;

They both get filled using the same way as my other post . Everything in vecLMBAREP gets sorted by the sLid. Then I uses the following code to see if the vecUTM105AP sLID is in the vecLMBAREP vector.

struct IsSlidEqual
{
    IsSlidEqual( const std::string &s ) : m_s(s) { }
    operator () ( const LM& obj )
    {
        return obj.sLID == m_s;
    }

private:
    std::string m_s;
};

	vector<UTM>::iterator lst;
	for (lst = vecUTM105AP.begin(); lst != vecUTM105AP.end(); lst++)
	{
		UTM* V;
		V = (UTM*)(&(*lst));
		vector<LM>::iterator it = std::find_if( vecLMBAREP.begin(), vecLMBAREP.end(), IsSlidEqual(V->sLID));

		if ( it != vecLMBAREP.end())
		{
			iBC = atoi(V->sLID.c_str());
		}

This works, but the problem I have is it is slow. The vecUTM105AP vector is only ~7700 elements and the other is ~13,000 and it takes 3-4 minutes at least. Granted thats not bad considering but I am going to have another vector that is going to be 34,000 elements and waiting 10-20 minutes is going to suck. Is there a faster/better way to do this?