C++ Iterator range using pointers to an array

Question

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."

[Please read this SO post and answers](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c), 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. — PaulMcKenzie, Apr 30 '19 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. — greg, Apr 30 '19 at 21:51
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. — Remy Lebeau, Apr 30 '19 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. — greg, Apr 30 '19 at 22:34

Cruz Jean · Accepted Answer · 2019-04-30T22:07:27.130

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;
}

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? — greg, Apr 30 '19 at 22:01
@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? — Cruz Jean, Apr 30 '19 at 22:10
@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. — , Apr 30 '19 at 22:21

C++ Iterator range using pointers to an array

1 Answers1