Jump to content
  • Advertisement
Sign in to follow this  
danielgamedev

sorting vector array based on first component

This topic is 4853 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Is their an algorithm that sorts a matrix based on the first column or a vector array based on the first component of the vectors? example I have vector array or matrix: M = 9, 4, 7 4, 6, 7 5, 7, 3 2, 3, 8 after sort M = : 2, 3, 8 4, 6, 7 5, 7, 3 9, 4, 7 dg

Share this post


Link to post
Share on other sites
Advertisement
This depends on how your matrix and row data structures look really, but one approach is to write a custom comparison operator for your row structure that only looks at the first element, put your row objects in a standard container and send it to a sorting algorithm (also from the standard library). This solution should be quick to implement, but it got some overhead that might make it unsuitable for you. If that's the case, you can rewrite your data structures to work with the C++ Standard Library interfaces or roll your own implementation of a sorting algorithm that's suitable for your data. If you're going with the standard library, this is a nice place to start.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster

#include
#include

int main() {

using namespace std;

const size_t N = 4;

float matrix[][N] = { { 9, 4, 5, 6 }, { 4, 6, 7, 3 }, { 7, 7, 3, 8 } };

const size_t M = sizeof(matrix) / sizeof(float[N]);

float (*itr)[N] = &matrix[0];

for(ptrdiff_t n = &matrix[M] - itr; n > 0; --n) {
sort(*itr, *itr + N);
++itr;
}
}

Share this post


Link to post
Share on other sites
Quote:
Original post by danielgamedev
wow! Anonymous. That is some heavy duty stuff. I'm not too familiar with the Microsoft Runtime Library.
could you explain this syntax or point me to a url? " float (*itr)[N] = ... "



std::sort, size_t, ptrdiff_t are part of the C++ standard & standard library.

size_t is used for referring to sizes in both standards C & C++ throughout, its also the type returned from the sizeof operator. size_t is a platform dependant type alias for some unsigned integral type.

ptrdiff_t is the type of the difference of pointers used in both standards C & C++ throughout. ptrdiff_t is a platform dependant type alias for some signed integral type.

Both type aliases are defined in the header stddef.h in C or cstddef in C++.

Moving on: float (*itr)[N] is a a pointer to an array of N elements of type float, where N is known at compile time. There probably isn't much info about them online but i'll give you the gist of it:

In that code in C++:

  • The type of matrix is of type float/const float (&)[M][N] (a reference to a 2d array).

  • The type of matrix is of type float/const float (&)[N] (a reference to a 1d array).

  • The type of matrix[j] is of type float/const float&



Therefore the type of &matrix is float/const float (*)[N] a pointer to a 1d array, therefore when you dereference it its of type float/const float (&)[N].

The C++ standard library generic algorithms (such as std::sort) work on templated iterator range and as pointers are a model of the iterator concept C-style arrays & strings can be used with them as well this is done through static (compile-time) polymorhism that templates can give you.

[Edited by - snk_kid on August 7, 2005 3:36:39 PM]

Share this post


Link to post
Share on other sites
Thanks for the reply snk_kid,
Let me expand on my original question. What if rather than using a matrix I used a structure myStructure. I then create an array of type myStructure. How would I make myStructure conform or meet the requirements of a sort function call?

DG

Share this post


Link to post
Share on other sites
You can either implement operator< for your structure, or pass a comparison functor as an extra argument to the sort call. That last argument is actually defaulted to be an instance of the class "std::less", which is a comparison functor which basically says "use the class' operator<". All you need for the comparison functor is an overload of "operator()" which accepts two instances of the structure to be compared (by const reference), and returns a bool (which is true iff the first parameter should come before the second in the sorted result).

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
That last argument is actually defaulted to be an instance of the class "std::less", which is a comparison functor which basically says "use the class' operator<".


Algorithms like std::sort are actually overloaded the version that does not take a custom predicate assumes the value type supports the relational less than operator and doesn't use std::less. The version that takes a custom predicate doesn't have a default value too.

Anyways i'm not sure if thats what he wants to do as he originally said he wants to sort the elements of each individual row/column vec of a matrix where row/column vec is representated by a user-defined type. If that is the case then he could do something like this:


struct vec4 {
float x, y, z, w;

typedef float* iterator;
typedef const float* const_iterator;

const_iterator begin() const {
return &x;
}

iterator begin() {
return &x;
}

const_iterator end() const {
return &w + 1;
}

iterator end() {
return &w + 1;
}
};

#include <ostream>

template < typename CharT, typename Traits >
std::basic_ostream<CharT, Traits>&
operator<<(std::basic_ostream<CharT, Traits>& out, const vec4& vref) {
return out << '(' << vref.x << ", " << vref.y << ", " << vref.z << ", " << vref.w << ')';
}

#include <cstddef>
#include <algorithm>
#include <iterator>
#include <iostream>

void sort_vec(vec4& vref) {
std::sort(vref.begin(), vref.end());
}

int main() {

using namespace std;

vec4 v[] = { { 9, 4, 5, 6 }, { 4, 6, 7, 3 }, { 7, 7, 3, 8 } };
const size_t N = sizeof v / sizeof(vec4);

cout << "before:\n";
copy(v, v + N, ostream_iterator<vec4>(cout, "\n"));

for_each(v, v + N, sort_vec);

cout << "\n\nafter:\n";
copy(v, v + N, ostream_iterator<vec4>(cout, "\n"));

}


But that might have issues with alignment.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!