C++ bindings for cgul_merge_sort
More...
#include <cgul_merge_sort_cxx.h>
Public Types | |
| typedef cgul_merge_sort__compare_t | compare_t |
Static Public Member Functions | |
| static void | sort (void *v, size_t v_count, size_t element_size, cgul_merge_sort__compare_t cf) |
| static void | sort_iteratively (void *v, size_t v_count, size_t element_size, cgul_merge_sort__compare_t cf) |
| static void | sort_pointers (void **v, size_t v_count, cgul_merge_sort__compare_t cf) |
| static void | sort_pointers_iteratively (void **v, size_t v_count, cgul_merge_sort__compare_t cf) |
Detailed Description
This class provides the C++ bindings for cgul_merge_sort. The main purpose of this class is to convert the C-style function calls and exception handling into C++-style function calls and exception handling.
Member Typedef Documentation
§ compare_t
This typedef is the interface the client must define in order for sort() or sort_pointers() to sort an array.
Member Function Documentation
§ sort()
|
inlinestatic |
Generic sort with the same parameter signature as stdlib's qsort(). v is a pointer to the top of your array. v_count is the number of elements in v. element_size is the number of contiguous bytes that comprise each element. cf is the comparison function. It will be passed pointers to two elements. It must return less than zero, zero, or greater than zero if the first element is less than, equal to, or greater than the second element. This function has to internally allocate memory to perform its task. If out-of-memory occurs, an exception is thrown, and the array is returned partially sorted.
The main draw back to using merge sort when sorting arrays is that it needs to create a copy of the original array in order to work efficiently. This particular implementation actually requires 1.5 copies of the original array at peak memory usage. If you are short on memory, you can either use cgul_merge_sort_iteratively() which only requires 1 copy or cgul_list_cxx::sort() which requires no extra copies because it operates on linked lists which have efficient removal and insertion operations.
If you need to constantly maintain a sorted list, cgul_rbtree_cxx or cgul_multimap_cxx are usually better solutions.
- Parameters
-
[in] v array of elements to sort [in] v_count number of elements in v[in] element_size size of each element in v[in] cf comparison function
References cgul_merge_sort().
§ sort_iteratively()
|
inlinestatic |
Generic sort with the same parameter signature as stdlib's qsort(). v is a pointer to the top of your array. v_count is the number of elements in v. element_size is the number of contiguous bytes that comprise each element. cf is the comparison function. It will be passed pointers to two elements. It must return less than zero, zero, or greater than zero if the first element is less than, equal to, or greater than the second element. This function has to internally allocate memory to perform its task. If out-of-memory occurs, an exception is thrown, and the array is returned partially sorted.
There are three main differences between this function and sort(). First, sort() is about 30% faster than this function. Second, sort() is a recursive implementation that consumes more stack space than this function which is an iterative implementation. Third, sort() uses 50% more memory than this implementation because it requires 1.5 extra copies of v; whereas, this implementation only requires 1 extra copy. If in doubt, use sort() instead of this function.
If you need to constantly maintain a sorted list, cgul_rbtree_cxx or cgul_multimap_cxx are usually better solutions.
- Parameters
-
[in] v array of elements to sort [in] v_count number of elements in v[in] element_size size of each element in v[in] cf comparison function
References cgul_merge_sort_iteratively().
§ sort_pointers()
|
inlinestatic |
If your array is already composed of pointers, you can directly call this function. v will be sorted using cf the same as described for sort(). If out-of-memory occurs, an exception is thrown, and the array is returned partially sorted.
The main draw back to using merge sort when sorting arrays is that it needs to create a copy of the original array in order to work efficiently. This particular implementation actually requires 1.5 copies of the original array at peak memory usage. If you are short on memory, you can either use sort_pointers_iteratively() which only requires 1 copy or cgul_list_cxx::sort() which requires no extra copies because it operates on linked list which have efficient removal and insertion operations.
If you need to constantly maintain a sorted list, cgul_rbtree_cxx or cgul_multimap_cxx are usually better solutions.
- Parameters
-
[in] v array of pointers to elements to sort [in] v_count number of elements in v[in] cf comparison function
References cgul_merge_sort_pointers().
§ sort_pointers_iteratively()
|
inlinestatic |
If your array is already composed of pointers, you can directly call this function. v will be sorted using cf the same as described for cgul_merge_sort_iteratively(). If out-of-memory occurs, an exception is thrown, and the array is returned partially sorted.
There are three main differences between this function and sort_pointers(). First, sort_pointers() is about 30% faster than this function. Second, sort_pointers() is a recursive implementation that consumes more stack space than this function which is an iterative implementation. Third, sort_pointers() uses 50% more memory than this implementation because it requires 1.5 extra copies of v; whereas, this implementation only requires 1 extra copy. If in doubt, use sort_pointers() instead of this function.
If you need to constantly maintain a sorted list, cgul_rbtree_cxx or cgul_multimap_cxx are usually better solutions.
- Parameters
-
[in] v array of pointers to elements to sort [in] v_count number of elements in v[in] cf comparison function
References cgul_merge_sort_pointers_iteratively().
The documentation for this class was generated from the following file:
