Prev: ANN: C++ cycliclogs library/commands is promoted to stable status
Next: How to declare the type in the class?
From: Todd Mars on 14 Apr 2008 12:22
Scott Meyers in Effective C++ at the start of the templates section
says that C++ templates are np-complete in the compiler processing.
Does this mean that the use of templates can cause the compile to
execute for an infinite loop or near infinite loop?
Todd.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Carl Barron on 15 Apr 2008 03:28
In article
<d12bdcd3-0e20-4d36-ab16-81d70bad3afd(a)r9g2000prd.googlegroups.com>,
Todd Mars <tamnt54(a)gmail.com> wrote:

> Scott Meyers in Effective C++ at the start of the templates section
> says that C++ templates are np-complete in the compiler processing.
> Does this mean that the use of templates can cause the compile to
> execute for an infinite loop or near infinite loop?
> Todd.

technically np-complete means there is no polynomial bound on the
measuring quantity, If the measuring quantity is N, there does not
exist a const K or an constant m such that processing time < K *N^m.

In simple terms the process gets too slow 'quite fast' after a certain
bound is exceeded.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Daniel Krügler on 15 Apr 2008 03:29
On 15 Apr., 05:22, Todd Mars <tamn...(a)gmail.com> wrote:
> Scott Meyers in Effective C++ at the start of the templates section
> says that C++ templates are np-complete in the compiler processing.
> Does this mean that the use of templates can cause the compile to
> execute for an infinite loop or near infinite loop?
> Todd.

Yes, that could be possible. But the standard has foreseen this
situation and has defined a "barrier" to prevent this[1], e.g.
[temp.inst]/14:

"There is an implementation-defined quantity that specifies the limit
on the total
depth of recursive instantiations, which could involve more than one
template.
The result of an infinite recursion in instantiation is undefined."

HTH & Greetings from Bremen,

Daniel Kr�gler

[1]: "Prevent" does mean here, that the standard moves any such
happening
out of the scope of the standard.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Marcin.Barczynski on 15 Apr 2008 03:32
On Apr 14, 8:22 pm, Todd Mars <tamn...(a)gmail.com> wrote:
> Scott Meyers in Effective C++ at the start of the templates section
> says that C++ templates are np-complete in the compiler processing.
> Does this mean that the use of templates can cause the compile to
> execute for an infinite loop or near infinite loop?

Sure. Consider the following code:

template<int N>
struct Infinity {
enum { val = 1 + Infinity<N + 1>::val };
};

int main() {
Infinity<0> inf;
}

But most compilers (if not all) prevents that by limiting maximum
template depth.
In g++ you can use --ftemplate-depth argument to manipulate this
value.

Marcin.

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Thomas Richter on 15 Apr 2008 03:31
Todd Mars schrieb:
> Scott Meyers in Effective C++ at the start of the templates section
> says that C++ templates are np-complete in the compiler processing.
> Does this mean that the use of templates can cause the compile to
> execute for an infinite loop or near infinite loop?

If compilers would support infinite template recursion, yes. However,
the standard also defines rules on how may levels of template resolution
a compiler has to support, at minimum, and compilers simply abort the
recursion if it is too deep. Thus, templates *would* be NP complete if
there weren't restrictions setup exactly to avoid infinite loops.

So long,
Thomas

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2
Prev: ANN: C++ cycliclogs library/commands is promoted to stable status
Next: How to declare the type in the class?