Диапазон итераторов C ++ с использованием указателей на массив - PullRequest
Новая
       13

Диапазон итераторов C ++ с использованием указателей на массив

0 голосов
/ 01 мая 2019

Вопрос

Я не хочу передавать размер массива в качестве параметра индекса.

Для моего merge_sort я хочу оптимизировать свои параметры, используя концепцию диапазона итераторов. Я не могу понять, как задержать диапазон итераторов и получить доступ к моему массиву. Я могу почтить доступ к индексам, таким как low и high в recursive_merge_sort, но, похоже, нет интуитивно понятного способа доступа к самому массиву. Я использовал это великолепное руководство по C ++ Pointers and Arrays в качестве отправной точки.

Мой Слияние с сортировкой 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] << " ";
    }
}

Комментарий раздела Решение от Байу

Реми Лебо: «Когда вы передаете массив по указателю, вы теряете всю информацию о нем. Вы не можете вернуться к исходному массиву, если указан только указатель / итератор, поскольку разыменование даст вам только один элемент массив, а не сам массив. При передаче массива по указателю у вас нет выбора, кроме как передать размер массива в качестве другого параметра. В противном случае, вместо этого передайте массив по ссылке, и если вам нужно поддерживать массивы разных размеров, тогда используйте шаблон, чтобы компилятор мог определить размер массива для ссылки. "

1 Ответ

1 голос
/ 01 мая 2019

Итераторы смоделированы так, чтобы действовать как указатели. Они имеют один и тот же тип перегруженных операторов: разыменование и инкремент по крайней мере (некоторые также имеют декремент, произвольный доступ и т. Д.).

Самый продвинутый интерфейс итератора - это произвольный доступ, который функционирует точно так же, как необработанный указатель (по замыслу).

Таким образом, все (необработанные) указатели являются в основном итераторами с произвольным доступом в массив (смежный) в стиле 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;
}
...