Comparing 2 std::lists without taking order into account

[intelfx]

Hi there! I have a task - to compare 2 std::lists without taking elements order into account. That is, lists A-B-C-D and D-C-B-A are equal, but A-B-C-D and A-B-D-E aren't.
We start with the following code

class T
{
...

public:
    bool operator= {...}
}

bool compare_lists(const std::list<T>& list_1, const std::list<T>& list_2)
{
// I need help with this function
}

Do anybody knows how to do this or with what to get started?

[daviddoria]

If the lists are small, I would copy each of them into an std::multiset. The set will be sorted automatically. You can then compare each element of the sets. If they all match, the original string you have are equal.

Maybe someone has a better (more efficient) idea for you?

Dave

[mrnutty]

The easiest way to do this is use stl's, set_difference.

[daviddoria]

Will that operate on std::list ?

[mrnutty]

Will that operate on std::list ?

Sure, just try it,

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <iterator>

template<class Coll>
void print(const Coll c){
	using std::cout;
	using std::endl;

	typename Coll::const_iterator itr = c.begin();
	cout << "{ ";
	while(itr != c.end()){
		cout << *itr++ << " ";
	}
	cout << "}";
}
int main(){	
	using namespace std;
	string s1 = "abc";
	string s2 = "abd";
	list<char> a = list<char>(s1.begin(),s1.end());
	list<char> b = list<char>(s2.begin(),s2.end());
	list<char> res;

	std::set_difference(a.begin(),a.end(),b.begin(),b.end(),std::back_insert_iterator<list<char> >(res));
	print(a);
	cout << " - ";
	print(b);	
	cout << " = ";
	print(res);
	cout << endl;

	return 0;
}

[LevyDee]

If you just need to compare to see if they contain the same char's, you could just add the ASCII value of each character and compare. Not always give you right answer, but with small list, should be fine.

[NathanOliver]

@firstPerson The link you provided states that both list must be sorted by a strict weak sorting method. So the OP would have to call sort() on his list first before he sends them to std::set_difference

[intelfx]

Thanks for the answers, but I can't sort the list - I do not have any compare operators (and surely will not have, that class is something like a tree)...

[NathanOliver]

why cant you sort the list? Also what do you mean by there is no comparison operator? do you mean the each element of the list will hold a binary tree? please try to show in a little more detail what you are trying to accomplish and what your restrictions are.

[intelfx]

I am sorry for the unclear problem description. The actual class is a tree (not binary). The class consists of data and a list of node's children (subtrees).The class' operator= should compare the data and recursively compare the children list. It would be easy to accomplish, but there is a problem - we should not take children' order into account while comparing them.