 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
benbowc@attglobal.net
Guest
|
 Posted: Thu Sep 15, 2005 10:18 am Post subject: searching a deque of deques using find_if |
 |
|
I was attempting to use the find_if algorithm in my deque of deques to
search for a matching string but I can't seem to figure out how one
does
this?
The terse documentation appears to indicate I should create a
binary function to do the comparison and have it return TRUE for a
match. I can't figure out how to do this. Has anyone got a piece of
code that uses a container class in this manner?
I have got a deque of deques containing structures that contain unique
names. I want to add additional, filled, structures based on the name
string to an existing deque or add a new one when theres no match. If
anyone has a better
solution I'm more than willing to hear it too!
TIA
Craig
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
msalters
Guest
|
| Posted: Thu Sep 15, 2005 1:57 pm Post subject: Re: searching a deque of deques using find_if |
|
|
benb... (AT) attglobal (DOT) net schreef:
| Quote: | I was attempting to use the find_if algorithm in my deque of deques to
search for a matching string but I can't seem to figure out how one
does
this?
The terse documentation appears to indicate I should create a
binary function to do the comparison and have it return TRUE for a
match. I can't figure out how to do this. Has anyone got a piece of
code that uses a container class in this manner?
|
The problem isn't really in the predicate(which is unary, not binary).
find_if finds an element in a linear range [begin,end). You don't have
iterators for such a range. Your strings are 2D, not 1D.
A "simple" solution is to define an iterator that loops over all
strings, continuing with deque[1].begin after deque[0].end
IIRC, such code is publicly available as part of the VTL.
( check out concatenation_view< > )
HTH,
Michiel Salters
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Thu Sep 15, 2005 1:58 pm Post subject: Re: searching a deque of deques using find_if |
|
|
On 15 Sep 2005 06:18:46 -0400, [email]benbowc (AT) attglobal (DOT) net[/email] wrote:
| Quote: | I was attempting to use the find_if algorithm in my deque of deques to
search for a matching string but I can't seem to figure out how one
does this?
I have got a deque of deques containing structures that contain unique
names. I want to add additional, filled, structures based on the name
string to an existing deque or add a new one when theres no match. If
anyone has a better solution I'm more than willing to hear it too!
|
If I understand you, each deque has Things with matching name fields.
Different names go in different deques. You have a Thing and wish to
add it to the deque for matching names or add a new deque for that
name. There will unconditionally be one more Thing in the collection.
struct Thing {
string name;
// ...
};
You wish to use find_if.
struct EqualThingName {
string const& name;
EqualThingName (string const& name) : name(name) {
}
bool operator() (deque<Thing> const& lhs) {
return lhs[0].name == name;
}
};
void addToCollection (deque<deque& ddt, Thing const& t) {
deque<deque::iterator it(find_if(ddt.begin(),
ddt.end(), EqualThingName(t.name)));
if (it != ddt.end())
it->push_back(t);
else
ddt.push_back(deque<Thing>(1, t));
}
You could also use find.
bool operator== (deque<Thing> const& lhs, string const& rhs) {
return lhs[0].name == rhs;
}
void addToCollection (deque<deque& ddt, Thing const& t) {
deque<deque::iterator it(find(ddt.begin(),
ddt.end(), t.name));
if (it != ddt.end())
it->push_back(t);
else
ddt.push_back(deque<Thing>(1, t));
}
Or, you could use the string as the key in a map and let it do
the work for you.
void addToCollection (map<string, deque& mdt,
Thing const& t) {
mdt[t.name].push_back(t);
}
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
benbowc@attglobal.net
Guest
|
| Posted: Fri Sep 16, 2005 1:25 pm Post subject: Re: searching a deque of deques using find_if |
|
|
John Potter wrote:
| Quote: | On 15 Sep 2005 06:18:46 -0400, [email]benbowc (AT) attglobal (DOT) net[/email] wrote:
I was attempting to use the find_if algorithm in my deque of deques to
search for a matching string but I can't seem to figure out how one
does this?
I have got a deque of deques containing structures that contain unique
names. I want to add additional, filled, structures based on the name
string to an existing deque or add a new one when theres no match. If
anyone has a better solution I'm more than willing to hear it too!
If I understand you, each deque has Things with matching name fields.
Different names go in different deques. You have a Thing and wish to
add it to the deque for matching names or add a new deque for that
name. There will unconditionally be one more Thing in the collection.
|
Thats correct.
| Quote: |
struct Thing {
string name;
// ...
};
You wish to use find_if.
struct EqualThingName {
string const& name;
EqualThingName (string const& name) : name(name) {
}
bool operator() (deque<Thing> const& lhs) {
return lhs[0].name == name;
}
};
void addToCollection (deque<deque& ddt, Thing const& t) {
deque<deque::iterator it(find_if(ddt.begin(),
ddt.end(), EqualThingName(t.name)));
if (it != ddt.end())
it->push_back(t);
else
ddt.push_back(deque<Thing>(1, t));
}
Boy I need to take some time to mull this over. |
| Quote: | You could also use find.
bool operator== (deque<Thing> const& lhs, string const& rhs) {
return lhs[0].name == rhs;
}
void addToCollection (deque<deque& ddt, Thing const& t) {
deque<deque::iterator it(find(ddt.begin(),
ddt.end(), t.name));
if (it != ddt.end())
it->push_back(t);
else
ddt.push_back(deque<Thing>(1, t));
}
Bit confused here. Whats the operator for? You don't use it do you? |
| Quote: | Or, you could use the string as the key in a map and let it do
the work for you.
void addToCollection (map<string, deque& mdt,
Thing const& t) {
mdt[t.name].push_back(t);
}
Now this is very tidy. I'll have to spend some time working through |
this and its implications. I had considered a map but wondered about
random access. Is it quick?
The application code may access any member of the container at anytime
in any order. Will this work?
Thanks for the wonderful suggestions. Your skills are well beyond mine
at present.
Craig
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Greg Herlihy
Guest
|
| Posted: Sun Sep 18, 2005 12:05 pm Post subject: Re: searching a deque of deques using find_if |
|
|
msalters wrote:
| Quote: | benb... (AT) attglobal (DOT) net schreef:
I was attempting to use the find_if algorithm in my deque of deques to
search for a matching string but I can't seem to figure out how one
does
this?
The terse documentation appears to indicate I should create a
binary function to do the comparison and have it return TRUE for a
match. I can't figure out how to do this. Has anyone got a piece of
code that uses a container class in this manner?
The problem isn't really in the predicate(which is unary, not binary).
find_if finds an element in a linear range [begin,end). You don't have
iterators for such a range. Your strings are 2D, not 1D.
A "simple" solution is to define an iterator that loops over all
strings, continuing with deque[1].begin after deque[0].end
IIRC, such code is publicly available as part of the VTL.
( check out concatenation_view< > )
HTH,
Michiel Salters
|
For the purposes of this search the data is linear - only the first
element in each deque needs to be checked for a match. Using an
iterator that loops through all the items in all the containers would
make an already inefficient design, an order of magnitude slower still.
Replacing the deque of deques with a map of deques (or vectors) seems
like an obvious improvement. Consider the case in which a new container
must be created. With 64 containers, a linear search through the deque
will have to make 64 comparisons before it decides to create a new one.
A binary search through a std::map would need only 6 comparisons (log2
64) to reach the same conclusion. With 1024 containers, the difference
is 1024 vs. 10 comparisons, a hundredfold difference. At some point the
data set may become large enough that these ratios will make a
difference.
Greg
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
John Potter
Guest
|
| Posted: Sun Sep 18, 2005 1:34 pm Post subject: Re: searching a deque of deques using find_if |
|
|
On 16 Sep 2005 09:25:00 -0400, [email]benbowc (AT) attglobal (DOT) net[/email] wrote:
| Quote: | John Potter wrote:
struct Thing {
string name;
// ...
};
You could also use find.
bool operator== (deque<Thing> const& lhs, string const& rhs) {
return lhs[0].name == rhs;
}
void addToCollection (deque<deque& ddt, Thing const& t) {
deque<deque::iterator it(find(ddt.begin(),
ddt.end(), t.name));
if (it != ddt.end())
it->push_back(t);
else
ddt.push_back(deque<Thing>(1, t));
}
Bit confused here. Whats the operator for? You don't use it do you?
|
Find is basicly
while (first != past && ! (*first == target))
++ first;
It needs the above operator== for deque and string.
| Quote: | Or, you could use the string as the key in a map and let it do
the work for you.
void addToCollection (map<string, deque& mdt,
Thing const& t) {
mdt[t.name].push_back(t);
}
Now this is very tidy. I'll have to spend some time working through
this and its implications. I had considered a map but wondered about
random access. Is it quick?
|
Looking only at the part you specified, addToCollection, the first two
use linear, O(N), searches while map uses binary, O(lgN), search.
| Quote: | The application code may access any member of the container at anytime
in any order. Will this work?
|
You are asking for a compare between ddt[4][2] which is O(1) and
mdt[name][2] which is O(lgN). How do you translate between name
and 4? How would the application decide to access ddt[4] with no
knowledge of the name used in that collection? If that also
requires a search for the right deque, the map wins hands down.
I also wonder how the application decided on the 2. There is
nothing to prevent duplicates in the inner deques. Maybe it should
really be a map<string, map. Insufficient data
to answer question.
John
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
