P
Pratyush
Hi,
Suppose there is a vector of objects of class A, i.e., std::vector<A>
vec_A(N); The class A satisifies all the STL vector requirements.
Now I wish to add some attributes for each of the objects in the
vector vec_A. Suppose there are K attributes to be added. For each of
the attributes I define K vectors of appropriate types. Say, the
attributes have types type1, type2, ..., typeK. So I define
std::vector<type1> attr1(vec_A.size());
std::vector<type2> attr2(vec_A.size());
....
std::vector<typeK> attrK(vec_A.size());
The important condition is that the object at location i in vec_A has
attributes at location i in attr1, attr2, ..., attrK.
Now suppose I need to sort the vector vec_A on basis of some of the
attributes. How can it be efficiently (both in terms of time and
memory) done so that the above mentioned condition is satisfied?
One approach that I used is to have copies of the basis attributes
vectors. Then sort vec_A, attr1, attr2, ..., attrK using the copies.
But this involves on average (K+1)*NlogN comparisons of the basis
attributes. Additionally I am creating copies of the basis attributes.
So this approach seems quite unsatisfactory. Is it possible to have
only NlogN comparisons? Best if no copies of the basis attributes are
involved.
Of course, one can define class A to have the attributes as its
fields. But then its not general and flexible enough. In that case,
one loses the flexibilty of having one attribute, two attributes and
so on.
One example of such a need can be the case where class A represent a
vertex of a graph, and the attributes are different properties of a
vertex.
Thanks & regards,
Pratyush
Suppose there is a vector of objects of class A, i.e., std::vector<A>
vec_A(N); The class A satisifies all the STL vector requirements.
Now I wish to add some attributes for each of the objects in the
vector vec_A. Suppose there are K attributes to be added. For each of
the attributes I define K vectors of appropriate types. Say, the
attributes have types type1, type2, ..., typeK. So I define
std::vector<type1> attr1(vec_A.size());
std::vector<type2> attr2(vec_A.size());
....
std::vector<typeK> attrK(vec_A.size());
The important condition is that the object at location i in vec_A has
attributes at location i in attr1, attr2, ..., attrK.
Now suppose I need to sort the vector vec_A on basis of some of the
attributes. How can it be efficiently (both in terms of time and
memory) done so that the above mentioned condition is satisfied?
One approach that I used is to have copies of the basis attributes
vectors. Then sort vec_A, attr1, attr2, ..., attrK using the copies.
But this involves on average (K+1)*NlogN comparisons of the basis
attributes. Additionally I am creating copies of the basis attributes.
So this approach seems quite unsatisfactory. Is it possible to have
only NlogN comparisons? Best if no copies of the basis attributes are
involved.
Of course, one can define class A to have the attributes as its
fields. But then its not general and flexible enough. In that case,
one loses the flexibilty of having one attribute, two attributes and
so on.
One example of such a need can be the case where class A represent a
vertex of a graph, and the attributes are different properties of a
vertex.
Thanks & regards,
Pratyush