![]() |
| | #1 |
| Registered User Join Date: Oct 2006 Location: LA
Posts: 44
| compare structures I have defined a structure as Code: typedef struct ps_report_rows
{
std::string cp_item_id;
std::string cp_object_string;
std::string mfg_object_string;
std::string mor_item_id;
} report_row;
Code: list<report_row> objectList1; list<report_row> objectList2; This is the code I have in mind Code: list < report_row > ::iterator listIter1;
list < report_row > ::iterator listIter2;
bool isDuplicate = false;
list<report_row> finalList;
finalList.clear();
for (listIter1 = objectList1.begin(); listIter1 != objectList1.end() ; listIter1++)
{
report_row primaryRow = *listIter1;
for (listIter2 = objectList2.begin(); listIter2 != objectList2.end() ; listIter2++)
{
isDuplicate = false;
report_row secondaryRow = *listIter2;
check_if_duplicate_row(primaryRow, secondaryRow, isDuplicate);
if(isDuplicate == true)
break;
}
if(isDuplicate == false)
{
finalList.push_back(primaryRow);
}
}
void check_if_duplicate_row(report_row primaryRow, report_row secondaryRow, bool& isDuplicate)
{
if(primaryRow->cp_item_id!=secondaryRow->cp_item_id)
{
isDuplicate = false;
break;
}
if(primaryRow->cp_object_string!=secondaryRow->cp_object_string)
{
isDuplicate = false;
break;
}
if(primaryRow->mfg_object_string!=secondaryRow->mfg_object_string)
{
isDuplicate = false;
break;
}
if(primaryRow->mor_item_id!=secondaryRow->mor_item_id)
{
isDuplicate = false;
break;
}
isDuplicate = true;
}
|
| lazyme is offline | |
| | #2 | |
| The larch Join Date: May 2006
Posts: 3,222
| You can overload operator== for report_row and use std::find instead of the inner loop. Code: void check_if_duplicate_row(report_row primaryRow, report_row secondaryRow, bool& isDuplicate) If you want to make it more efficient, you might sort the list first. Then you'll only need to check pairs of neighbours to find out if they are duplicates or not.
__________________ I might be wrong. Quote:
| |
| anon is offline | |
| | #3 | |||
| Registered User Join Date: Oct 2006 Location: LA
Posts: 44
| Quote:
Code: list < report_row > ::iterator listIter1;
list<report_row> finalList;
finalList.clear();
for (listIter1 = objectList1.begin(); listIter1 != objectList1.end() ; listIter1++)
{
report_row primaryRow = *listIter1;
if(std::find(objectList2.begin(), objectList2.end(), primaryRow) != objectList2.end())
{
finalList.push_back(primaryRow);
}
}
Quote:
Quote:
| |||
| lazyme is offline | |
| | #4 | |
| C++ Witch Join Date: Oct 2003 Location: Singapore
Posts: 11,318
| Quote:
Sounds tough? If both the lists are sorted, then you can avoid implementing the algorithm yourself by using std::set_difference. Another algorithm to accomplish the same task, of comparable efficiency (if you were using a container with random access instead of std::list), involves sorting the second list only, then making a single pass over the first list while binary searching the second list to determine if the current element of the first list is present in the second.
__________________ C + C++ Compiler: MinGW port of GCC Build + Version Control System: SCons + Bazaar Look up a C/C++ Reference and learn How To Ask Questions The Smart Way | |
| laserlight is online now | |
| | #5 |
| Registered User Join Date: Oct 2006 Location: LA
Posts: 44
| Ok. I got your point. Will this work fine? Code: list < report_row > ::iterator listIterEnd, listIter; list<report_row> finalList; finalList.clear(); objectList1.sort(); objectList2.sort(); listIterEnd = set_difference(objectList1.begin(), objectList1.end(), objectList2.begin(), objectList2.end(), finalList.begin()); |
| lazyme is offline | |
| | #6 |
| Registered User Join Date: Jan 2008
Posts: 634
| "Describe an algorithm that makes a single pass over the first list and at most a single pass over the second list to determine the elements that are present in the first list but not in the second list." Easy. Create a third and fourth list and... ^_^; Soma |
| phantomotap is offline | |
| | #7 |
| Registered User Join Date: Oct 2006 Location: LA
Posts: 44
| Ok. What about the code I posted. Should that work fine? |
| lazyme is offline | |
| | #8 |
| Registered User Join Date: Oct 2006 Location: LA
Posts: 44
| objectList1.sort() gives me an error Code: bool std::operator <(const std::vector<_Ty,_Alloc> &,const std::vector<_Ty,_Alloc> &)' : could not deduce template argument for 'const std::vector<_Ty,_Alloc> &' from 'ps_report_rows Also, how can I use set_difference for my structure. I tried the code I posted above but that doesnt work. |
| lazyme is offline | |
| | #9 | |
| The larch Join Date: May 2006
Posts: 3,222
| I have no idea where the vector came from. Do you have operator< defined for ps_report_rows? What does it look like (might be tricky if you want to compare more than one field in a struct)? Code: bool operator< (const ps_report_rows& lhv, const ps_report_rows& rhv)
{
//comparison logic here
}
Code: #include <iterator> ... list<report_row> finalList; //finalList.clear(); //it's already empty objectList1.sort(); objectList2.sort(); listIterEnd = set_difference(objectList1.begin(), objectList1.end(), objectList2.begin(), objectList2.end(), std::back_inserter(finalList));
__________________ I might be wrong. Quote:
| |
| anon is offline | |
| | #10 |
| Registered User Join Date: Oct 2006 Location: LA
Posts: 44
| No, I don't have the operator < defined. I dont necessarily need to compare more than one field in the struct. Can I use set_difference if my lists are sorted by any field in the struct? |
| lazyme is offline | |
| | #11 | |
| The larch Join Date: May 2006
Posts: 3,222
| You'll either need to overload operator<, or provide a comparison function (that is the same for both sort and set_difference). The overloaded operator could be implemented like this: Code: bool operator< (const ps_report_rows& lhv, const ps_report_rows& rhv)
{
return lhv.cp_item_id < rhv.cp_item_id;
}
__________________ I might be wrong. Quote:
| |
| anon is offline | |
| | #12 |
| Registered User Join Date: Oct 2006 Location: LA
Posts: 44
| I want set_difference to determine the items are same only if all the four fields match. Can I achieve this with Code: bool operator< (const ps_report_rows& lhv, const ps_report_rows& rhv)
{
if(lhv.cp_item_id!=rhv.cp_item_id)
return lhv.cp_item_id < rhv.cp_item_id;
if(lhv.cp_object_string!=rhv.cp_object_string)
return lhv.cp_object_string< rhv.cp_object_string;
if(lhv.mfg_object_string!=rhv.mfg_object_string)
return lhv.mfg_object_string < rhv.mfg_object_string;
return lhv.mor_item_id < rhv.mor_item_id;
}
|
| lazyme is offline | |
| | #13 | |
| The larch Join Date: May 2006
Posts: 3,222
| It looks correct.
__________________ I might be wrong. Quote:
| |
| anon is offline | |
| | #14 |
| Registered User Join Date: Oct 2006 Location: LA
Posts: 44
| Thanks anon. I have written my code around this and it works fine. The structure contains 13 elements now. I am posting my complete code below. Please let me know if you can foresee any errors(mainly in the boolean operator < function) I cant see at the moment and also any suggestions to improve this code. Code: std::list<pn_report_row_t> finalDeltaList; finalDeltaList.clear(); objectList1.sort(); objectList2.sort(); set_difference(objectList1.begin(), objectList1.end(), objectList2.begin(), objectList2.end(), std::back_inserter(finalDeltaList)); Code: std::string siemens_trim(std::string inputStr)
{
if (!inputStr.empty())
{
/*get the first white space in the string*/
std::string::size_type startPos = inputStr.find_first_not_of("\n\t ");
if (startPos != std::string::npos)
{
/*get the last white space in the string*/
std::string::size_type endPos = inputStr.find_last_not_of("\n\t ");
/*trim the white spaces*/
inputStr = inputStr.substr(startPos, endPos - startPos + 1);
}
else
{
inputStr.clear();
}
return inputStr;
}
}
Code: bool operator< ( pn_report_row_t& primaryRow, pn_report_row_t& secondaryRow)
{
string cpItemId = siemens_trim(primaryRow.cp_item_id);
string secCpItemId = siemens_trim(secondaryRow.cp_item_id);
string cpObjStr = siemens_trim(primaryRow.cp_object_string);
string secCpObjStr = siemens_trim(secondaryRow.cp_object_string);
string mfgObjStr = siemens_trim(primaryRow.mfg_object_string);
string secMfgObjStr = siemens_trim(secondaryRow.mfg_object_string);
string morItemId = siemens_trim(primaryRow.mor_item_id);
string secMorItemId = siemens_trim(secondaryRow.mor_item_id);
string morObjStr = siemens_trim(primaryRow.mor_object_string);
string secMorObjStr = siemens_trim(secondaryRow.mor_object_string);
string sorItemId = siemens_trim(primaryRow.sor_item_id);
string secSorItemId = siemens_trim(secondaryRow.sor_item_id);
string sorObjStr = siemens_trim(primaryRow.sor_object_string);
string secSorObjStr = siemens_trim(secondaryRow.sor_object_string);
string manufacturerType = siemens_trim(primaryRow.manufacturer_type);
string secManufacturerType = siemens_trim(secondaryRow.manufacturer_type);
string orderDesc = siemens_trim(primaryRow.order_desc);
string secOrderDesc = siemens_trim(secondaryRow.order_desc);
string addnOrderDesc = siemens_trim(primaryRow.additional_order_desc);
string secAddnOrderDesc = siemens_trim(secondaryRow.additional_order_desc);
string objStr = siemens_trim(primaryRow.object_string);
string secObjStr = siemens_trim(secondaryRow.object_string);
string lastOrdDt = siemens_trim(primaryRow.last_order_date);
string secLastOrdDt = siemens_trim(secondaryRow.last_order_date);
string howImpact = siemens_trim(primaryRow.how_impacted);
string secHowImpact = siemens_trim(secondaryRow.how_impacted);
if(cpItemId.compare(secCpItemId)!=0)
{
return cpItemId < secCpItemId;
}
if(cpObjStr.compare(secCpObjStr)!=0)
{
return cpObjStr < secCpObjStr;
}
if(mfgObjStr.compare(secMfgObjStr)!=0)
{
return mfgObjStr < secMfgObjStr;
}
if(morItemId.compare(secMorItemId)!=0)
{
return morItemId < secMorItemId;
}
if(morObjStr.compare(secMorObjStr)!=0)
{
return morObjStr < secMorObjStr;
}
if(sorItemId.compare(secSorItemId)!=0)
{
return sorItemId < secSorItemId;
}
if(morItemId.compare(secMorItemId)!=0)
{
return morItemId < secMorItemId;
}
if(sorObjStr.compare(secSorObjStr)!=0)
{
return sorObjStr < secSorObjStr;
}
if(manufacturerType.compare(secManufacturerType)!=0)
{
return manufacturerType < secManufacturerType;
}
if(orderDesc.compare(secOrderDesc)!=0)
{
return orderDesc < secOrderDesc;
}
if(objStr.compare(secObjStr)!=0)
{
return objStr < secObjStr;
}
if(lastOrdDt.compare(secLastOrdDt)!=0)
{
return lastOrdDt < secLastOrdDt;
}
return howImpact < secHowImpact;
}
|
| lazyme is offline | |
| | #15 | |
| The larch Join Date: May 2006
Posts: 3,222
| The comparison function looks a bit heavy. If it is not important for some reasons that the stored strings keep their trailing and leading whitespace, you could make sure that the strings are trimmed when you store them in a pn_report_row_t. Another thing to reduce code might be to store the strings in an array instead of individual variables. You can provide an enum, so each index has a descriptive name (yours aren't very descriptive). A small fault is that comparison operators should not modify what is being compared and therefore they should take the arguments by const reference. There's also a small problem with the trimming function. The return statement should be moved to the end of the function, otherwise it won't return anything if the string is empty. (The test whether the string is empty is not very important: find_first_not_of would simply return npos and it is OK to clear an empty string.) Code: std::string siemens_trim(std::string inputStr)
{
if (!inputStr.empty())
{
/*get the first white space in the string*/
std::string::size_type startPos = inputStr.find_first_not_of("\n\t ");
if (startPos != std::string::npos)
{
/*get the last white space in the string*/
std::string::size_type endPos = inputStr.find_last_not_of("\n\t ");
/*trim the white spaces*/
inputStr = inputStr.substr(startPos, endPos - startPos + 1);
}
else
{
inputStr.clear();
}
}
return inputStr;
}
class pn_report_row_t
{
public:
enum
{
cpItemId, cpObjStr, mfgObjStr, morItemId, morObjStr, sorItemId, sorObjStr,
manufacturerType, orderDesc, addnOrderDesc, objStr, lastOrdDt, howImpact,
maxField
};
const std::string& get(unsigned index) const
{
assert(index < maxField);
return fields[index];
}
void set(const std::string& value, unsigned index)
{
assert(index < maxField);
fields[index] = siemens_trim(value);
}
private:
std::string fields[maxField];
};
bool operator< (const pn_report_row_t& primaryRow, const pn_report_row_t& secondaryRow)
{
for (unsigned i = 0; i != pn_report_row_t::maxField; ++i) {
if (primaryRow.get(i) != secondaryRow.get(i)) {
return primaryRow.get(i) < secondaryRow.get(i);
}
}
return false;
}
Code: std::string siemens_trim(const std::string& inputStr)
{
if (!inputStr.empty())
{
/*get the first white space in the string*/
std::string::size_type startPos = inputStr.find_first_not_of("\n\t ");
if (startPos != std::string::npos)
{
/*get the last white space in the string*/
std::string::size_type endPos = inputStr.find_last_not_of("\n\t ");
/*trim the white spaces*/
return inputStr.substr(startPos, endPos - startPos + 1);
}
}
return std::string();
}
__________________ I might be wrong. Quote:
Last edited by anon; 05-27-2009 at 08:24 AM. | |
| anon is offline | |
![]() |
| Thread Tools | |
| Display Modes | |
|
Similar Threads | ||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| Dynamic array of structures containing yet another dynamic array of structures | innqubus | C Programming | 2 | 07-11-2008 07:39 AM |
| Structures within Structures | Misko82 | C Programming | 2 | 08-27-2007 12:25 AM |
| Classes and Structures. | jrahhali | C++ Programming | 6 | 03-28-2004 05:03 PM |
| How do I compare structures?? | aspand | C Programming | 4 | 06-09-2002 10:47 AM |
| Methods for Sorting Structures by Element... | Sebastiani | C Programming | 9 | 09-14-2001 12:59 PM |