使用指向数组的指针的 C++ 迭代器范围

Question

问题

我不想将数组的大小作为索引参数传递。

对于我的 merge_sort，我想使用迭代器范围概念优化我的参数。我似乎无法弄清楚如何引用迭代器范围并访问我的数组。我可以尊重访问 recursive_merge_sort 中的 low 和 high 等索引，但似乎没有一种直观的方法来访问数组本身.我一直在使用这个很棒的指南 C++ Pointers and Arrays作为起点。

我的 Merge Sort C++11 C++17这个问题揭示了这个概念，我喜欢使用迭代器范围来减少我的排序参数数量的想法。

代码

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

来自bayou的评论区解决方案

Remy Lebeau:“当你通过指针传递一个数组时，你会丢失关于它的所有信息。你无法返回到只给定一个指针/迭代器的原始数组，因为取消引用只会给你一个元素数组，而不是数组本身。当通过指针传递数组时，您别无选择，只能将数组大小作为另一个参数传递。否则，通过引用传递数组，如果您需要支持不同大小的数组，则使用模板，以便编译器可以推断出引用的数组大小。”

Answer 1

迭代器被建模为像指针一样工作。它们具有相同类型的重载运算符:至少是取消引用和递增(有些还具有递减、随机访问等)。

最先进的迭代器接口(interface)是随机访问，其功能与原始指针完全一样(按设计)。

所以所有(原始)指针基本上都是 C 风格(连续)数组中的随机访问迭代器。查看以下内容以可视化 C 样式数组的开始/结束迭代器:

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.

所以基本上，您只需将开始迭代器视为数组的前端，并且您不会在开始迭代器之前、结束迭代器处或结束迭代器之后的任何位置取消引用，因为标准 C++ 约定规定结束迭代器为 1超过范围的末尾。

这是一个像迭代器一样使用指针的例子:

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