指针在阵列测试 [英] pointer-in-array test

问题描述

询问您对以下主题的建议：


假设我想知道是否给定指针（例如， p）类型* T

指向T [max]类型的给定数组（例如a）的元素。

实现此目的的一种方法是线性搜索数组：


int ptrInArrSafe（T * p，T * a，int max）

/ *检查p是否指向元素a [max] * /

{

int j = 0;

while（j！= max&& a + j！ = p）++ j;

返回j！= max;

}


显然，这个算法非常慢最大值


更有效的算法是


int ptrInArrUnsafe（T * p，T * a，int max）

/ *检查p是否指向[max]的元素* /

{

int j = pa; / *可能未定义* /

返回0< = j&& j< max&& a + j == p;

}


如果p指向[max]的元素，j将是一个有效的索引并且

返回表达式将评估为true。

如果p未指向[max]的元素，则指针减法可能会导致
调用未定义的行为;垃圾将存储在j中，并且返回表达式的合取中至少有一个
将评估为false。


除了在j中存储垃圾外，理论上，指针减法可以使系统崩溃，重新格式化软盘或唤醒鼻子守护进程，

但到目前为止这在任何平台上都没有发生过与任何编译器

（尝试了几个）。


我的问题是，你是否有这个组的专家看到任何真正的问题

第二种算法？或者，有没有比第一个更快的算法

，它不会调用未定义的行为？


提前谢谢，

Ike

Hi,

Asking your advice on the following subject:

Suppose I want to find out whether a given pointer (say, p) of type *T
points to an element of a given array (say, a) of type T[max].
A way to achieve this would be a linear search through the array:

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=0;
while (j!=max && a+j!=p) ++j;
return j!=max;
}

Obviously, this algorithm is terribly slow for large max.

A more efficient algorithm is

int ptrInArrUnsafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=p-a; /* possibly undefined */
return 0<=j && j<max && a+j==p;
}

If p points to an element of a[max], j will be a valid index and
the return expression will evaluate to true.
If p does not point to an element of a[max], the pointer subtraction may
invoke undefined behaviour; garbage will be stored in j, and at least one
of the conjuncts of the return expression will evaluate to false.

Apart from storing garbage in j, the pointer subtraction could, in theory,
crash the system, re-format the floppy disk or wake up nasal daemons,
but this has not happened so far on any platform with any compiler
(tried several).

My question is, do you experts in this group see any real problem with
the second algorithm? Alternatively, would there be a faster algorithm
than the first one, that does not invoke undefined behaviour?

Thanks in advance,
Ike

推荐答案

2004年4月7日星期三02:17:47 GMT，Ike Naar< no **** @ nospam.invalid> ;

写道：

On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam.invalid>
wrote:

询问您对以下主题的建议：

假设我想知道类型* T
的给定指针（比方说，p）是否指向类型为T [max]的给定数组（例如a）的元素。
一种实现的方法这将是通过数组的线性搜索：

int ptrInArrSafe（T * p，T * a，int max）
/ *检查p是否指向[max]的元素* /
{j / 0;
而（j！= max&& a + j！= p）++ j;
返回j！= max ;


显然，这个算法对于大的最大速度非常慢。

一个更有效的算法是

int ptrInArrUnsafe（T * p，T * a，int max）
/ *检查p是否指向[max]的元素* /
{zh / // int j = p-a; / *可能未定义* /
返回0< = j&& j< max&& a + j == p;
}
如果p指向[max]的元素，j将是一个有效的索引，并且返回表达式将评估为true 。
如果p没有指向[max]的元素，指针减法可能会调用未定义的行为;垃圾将存储在j中，并且返回表达式的合取中至少有一个将评估为false。

除了在j中存储垃圾之外，从理论上讲，指针减法可以
崩溃系统，重新格式化软盘或唤醒鼻子守护进程，
但到目前为止在任何平台上都没有发生任何编译器
（尝试过几次）。

我的问题是，你是否在这个小组的专家看到第二个算法的任何真正的问题？或者，是否有比第一个算法更快的算法，它不会调用未定义的行为？

Hi,

Asking your advice on the following subject:

Suppose I want to find out whether a given pointer (say, p) of type *T
points to an element of a given array (say, a) of type T[max].
A way to achieve this would be a linear search through the array:

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=0;
while (j!=max && a+j!=p) ++j;
return j!=max;
}

Obviously, this algorithm is terribly slow for large max.

A more efficient algorithm is

int ptrInArrUnsafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=p-a; /* possibly undefined */
return 0<=j && j<max && a+j==p;
}

If p points to an element of a[max], j will be a valid index and
the return expression will evaluate to true.
If p does not point to an element of a[max], the pointer subtraction may
invoke undefined behaviour; garbage will be stored in j, and at least one
of the conjuncts of the return expression will evaluate to false.

Apart from storing garbage in j, the pointer subtraction could, in theory,
crash the system, re-format the floppy disk or wake up nasal daemons,
but this has not happened so far on any platform with any compiler
(tried several).

My question is, do you experts in this group see any real problem with
the second algorithm? Alternatively, would there be a faster algorithm
than the first one, that does not invoke undefined behaviour?

如果你的系统支持可选的intptr_t类型，你可以转换p，

a，+ 1到整数并确定正确答案而不用担心

未定义的行为。

<<删除del电子邮件>>

If your system supports the optional intptr_t type, you can convert p,
a, and a+1 to integers and determine the correct answer without fear
of undefined behavior.
<<Remove the del for email>>

2004年4月7日星期三02:17:47 GMT，Ike Naar< no **** @ nospam.invalid>

写道：

On Wed, 07 Apr 2004 02:17:47 GMT, Ike Naar <no****@nospam.invalid>
wrote:

询问你对以下主题的建议：

假设我想找出来类型* T
的给定指针（例如，p）是否指向类型为T [max]的给定数组（例如，a）的元素。
实现此目的的一种方法是线性的搜索数组：

int ptrInArrSafe（T * p，T * a，int max）
/ *检查p是否指向[max]的元素* /
{
int j = 0;
while（j！= max&& a + j！= p） ++ j;
返回j！= max;
}
很明显，这个算法对于大的最大值来说非常慢。

一个更有效的算法是什么？

int ptrInArrUnsafe（T * p，T * a，int max）
/ *检查p是否指向[max]的元素* /
{
int j = pa; / *可能未定义* /
返回0< = j&& j< max&& a + j == p;
}
如果p指向[max]的元素，j将是一个有效的索引，并且返回表达式将评估为true 。
如果p没有指向[max]的元素，指针减法可能会调用未定义的行为;垃圾将存储在j中，并且返回表达式的合取中至少有一个将评估为false。

除了在j中存储垃圾之外，从理论上讲，指针减法可以
崩溃系统，重新格式化软盘或唤醒鼻子守护进程，
但到目前为止在任何平台上都没有发生任何编译器
（尝试过几次）。

我的问题是，你是否在这个小组的专家看到第二个算法的任何真正的问题？或者，是否有比第一个算法更快的算法，它不会调用未定义的行为？

Hi,

Asking your advice on the following subject:

Suppose I want to find out whether a given pointer (say, p) of type *T
points to an element of a given array (say, a) of type T[max].
A way to achieve this would be a linear search through the array:

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=0;
while (j!=max && a+j!=p) ++j;
return j!=max;
}

Obviously, this algorithm is terribly slow for large max.

A more efficient algorithm is

int ptrInArrUnsafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=p-a; /* possibly undefined */
return 0<=j && j<max && a+j==p;
}

If p points to an element of a[max], j will be a valid index and
the return expression will evaluate to true.
If p does not point to an element of a[max], the pointer subtraction may
invoke undefined behaviour; garbage will be stored in j, and at least one
of the conjuncts of the return expression will evaluate to false.

Apart from storing garbage in j, the pointer subtraction could, in theory,
crash the system, re-format the floppy disk or wake up nasal daemons,
but this has not happened so far on any platform with any compiler
(tried several).

My question is, do you experts in this group see any real problem with
the second algorithm? Alternatively, would there be a faster algorithm
than the first one, that does not invoke undefined behaviour?

如果你的系统支持可选的intptr_t类型，你可以转换p，

a，+ 1到整数并确定正确答案而不用担心

未定义的行为。

<<删除del电子邮件>>

If your system supports the optional intptr_t type, you can convert p,
a, and a+1 to integers and determine the correct answer without fear
of undefined behavior.
<<Remove the del for email>>

Ike Naar写道：

Ike Naar wrote:

假设我想知道是否给定指针（例如，p）类型
* T指向给定数组（例如，a）类型为T [max]的元素。
实现此目的的一种方法是通过数组进行线性搜索：

int ptrInArrSafe（T * p，T * a，int max）
/ *检查p是否指向[max]的元素* /
{
int j = 0;
while（j！= max&& a + j！= p）++ j;
返回j！= max;
}

显然，这个算法对于大的最大速度非常慢。

更高效算法是

int ptrInArrUnsafe（T * p，T * a，int max）
/ *检查p是否指向[max]的元素* /
{
int j = pa; / *可能未定义* /
返回0< = j&& j< max&& a + j == p;
}

....剪...
我的问题是，你是否有这个小组的专家看到任何真正的问题
用第二个算法？或者，是否会有比第一个算法更快的算法，不会调用未定义的行为？

Suppose I want to find out whether a given pointer (say, p) of type
*T points to an element of a given array (say, a) of type T[max].
A way to achieve this would be a linear search through the array:

int ptrInArrSafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=0;
while (j!=max && a+j!=p) ++j;
return j!=max;
}

Obviously, this algorithm is terribly slow for large max.

A more efficient algorithm is

int ptrInArrUnsafe(T *p,T *a,int max)
/* check whether p points to an element of a[max] */
{
int j=p-a; /* possibly undefined */
return 0<=j && j<max && a+j==p;
}
.... snip ...
My question is, do you experts in this group see any real problem
with the second algorithm? Alternatively, would there be a faster
algorithm than the first one, that does not invoke undefined
behaviour?

这就是那种东西你把文件标记为系统

依赖代码，并包含两个版本，由一些

定义控制。


但是我会仔细研究这样一个例子的原因，并试图首先避免它。


安全版本可能是稍微加快：


/ *检查p是否指向[max]的元素* /

int ptrInArrSafe（T * p，const T * a，int max）

{

T * pp;


for（pp = a + max; a< pp; a ++）

如果（p == a）返回1;

返回0;

}


将有效但不可引用的指针视为一个（值pp）的结尾，而不是a。这可能是也可能不是你想要的
。


-

查克F（cb ****** **@yahoo.com）（cb********@worldnet.att.net）

可用于咨询/临时嵌入式和系统。

< ; HTTP：//cbfalconer.home.att.net>使用worldnet地址！

This is the sort of thing that you put in a file marked as system
dependant code, and include both versions, controlled by some
define.

However I would look closely at the reason for having such a
routine, and try to avoid it in the first place.

The safe version can possibly be slightly sped up by:

/* check whether p points to an element of a[max] */
int ptrInArrSafe(T *p, const T *a, int max)
{
T *pp;

for (pp = a + max; a < pp; a++)
if (p == a) return 1;
return 0;
}

which treats the valid, but undereferenceable, pointer one past
the end of a (value pp) as not within a. This may or may not be
what you want.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

这篇关于指针在阵列测试的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！