0

Question

I do not want to pass the size of the array as an index parameter.

For my merge_sort, I want to optimize my parameters using the iterator range concept. I can't seem to figure out how to deference the iterator range and access my array. I can deference to access the indices like low and high in recursive_merge_sort, but there does not seem to be an intuitive way to access the array itself. I've been using this great guide on C++ Pointers and Arrays as a starting point.

My Merge Sort C++11 C++17 question brought this concept to light and I like the idea of using iterator ranges to reduce the number of parameters for my sort.

Code

void recursive_merge_sort(int* low, int* high) { // deference to get starting index "low" and ending index "high" if(*(low) >= *(high) - 1) { return; } int mid = *(low) + (*(high) - *(low))/2; // what's the correct syntax to access my array from the iterator range // int* d = some how deference low or how to get the data array they iterate on recursive_merge_sort_v(d + low, d + mid); recursive_merge_sort_v(d + mid, d + high); merge(d + low, mid, d + high); // delete d; } void merge_sort(int* data) { // what's the correct syntax to access my array from the passed in iterator range // is this event possible? incorrect syntax below recursive_merge_sort(data + 0, data + std::size(*(data))); } int main() { int data[] = { 5, 1, 4, 3, 65, 6, 128, 9, 0 }; int num_elements = std::size(data); std::cout << "unsorted\n"; for(int i=0; i < num_elements; ++i) { std::cout << data[i] << " "; } merge_sort(data); std::cout << "\nsorted\n"; for(int i=0; i < num_elements; ++i) { std::cout << data[i] << " "; } }

Comment section Solution from the bayou

Remy Lebeau: "When you pass an array by pointer, you lose all information about it. You can't get back to the original array given only a pointer/iterator, as dereferencing will only give you a single element of the array, not the array itself. When passing an array by pointer, you have no choice but to pass the array size as another parameter. Otherwise, pass the array by reference instead, and if you need to support arrays of different sizes then use a template so the compiler can deduce the array size for the reference."

Improve this question
5
  • Pass the size of the array as an extra parameter. Commented Apr 30, 2019 at 21:40
  • Please read this SO post and answers, and read the "Merge Sort" section. You see that your version lacks a way to compare two generic items, something a sorting algorithm should be able to provide. Commented Apr 30, 2019 at 21:41
  • @0x499602D2 I want to avoid passing in any extra params and want to use iterators in place of passing in the array size. Commented Apr 30, 2019 at 21:51
  • 1
    When you pass an array by pointer, you lose all information about it. You can't get back to the original array given only a pointer/iterator, as dereferencing will only give you a single element of the array, not the array itself. When passing an array by pointer, you have no choice but to pass the array size as another parameter. Otherwise, pass the array by reference instead, and if you need to support arrays of different sizes then use a template so the compiler can deduce the array size for the reference. Commented Apr 30, 2019 at 22:26
  • @RemyLebeau I'll change to my previous approach, thanks for the clarification and for taking time out of your busy schedule with the Fox Disney deal. Commented Apr 30, 2019 at 22:34

1 Answer 1

Reset to default
1

Iterators are modeled to act like pointers. They have the same type of overloaded operators: dereferencing and increment at the very least (some also have decrement, random access, etc.).

The most advanced iterator interface is random access, which functions exactly like a raw pointer (by design).

So all (raw) pointers are basically random access iterators into a C-style (contiguous) array. Look at the following to visualize begin/end iterators for a C-style array:

int vals[] = { 0, 1, 2, 3, 4 }; int *begin = vals; int *end = vals + 5; 
v vals[] 0 1 2 3 4 ... ^ begin ^ end (1 past the end of array) vals[2] == begin[2] vals[4] == begin[4] etc.

So basically, you just treat the begin iterator as the front of the array, and you just don't dereference anywhere before the begin iterator, nor at or past the end iterator, as standard C++ convention dictates the end iterator is 1 past the end of the range.

Here's an example of using pointers like iterators:

void print(int *begin, int *end) { // for each element in the range (starting at begin, up to but not including end) for (; begin != end; ++begin) { // print the element std::cout << *begin << '\n'; } } int main() { // declare a C-style array int arr[] = { 10, 5, 2, 6, 20 }; // for the sake of example, print only the middle 3 elements // begin = arr + 1 // end = arr + 4 print(arr + 1, arr + 4); return 0; }
Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Now let's say I pass an iterator like this int *end = vals + 5; to a function, is it possible to access vals from *end? Or do I only have access to the ending index 5 from such a parameter?
@GregDegruy Ok, added an example for printing contents of an iterator range. Does that answer your question for how to access elements from an iterator range?
@GregDegruy No, if your function gets the address or value pointed by the pointer "end", you will have no information of the integer 5, hence, you will not know of "vals" in C. But, you can make your own pointer implementation that has an init pointer and an offset integer (e.g. ptr *start = vals + 0 and ptr *end = vals + 5), and pass that to anywhere you like. This way you can use a single "ptr" data structure.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.