Partial key match in a map

[Ninan]

I have a map, with a composite key (a struct). I would like to delete
all the elements with a partial key match and may be do other things in
the future. The way I am doing it is as follows. I think this is not
very effecient. I am wondering is there a better way to do this

struct SLNetKey

{

string m_usrid;

string m_portfolio;

string m_symbol;

PorSide m_enSide;

bool operator = (const stLNetRowInfo *row);

};
typedef map<SLNetKey, SLNetData> MapLNet;

typedef map<SLNetKey, SLNetData>::ite rator MapiterLNet;
class CLNetData

{

public:
int DelRowsByUser (const char *user);
private:
MapLNet m_Data;



};

int CLNetData::DelR owsByUser (const char *user)

{

MapiterLNet pREnditer = m_Data.end();

MapiterLNet pBeg = m_Data.end(), pEnd = m_Data.end();

string User = user;

bool bBeg = true;

for (MapiterLNet pRiter = m_Data.begin(); pRiter != pREnditer;
++pRiter) {



if (bBeg && pRiter->first.m_usri d == User)

{

bBeg = false;

pBeg = pRiter;

}

else if (!bBeg)

{

if (pRiter->first.m_usri d != User)

{

pEnd = pRiter;

break;

}

}

}

if (pBeg == m_Data.end())

return -1;

m_Data.erase (pBeg, pEnd);

return 0;



}

//Map comparator function, just for information
bool operator<(const SLNetKey& lhs, const SLNetKey& rhs)

{

if (lhs.m_usrid != rhs.m_usrid)

return lhs.m_usrid < rhs.m_usrid;

if (lhs.m_portfoli o != rhs.m_portfolio )

return lhs.m_portfolio < rhs.m_portfolio ;

if (lhs.m_symbol != rhs.m_symbol)

return lhs.m_symbol < rhs.m_symbol;

return (int)lhs.m_enSi de < (int)rhs.m_enSi de;



}

[mlimber]

Re: Partial key match in a map

Ninan wrote:[color=blue]
> I have a map, with a composite key (a struct). I would like to delete
> all the elements with a partial key match and may be do other things in
> the future. The way I am doing it is as follows. I think this is not
> very effecient. I am wondering is there a better way to do this
>
> struct SLNetKey
>
> {
>
> string m_usrid;
>
> string m_portfolio;
>
> string m_symbol;
>
> PorSide m_enSide;
>
> bool operator = (const stLNetRowInfo *row);
>
> };
> typedef map<SLNetKey, SLNetData> MapLNet;
>
> typedef map<SLNetKey, SLNetData>::ite rator MapiterLNet;
> class CLNetData
>
> {
>
> public:
> int DelRowsByUser (const char *user);
> private:
> MapLNet m_Data;
>
>
>
> };
>
> int CLNetData::DelR owsByUser (const char *user)[/color]

You should make the argument a const string&, and it would
automatically do the conversion for you, making the variable User below
(which should be const, BTW) unnecessary.
[color=blue]
>
> {
>
> MapiterLNet pREnditer = m_Data.end();[/color]

This line is likely premature optimization. If inlining is enabled,
there will most likely be no penalty for retrieving the iterator. If
you keep this, you should at least make it const.
[color=blue]
>
> MapiterLNet pBeg = m_Data.end(), pEnd = m_Data.end();
>
> string User = user;
>
> bool bBeg = true;
>
> for (MapiterLNet pRiter = m_Data.begin(); pRiter != pREnditer;
> ++pRiter) {
>
>
>
> if (bBeg && pRiter->first.m_usri d == User)
>
> {
>
> bBeg = false;
>
> pBeg = pRiter;
>
> }
>
> else if (!bBeg)
>
> {
>
> if (pRiter->first.m_usri d != User)[/color]

There's no reason not to combine these two:

else if( !bBeg && pRiter->first.m_usri d != User )
[color=blue]
>
> {
>
> pEnd = pRiter;
>
> break;
>
> }
>
> }
>
> }[/color]

It might be clearer if you had two loops, one to find pBegin and one to
find pEnd. This would eliminate the boolean bBeg and would make things
simpler.
[color=blue]
>
> if (pBeg == m_Data.end())
>
> return -1;
>
> m_Data.erase (pBeg, pEnd);
>
> return 0;
>[/color]

How about returning the number of elements deleted instead? If not, how
about a bool instead of the more cryptic 0 or -1.
[color=blue]
>
>
> }[/color]

You could use an STL algorithm like find_if
(http://www.sgi.com/tech/stl/find_if.html) or possibly the second
version of equal_range (http://www.sgi.com/tech/stl/equal_range.html ;
n.b., the algorithm's requirements).
[color=blue]
>
> //Map comparator function, just for information
> bool operator<(const SLNetKey& lhs, const SLNetKey& rhs)
>
> {
>
> if (lhs.m_usrid != rhs.m_usrid)
>
> return lhs.m_usrid < rhs.m_usrid;
>
> if (lhs.m_portfoli o != rhs.m_portfolio )
>
> return lhs.m_portfolio < rhs.m_portfolio ;
>
> if (lhs.m_symbol != rhs.m_symbol)
>
> return lhs.m_symbol < rhs.m_symbol;
>
> return (int)lhs.m_enSi de < (int)rhs.m_enSi de;
>
>
>
> }[/color]

Cheers! --M

[Ninan]

Re: Partial key match in a map

find_if and equal_range are for exact key matches, It won't work in
this case. I only know part of the key, ie m_usrid

[mlimber]

Re: Partial key match in a map

Ninan wrote:[color=blue]
> find_if and equal_range are for exact key matches, It won't work in
> this case. I only know part of the key, ie m_usrid[/color]

Please quote the post you are replying to (on Google groups, select
"show options" and click "Reply" in the revealed header); it makes it
easier for others to follow the discussion and thus more likely that
they'll participate.

You can supply your own predicate and comparison functors to those two
functions, so they can be configured to do whatever you want.

Cheers! --M

[TIT]

Re: Partial key match in a map

Ninan sade:[color=blue]
> I have a map, with a composite key (a struct). I would like to delete
> all the elements with a partial key match and may be do other things in
> the future. The way I am doing it is as follows. I think this is not
> very effecient. I am wondering is there a better way to do this
>[/color]
<snip>

Here's possibly a more dynamic and expandable version:
(adjust it at your free will to std::maps)

#include <set>
#include <functional>

#define MULTIKEYDEF(NAM E,TYPE) \
inline TYPE const & NAME() const { return d_##NAME; } \
inline void NAME(TYPE const & t) { d_##NAME = t; } \
TYPE d_##NAME; \
class T##NAME \
: public std::unary_func tion<Tmultikey* ,bool> { \
private: \
TYPE d_compare; \
public: \
T##NAME(TYPE t) : d_compare(t) {} \
T##NAME(T##NAME const & self) \
: d_compare(self. d_compare) {} \
bool operator()(Tmul tikey * mk) { \
return d_compare == mk->##NAME(); \
} \
}

class Tmultikey {
public:
// Actual keys
// Can be accessed through d_primary and d_secondary,
// or primary() and secondary()
MULTIKEYDEF(pri mary , unsigned int);
MULTIKEYDEF(sec ondary, unsigned int);

// Mandatory
bool operator < (Tmultikey const & mk) const {
if(primary() < mk.primary()) return true;
else if(primary() == mk.primary()) {
return secondary() < mk.secondary();
}
return false;
}

// Constructor
Tmultikey(unsig ned int p, unsigned int s)
: d_primary(p), d_secondary(s) {}

// Eraser for std::set
template<typena me Compare>
static void erase(std::set< Tmultikey> & c, Compare op) {
typename std::set<Tmulti key>::iterator pos = c.begin();
while(pos != c.end()) {
if(op(&(*pos))) {
c.erase(pos++);
} else ++pos;
}
}
};

int main(int argc, char* argv[])
{
std::set<Tmulti key> mkset;

mkset.insert(Tm ultikey(1,5));
mkset.insert(Tm ultikey(6,4));
mkset.insert(Tm ultikey(3,7));
mkset.insert(Tm ultikey(1,6));

Tmultikey::eras e(mkset,Tmultik ey::Tsecondary( 4));
Tmultikey::eras e(mkset,Tmultik ey::Tprimary(1) );

// If you have compose_f_gx_hx and siblings (non-standard functions)
// Removes keys where primary is 1 or secondary is 4
Tmultikey::eras e(mkset, compose_f_gx_hx (
std::logical_or <bool>(),
Tmultikey::Tpri mary(1),
Tmultikey::Tsec ondary(4)));

return 0;
}

TIT

[Ninan]

Re: Partial key match in a map


TIT wrote:[color=blue]
> Ninan sade:[color=green]
> > I have a map, with a composite key (a struct). I would like to delete
> > all the elements with a partial key match and may be do other things in
> > the future. The way I am doing it is as follows. I think this is not
> > very effecient. I am wondering is there a better way to do this
> >[/color]
> <snip>
>
> Here's possibly a more dynamic and expandable version:
> (adjust it at your free will to std::maps)
>
> #include <set>
> #include <functional>
>
> #define MULTIKEYDEF(NAM E,TYPE) \
> inline TYPE const & NAME() const { return d_##NAME; } \
> inline void NAME(TYPE const & t) { d_##NAME = t; } \
> TYPE d_##NAME; \
> class T##NAME \
> : public std::unary_func tion<Tmultikey* ,bool> { \
> private: \
> TYPE d_compare; \
> public: \
> T##NAME(TYPE t) : d_compare(t) {} \
> T##NAME(T##NAME const & self) \
> : d_compare(self. d_compare) {} \
> bool operator()(Tmul tikey * mk) { \
> return d_compare == mk->##NAME(); \
> } \
> }
>
> class Tmultikey {
> public:
> // Actual keys
> // Can be accessed through d_primary and d_secondary,
> // or primary() and secondary()
> MULTIKEYDEF(pri mary , unsigned int);
> MULTIKEYDEF(sec ondary, unsigned int);
>
> // Mandatory
> bool operator < (Tmultikey const & mk) const {
> if(primary() < mk.primary()) return true;
> else if(primary() == mk.primary()) {
> return secondary() < mk.secondary();
> }
> return false;
> }
>
> // Constructor
> Tmultikey(unsig ned int p, unsigned int s)
> : d_primary(p), d_secondary(s) {}
>
> // Eraser for std::set
> template<typena me Compare>
> static void erase(std::set< Tmultikey> & c, Compare op) {
> typename std::set<Tmulti key>::iterator pos = c.begin();
> while(pos != c.end()) {
> if(op(&(*pos))) {
> c.erase(pos++);
> } else ++pos;
> }
> }
> };
>
> int main(int argc, char* argv[])
> {
> std::set<Tmulti key> mkset;
>
> mkset.insert(Tm ultikey(1,5));
> mkset.insert(Tm ultikey(6,4));
> mkset.insert(Tm ultikey(3,7));
> mkset.insert(Tm ultikey(1,6));
>
> Tmultikey::eras e(mkset,Tmultik ey::Tsecondary( 4));
> Tmultikey::eras e(mkset,Tmultik ey::Tprimary(1) );
>
> // If you have compose_f_gx_hx and siblings (non-standard functions)
> // Removes keys where primary is 1 or secondary is 4
> Tmultikey::eras e(mkset, compose_f_gx_hx (
> std::logical_or <bool>(),
> Tmultikey::Tpri mary(1),
> Tmultikey::Tsec ondary(4)));
>
> return 0;
> }
>
> TIT[/color]
I have not really followed the compose_f_gx_hx , but I can see one
problem immediatly, when an item is erased from set the iterator
becomes invalid and cannot be incremented.
c.erase(pos++);

[red floyd]

Re: Partial key match in a map

Ninan wrote:[color=blue]
>
> I have not really followed the compose_f_gx_hx[/color]

compose_f_gx_hx comes from Josuttis. He gives examples of some
composition adapters in his library book. Very useful.

compose_f_gx_hx is f(g(x),h(x))

[TIT]

Re: Partial key match in a map

Ninan sade:[color=blue]
> TIT wrote:[/color]
<snip>[color=blue][color=green]
>> // Eraser for std::set
>> template<typena me Compare>
>> static void erase(std::set< Tmultikey> & c, Compare op) {
>> typename std::set<Tmulti key>::iterator pos = c.begin();
>> while(pos != c.end()) {
>> if(op(&(*pos))) {
>> c.erase(pos++);
>> } else ++pos;
>> }
>> }[/color][/color]
<snip>[color=blue][color=green]
>>
>>TIT[/color]
>
> I have not really followed the compose_f_gx_hx , but I can see one
> problem immediatly, when an item is erased from set the iterator
> becomes invalid and cannot be incremented.
> c.erase(pos++);
>[/color]

There is no problem there.

TIT

[TIT]

Re: Partial key match in a map

TIT sade:[color=blue]
> Ninan sade:
>[color=green]
>> TIT wrote:[/color]
>
> <snip>
>[color=green][color=darkred]
>>> // Eraser for std::set
>>> template<typena me Compare>
>>> static void erase(std::set< Tmultikey> & c, Compare op) {
>>> typename std::set<Tmulti key>::iterator pos = c.begin();
>>> while(pos != c.end()) {
>>> if(op(&(*pos))) {
>>> c.erase(pos++);
>>> } else ++pos;
>>> }
>>> }[/color][/color]
>
> <snip>
>[color=green][color=darkred]
>>>
>>> TIT[/color]
>>
>>
>> I have not really followed the compose_f_gx_hx , but I can see one
>> problem immediatly, when an item is erased from set the iterator
>> becomes invalid and cannot be incremented. c.erase(pos++);
>>[/color]
>
> There is no problem there.
>
> TIT[/color]

And in case you don't believe my simple answer let me quote the
actual standard:

23.1.2/8

"[...], and the erase members shall invalidate only iterators
and references to the erased elements"

TIT

[TIT]

Re: Partial key match in a map

TIT sade:[color=blue]
> Ninan sade:
>[color=green]
>> TIT wrote:[/color]
>
> <snip>
>[color=green][color=darkred]
>>> // Eraser for std::set
>>> template<typena me Compare>
>>> static void erase(std::set< Tmultikey> & c, Compare op) {
>>> typename std::set<Tmulti key>::iterator pos = c.begin();
>>> while(pos != c.end()) {
>>> if(op(&(*pos))) {
>>> c.erase(pos++);
>>> } else ++pos;
>>> }
>>> }[/color][/color]
>
> <snip>
>[color=green][color=darkred]
>>>
>>> TIT[/color]
>>
>>
>> I have not really followed the compose_f_gx_hx , but I can see one
>> problem immediatly, when an item is erased from set the iterator
>> becomes invalid and cannot be incremented. c.erase(pos++);
>>[/color]
>
> There is no problem there.
>
> TIT[/color]

And you might want to read about the difference
between postfix and prefix operator++.

TIT