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>::iterator MapiterLNet;
class CLNetData

{

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



};

int CLNetData:elRowsByUser (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_usrid == User)

{

bBeg = false;

pBeg = pRiter;

}

else if (!bBeg)

{

if (pRiter->first.m_usrid != 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_portfolio != 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_enSide < (int)rhs.m_enSide;



}

 

[mlimber]

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>::iterator MapiterLNet;
class CLNetData

{

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



};

int CLNetData:elRowsByUser (const char *user)

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.

{

MapiterLNet pREnditer = m_Data.end();

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.

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_usrid == User)

{

bBeg = false;

pBeg = pRiter;

}

else if (!bBeg)

{

if (pRiter->first.m_usrid != User)

There's no reason not to combine these two:

else if( !bBeg && pRiter->first.m_usrid != User )

{

pEnd = pRiter;

break;

}

}

}

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.

if (pBeg == m_Data.end())

return -1;

m_Data.erase (pBeg, pEnd);

return 0;

How about returning the number of elements deleted instead? If not, how
about a bool instead of the more cryptic 0 or -1.

}

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).

//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_portfolio != 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_enSide < (int)rhs.m_enSide;



}

Cheers! --M

 

[Ninan]

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]

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

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]

Ninan sade:

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

<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(NAME,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_function<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()(Tmultikey * 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(primary , unsigned int);
MULTIKEYDEF(secondary, 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(unsigned int p, unsigned int s)
: d_primary(p), d_secondary(s) {}

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

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

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

Tmultikey::erase(mkset,Tmultikey::Tsecondary(4));
Tmultikey::erase(mkset,Tmultikey::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::erase(mkset, compose_f_gx_hx(
std::logical_or<bool>(),
Tmultikey::Tprimary(1),
Tmultikey::Tsecondary(4)));

return 0;
}

TIT

 

[Ninan]

Ninan sade:

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

<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(NAME,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_function<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()(Tmultikey * 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(primary , unsigned int);
MULTIKEYDEF(secondary, 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(unsigned int p, unsigned int s)
: d_primary(p), d_secondary(s) {}

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

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

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

Tmultikey::erase(mkset,Tmultikey::Tsecondary(4));
Tmultikey::erase(mkset,Tmultikey::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::erase(mkset, compose_f_gx_hx(
std::logical_or<bool>(),
Tmultikey::Tprimary(1),
Tmultikey::Tsecondary(4)));

return 0;
}

TIT

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]

I have not really followed the compose_f_gx_hx

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]

Ninan sade:

TIT wrote:

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++);

There is no problem there.

TIT

 

[TIT]

TIT sade:

Ninan sade:


There is no problem there.

TIT

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]

TIT sade:

Ninan sade:


There is no problem there.

TIT

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

TIT