C++11 标准特性:指向数组首元素和尾后元素的指针(附归并排序代码)
程序员文章站
2022-03-21 16:33:42
...
数组是以指针形式传递给函数的,所以函数一开始并不知道数组的确切尺寸,所以应该提供一些额外的信息。C++中常用方法有两种:1. 显示地传递一个表示数组大小的形参,这也是C语言和C++11标准之前常用的; 2. 在C++11标准中,可以传递指向数组首元素和尾后元素的指针,下面的代码我用了这种方法。这类似于容器类型的迭代器,但因为数组不是类类型,所以这两个函数不是成员函数,使用方法为:
int * beg = std::beging(array_name);
int * end = std::end(array_name);
这两个函数在iterator头文件中。这两个函数使得指针的使用更简单,更安全,避免下标越界或者访问非法指针造成segmentation error,前提是正确计算指针的位置。
特别注意,尾后指针不可以解引用和递增操作。
实现数组的归并排序(Merge Sort)
#include <iostream>
#include <iterator>
void swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
void print_array(const int *beg, const int *end)
{
while(beg != end)
{
std::cout << *beg++ << " ";
}
std::cout << "\n";
}
void merge(const int *beg, const int *end, int *result_ptr)
{
int left_length = (end - beg) / 2;//左部分区间的数据元素的个数
const int *left_ptr = beg;
const int *right_ptr = beg + left_length;
while(left_ptr != beg + left_length && right_ptr != end)
{
//对分别已经排好序的左区间和右区间进行合并
if(*left_ptr <= *right_ptr)
*result_ptr++ = *left_ptr++;
else
*result_ptr++ = *right_ptr++;
}
while(left_ptr != beg + left_length)
*result_ptr++ = *left_ptr++;
while(right_ptr != end)
*result_ptr++ = *right_ptr++;
}
void merge_sort(int * beg, int * end, int *result_ptr)
{
if((end - beg) == 1 || beg == end)//如果只有1或0个元素,则不用排序
return;
else if (end - beg == 2)
{
if (*beg > *(end-1))
{
swap(*beg, *(end-1));
}
}
else
{
//继续划分子区间,分别对左右子区间进行排序
merge_sort(beg, (end-beg)/2+beg, result_ptr);
merge_sort((end-beg)/2+beg, end, result_ptr);
//开始归并已经排好序的start到end之间的数据
merge(beg, end, result_ptr);
//把排序后的区间数据复制到原始数据中去
while(beg != end)
*beg++ = *result_ptr++;
}
}
int main(void)
{
int array[9] = {9,7,5,8,2,4,1,3,6};
int result[9];
int * beg = std::begin(array);
int * end = std::end(array);
int * result_ptr = std::begin(result);
std::cout << "before sorting" << std::endl;
print_array(beg, end);
merge_sort(beg, end, result_ptr);
beg = std::begin(result);
end = std::end(result);
std::cout << "after sorting" << std::endl;
print_array(beg, end);
return 0;
}
上一篇: C++11 常用新特性总结