How to use SORT() function on class variable

[unkn00wn]

Hello everyone, i needed to sort really large number of class objects on the basis of their one variable. And i am willing to use inbuilt sort(...) algorithm from <algorithm>

EG.

//file1.h
class database {
        protected:
	vector<node> root;
	int count;
	friend class usernlist;
.
.
.

//file2.h
class node {
        protected:
	string name;
	int index;
	vector<unsigned int> users;
.
.
.

Now in above code, assume root.size() is much high. and i wish to output a sorted list of root[i]'s on basis of root[i].users.size() without actually disturbing order of root[i]'s.

I hope i am clear enough, can anyone help me soon. Thanks.

[helios]

How about

template <typename T>
class invariant_vector_sorter{
	const std::vector<T> *v;
public:
	invariant_vector_sorter(const std::vector<T> &v):v(&v){}
	bool operator<(const size_t &a,const size_t &b){
		//T (T==node, in your case) will have to implement
		//bool operator<(const T &) const
		return (*this->v)[a]<(*this->v)[b]
	}
	static void sort(std::vector<size_t> &dst,const std::vector<T> &v){
		invariant_vector_sorter ivs(v);
		size_t n=v.size();
		dst.resize(n);
		for (size_t i=0;i<n;i++)
			dst[i]=i;
		std::sort(dst.begin(),dst.end(),ivs);
	}
};

//...

std::vector<size_t> v;
invariant_vector_sorter::sort(v,root);
for (size_t i=0;i<v.size();i++)
	std::cout <<root[v[i]]<<std::endl;

[unkn00wn]

Well, to be frank, i am not too good in c++, so i am facing some problem in understanding your code.

can you explain your code a bit.

What i got is storing root[i].users.size() in different array(or vector) sorting that array and then using some iterators to find sequence. But how!?

Thank you. Listening.

[helios]

Let's define root like this (not valid C++, obviously):
root = {root[0], root[1], ..., root[root.size()-1]};
We can define another vector v:
v = {0, 1, ..., root.size()-1};
Note that for all natural i in [0;root.size()-1] v[i] == i.
Therefore, for all natural i in [0;root.size()-1] root[v[i]] == root[i].
In other words, v is a vector of indices of root.

A vector<T> x is considered sorted iff for all natural i in [0;v.size()-2] ¬f(x[i+1], x[i]), where f is some strict weak ordering of T.
What this code does is simply sort v by defining the strict weak ordering f(x,y) = root[x]<root[y]. Let's say that v' is the sorted version of v according to this ordering. We can now define a function g(i) = root[v'[i]]. g behaves as a sorted version of root: for all natural i in [0;v'.size()-2] ¬(g(i+1)<g(i)).
g is exemplified on line 26.

Now your job, as I stated on lines 7 and 8, is to define a strict weak ordering of node:

bool operator<(const node &the_other_node) const{
    return /*...*/;
}

[unkn00wn]

Thanks helios,

I tried what you told, but couldn't able to implement it correctly. Thus i tried BST and it is working.

database A;

//file1.cpp
void create_top_list(void)
{
	unsigned int i=1;
	song *curr=new node[1];
	song *temp=new node[1];

 	while(i<A.root.size())
	{
		curr=&A.root[0];
		temp=&A.root[0];
		while(curr)
		{
			temp=curr;
			if(A.root[i].users.size()>=curr->users.size()) curr=curr->right;
			else curr=curr->left;

		}
		if(A.root[i].users.size()>=temp->users.size()) temp->right=&A.root[i];
		else temp->left=&A.root[i];
		i++;

	}
 	print_top_list(&A.root[0]);
	A.nullify_link();
	delete curr;
	delete temp;

}

with problem, worst case with O(N*N).
Thinking to implement AVL to reduce to O(N logN).

[helios]

I tried what you told, but couldn't able to implement it correctly. Thus i tried BST and it is working.

I'm speechless. That's like saying "I can't find my tent to go camping, so I'll just hire a building crew and build myself a house in the woods".

[unkn00wn]

Sorry no offense, i just said that i am too stupid to understand and use your code, so i moved to BST.

I just cant figure out what was compiler saying when i implemented your code. i cant figure out where to use root[i], root, root[i].users and so on.

And i love woods, I'll certainly hire a building crew and build myself a house in the woods.