Sign in to follow this  
chessnut

What's the more elegant function?

Recommended Posts

Hi, I'm new to writing good c++ software programs and I'm trying to think of the best way to implement this function that filters all elements in a list that don't contain a search token in one of their members. I have the following pseudoish code below:
using namespace std; 

struct Card
{
	string m_CardName, m_CardType, m_Rules;
};

vector<Card>* filteredList; // this is pointing to a valid vector<Card> object.

void SearchFilterVersionA(string searchStr)
{
	// this algorithm uppercases all tokens to make searching case insensitive.
	transform(searchStr.begin(), searchStr.end(), searchStr.begin(), ::toupper);

	for (size_t i=0; i<filteredList->size(); ++i)
	{
		string* s[3] = {&((*filteredList)[i].m_CardName), &((*filteredList)[i].m_CardType), &((*filteredList)[i].m_Rules)};
		for (size_t j=0; j<3; ++j)
		{
			transform(s[j]->begin(), s[j]->end(), s[j]->begin(), ::toupper);
			
			if (s[j]->find(searchStr) != string::npos) 
				break;
			else if (j==2) // this Card does not contain the search token, erase it.
			{
				filteredList->erase(filteredList->begin()+i);
				--i;
			}
		}
	}
}
void SearchFilterVersionB(string searchStr)
{
	// this algorithm uppercases all tokens to make searching case insensitive.
	transform(searchStr.begin(), searchStr.end(), searchStr.begin(), ::toupper);

	for (size_t i=0, j; i<filteredList->size(); ++i)
	{
		string s = (*filteredList)[i].m_CardName;
		transform(s.begin(), s.end(), s.begin(), ::toupper);
		if (s.find(searchStr) != string::npos)
			continue;
		
		s = (*filteredList)[i].m_CardType;
		transform(s.begin(), s.end(), s.begin(), ::toupper);
		if (s.find(searchStr) != string::npos)
			continue;
		
		s = (*filteredList)[i].m_Rules;
		transform(s.begin(), s.end(), s.begin(), ::toupper);
		if (s.find(searchStr) != string::npos)
			continue;

		filteredList->erase(filteredList->begin()+i);
		--i;
	}
}

As you can see each version of the function is identical in its logic. It's going through a list of cards and searching each member for a search token. If the search token is not found, it erases the card from the list. The primary difference between the two functions is one makes a list to its members and then loops through the member list looking for the search string where as the other version of the function explicitly searches through each member. I'm wondering what is better and why? IMO Version A is more extensible and managable, but the code is definitely uglier with that list of pointers to member strings. Version B is very straight forward and a more clear, but I really don't like copy and paste style coding and especially repeating the same lines over and over. If there was a few more members I wouldn't even be asking this question as Version A is clearly more concise. BTW is this the right forum to ask this question in?

Share this post


Link to post
Share on other sites
functionB looks much cleaner. Its MUCH easier to read, which is very good. You only repeat those same lines three times, thats not so bad. If it really bothers you, create a helper method and pass the method what it needs.

I say B, because of the readablity and straight-forwardness.

Share this post


Link to post
Share on other sites
Copy and pasting is normally frowned upon for me when you do it in different parts of the program for the simple reason of if you change one, you have to go and find all and change them. Doin versionB is simpler, if something changes, theyre all right there. I think version B is probably a better route unless you comment nicely or have a good memory. The reason I say this is because I find myself forgetting what functions did exactly and my code isnt perfect, so its hard to prove in my head sometimes (and since its not perfect, hard to prove through regular pen n paper).

Share this post


Link to post
Share on other sites
I'd suggest something more like this:

using namespace std;

struct Card
{
string m_CardName, m_CardType, m_Rules;
};

list<Card>* filteredList; // this is pointing to a valid vector<Card> object.

// lots of copying and pasting typically mean you should create a function to do it.
bool contains(string str, string searchStr)
{
transform(str->begin(), str->end(), str->begin(), ::toupper);
if (str->find(searchStr) != string::npos)
return true;
return false;
}

void SearchFilterVersionA(string searchStr)
{
// this algorithm uppercases all tokens to make searching case insensitive.
transform(searchStr.begin(), searchStr.end(), searchStr.begin(), ::toupper);

list<Card>::iterator iter;
for (iter = filteredList->begin(); iter != filteredList->end(); ++iter)
{
// if the none of the members contain the searchStr erase it
if( !contains(iter->m_CardName, searchStr) &&
!contains(iter->m_CardType, searchStr) &&
!contains(iter->m_Rules, searchStr) )
{
temp = iter; // remember this iter
++temp; // move on to the next
filteredList->erase(iter); // get rid of the old
iter = temp; // on to the next
}
}
}



This uses a list type instead of a vector type, which makes the erase a little different as well as the iteration. If you'd like to keep on using your vector simply put your old erase code back in where the filteredList->erase(iter) is. Should work the same way.

Share this post


Link to post
Share on other sites
Thanks for all the replies.
Quote:

Amnesty2: Curious, why don't you make all your strings packed into filterlist all uppercase to begin with; so you don't have to toupper 3 times per iteration?


What I showed is only 90% of the function. The strings in the Card struct are case-sensitive so I dont want to upper them. In my actual function I compare a tempory Card object that has been uppered to not disturb the case-sensitive strings.

Dwiel: I totally agree with you that if you're going to use the same code more then once or twice you should make a function, but I would make sure to use logical-or over logical-and here as the filter lists and the strings can be huge.

Share this post


Link to post
Share on other sites
I might as well through some more versions in the mix so


// Standard library version, i think this is probally the most descriptive
// and extensible way

struct Card
{
std::string m_CardName, m_CardType, m_Rules;
};

typedef std::vector<Card> CardList;
CardList filteredList;

bool Contains(std::string str, const std::string& searchStr)
{
std::transform(str.begin(), str.end(), str.begin(), toupper);
return (str.find(searchStr) != string::npos);
}

bool IsInvalidSearchString(const std::string& searchString, const Card& card)
{
return !Contains(card.m_CardName, searchString) &&
!Contains(card.m_CardType, searchString) &&
!Contains(card.m_Rules, searchString);
}

void SearchFilter(std::string searchStr)
{
std::transform(searchStr.begin(), searchStr.end(), searchStr.begin(), toupper);

CardList::iterator newEnd = std::remove_if(filteredList.begin(),
filteredList.end(),
std::bind1st(IsInValidSearchString, searchStr));
filteredList.erase(newEnd, filteredList.end());
}






// Boost version, basically just gets rid of the helper functions which keeps
// everything local

struct Card
{
std::string m_CardName, m_CardType, m_Rules;
};

typedef std::vector<Card> CardList;
CardList filteredList;

void SearchFilter(std::string searchStr)
{
using namespace boost;
using namespace boost::lambda;

std::transform(searchStr.begin(), searchStr.end(), searchStr.begin(), toupper);

placeholder1_type str;
function<bool (std::string)> contains =
(
bind(std::transform,
bind(call_begin(), str),
bind(call_end(), str),
bind(call_begin(), str),
toupper),
bind(std::find<std::string::iterator, std::string>,
searchStr.begin(),
searchStr.end(),
str);
);

placeholder1_type card;
CardList::iterator newEnd = std::remove_if(filteredList.begin(),
filteredList.end(),
(
!bind(contains, (&card ->* &Card::m_CardName)) &&
!bind(contains, (&card ->* &Card::m_CardType)) &&
!bind(contains, (&card ->* &Card::m_Rules))
));

filteredList.erase(newEnd, filteredList.end());
}



Share this post


Link to post
Share on other sites
Quote:
Original post by Julian90
I might as well through some more versions in the mix so

*** Source Snippet Removed ***

*** Source Snippet Removed ***

LOL! Awesome Julian90, I love those. That's some very sesy code.
*EDIT*
Thank you, I'm definitely going to use one of those, though I need to go over the boost documentation to understand what the second one does, thank you very much for those.

Share this post


Link to post
Share on other sites
Quote:
Original post by chessnut
Dwiel: I totally agree with you that if you're going to use the same code more then once or twice you should make a function, but I would make sure to use logical-or over logical-and here as the filter lists and the strings can be huge.


logical-and has the same early-out behaviour as logical-or, and rewriting a boolean expression using DeMorgan's Laws will not change the performance WRT early-outs. It is purely a matter of what seems more readable, unless you are worried about the overhead of logical negations. Even then, the compiler is likely to rearrange things behind the scenes.

That said, a version with fewer logical negations is usually more easily understood.

Also, some more refactoring.


using namespace std;

struct Card {
string m_CardName, m_CardType, m_Rules;
};

// The container type doesn't really matter.
// But why would you have a pointer to a container? :s
list<Card> filteredList;

// Prefer to pass arguments of object type by const reference, unless the
// function needs to make a copy anyway.
bool contains(const string& str, const string& searchStr) {
// We don't have a pointer to the string, so we shouldn't be using
// arrow operators.
transform(str.begin(), str.end(), str.begin(), ::toupper);
// AARGH. Please avoid that kind of extra verbosity when handling
// booleans. This is all you need:
return str.find(searchStr) != string::npos;
}

// Since we're already using std:: algorithms, we should be using the
// "erase-remove idiom" to handle the container update. :) This actually
// encourages us to do a bit more factoring which will probably help us in
// the long run:
struct card_matches : public unary_function {
string searchStr;

card_matches(const string& str): searchStr(str) {
transform(searchStr.begin(), searchStr.end(), searchStr.begin(), ::toupper);
}

bool operator()(const Card& c) {
return contains(c.m_CardName, searchStr) ||
contains(c.m_CardType, searchStr) ||
contains(c.m_Rules, searchStr);
}
};

void SearchFilter(const string& searchStr) {
filteredList.erase(remove_if(filteredList.begin(), filteredList.end(), card_matches(searchStr)), not1(filteredList.end()));
}

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this