C++ Not Requiring Array Length with Recursive Sorting Algorithms

Question

Some may or may not know that you can get the size of an array argument to a function using this code:

template<typename DataType, size_t SIZE>
void SortingAlgorithm(DataType (&array)[SIZE])
{
  ...
  return;
}

where SIZE can be used to represent the number of elements in the array, allowing the, programmer using your function to pass the array as an argument without explicitly passing the length. For example, the programmer can do this:

SortingAlgorithm( arrayToBeSorted ); //the length is not passed here, which is fine

For Algorithms that can be implemented relatively easily in an iterative style, this is fine. But I've tried to do this with other algorithms that are recursive. The code for each one might look something like this:

template<typename DataType, size_t SIZE>
void SortingAlgorithm(DataType (&array)[SIZE])
{
  DataType newArray[SIZE];
  memcpy(newArray,array, SIZE);  //copy to a new array
  SortingAlgorithm( newArray );
  ...
  return;
}

But this throws an error every time saying that the program expects a different argument type, type conversion has failed, and shows an attempt to typecast the SIZE specifier for the newArray array multiple times, and the program fails. It does not however spit out these errors if I use an actual value to define the size of newArray before making the recursive call, like this:

DataType newArray[10]; //arbitrary number, but the compiler accepts this.

Why is it that a variable sized array causes an error? Also is there anyway to implement a recursive algorithm that accepts an array as input but does not require the length of the array as an argument because It can determine the length of the array each time within the function call?

You're aware that the downside of this is that a fresh instantiation of the sorting routine will be generated for each size of array you need to sort, right? Unless you're extremely agressive about trading code size for speed the body of your template sorter ought to be something like SizeGenericSortingAlgorithm(array, SIZE), calling a template<typename DataType> void SizeGenericSortingAlgorithm(DataType *array, size_t size). — hmakholm left over Monica
– hmakholm left over Monica, Commented Nov 9, 2012 at 20:42
Well the ambition here is to figure out if I can make recursive sorting algorithms convenient by not requiring the programmer to keep track of the size of the array he/she is using. — kjh
– kjh, Commented Nov 9, 2012 at 20:44

Benjamin Lindley · Accepted Answer · 2012-11-09 21:06:15Z

Make a helper function that takes a size, it can be used internally by your other function, and nobody has to know about it. For example:

template<typename DataType>
void SortingAlgorithm_helper(DataType * ptr, size_t size)
{
    ...
    SortingAlgorithm_helper(ptr + 1, size - 1);
    ...
}

template<typename DataType, size_t SIZE>
void SortingAlgorithm(DataType (&array)[SIZE])
{
    ...
    SortingAlgorithm_helper(newArray,SIZE);
    ...      
}

By your comments, you are considering switching to vector. Well, you don't have to make a choice here. You can make the code much more generic to handle both. Instead of passing in a pointer and a size to the helper function, we pass in two iterators designating a range. Then we modify the main function to accept any container, as long as std::begin and std::end work on it.

template<typename Iterator>
void SortingAlgorithm_helper(Iterator first, Iterator last)
{
    ...
    SortingAlgorithm(++first, last);
    ...
}

template<typename Container>
void SortingAlgorithm(Container & c)
{
    ...
    SortingAlgorithm_helper(std::begin(c), std::end(c));
    ...
}

This should handle built-in arrays, std::vector, std::array and std::deque. If you limit the operations performed on the iterators to bi-directional (++ and --), then it should handle std::list as well.

user500944 · Accepted Answer · 2012-11-09 20:40:33Z

4

Don't do this. Instead, use one of the following options:

Use a std::vector (it has a size() method) instead of an array.
Pass in the size of the array as an additional argument to your function.

As for recursive algorithms, don't just copy the elements into a new array, it's time consuming.

Instead, pass in two pointers to the beginning and the end of the portion of the array that you want to process (look at how STL algoritms work, std::sort doesn't take a container, instead it takes two iterators).

Note however, that this actually depends on the details of the algorithm you're using, some algorithms may actually require explicit copying, but you should avoid it when possible.

answered Nov 9, 2012 at 20:40

user500944

Comments

stonemetal · Accepted Answer · 2012-11-09 20:43:42Z

1

The template generates code at compile time, specifying a value like 10 allows it to generate code because it knows what value to use. Specifying something that can not be determined at compile time(like a variable that only has a value at run time) means it doesn't know what value to use when generating code.

answered Nov 9, 2012 at 20:43

stonemetal

6,19025 silver badges25 bronze badges

Comments

Darryl · Accepted Answer · 2012-11-09 20:50:41Z

0

The compiler needs to figure out the sizes at compile time, not run time. My compiler accepts your code as written, but apparently yours can't figure out the size. You can explicitly tell it the size like this:

SortingAlgorithm<DataType, SIZE>( newArray );.

Both versions of that line of code work with my compiler.

answered Nov 9, 2012 at 20:50

Darryl

6,3061 gold badge29 silver badges37 bronze badges

Collectives™ on Stack Overflow

C++ Not Requiring Array Length with Recursive Sorting Algorithms

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related