templated types are supposed to follow
a "concept" (Input Iterator, Forward
Iterator, etc...) where the actual
details of the concept are defined
entirely by the implementation of the
template function/class, and not by
the class of the type used with the
template, which is a somewhat
anti-usage of OOP.
I think you misunderstand the intended use of concepts by templates. Forward Iterator, for example, is a very well-defined concept. To find the expressions which must be valid in order for a class to be a Forward Iterator, and their semantics including computational complexity, you look at the standard or at http://www.sgi.com/tech/stl/ForwardIterator.html (you have to follow the links to Input, Output, and Trivial Iterator to see it all).
That document is a perfectly good interface, and "the actual details of the concept" are defined right there. They are not defined by the implementations of Forward Iterators, and neither are they defined by the algorithms which use Forward Iterators.
The differences in how interfaces are handled between STL and Java are three-fold:
1) STL defines valid expressions using the object, whereas Java defines methods which must be callable on the object. Of course a valid expression might be a method (member function) call, but it doesn't have to be.
2) Java interfaces are runtime objects, whereas STL concepts are not visible at runtime even with RTTI.
3) If you fail to make valid the required valid expressions for an STL concept, you get an unspecified compilation error when you instantiate some template with the type. If you fail to implement a required method of a Java interface, you get a specific compilation error saying so.
This third part is if you like a kind of (compile-time) "duck typing": interfaces can be implicit. In Java, interfaces are somewhat explicit: a class "is" Iterable if and only if it says it implements Iterable. The compiler can check that the signatures of its methods are all present and correct, but the semantics are still implicit (i.e. they're either documented or not, but only more code (unit tests) can tell you whether the implementation is correct).
In C++, like in Python, both semantics and syntax are implicit, although in C++ (and in Python if you get the strong-typing preprocessor) you do get some help from the compiler. If a programmer requires Java-like explicit declaration of interfaces by the implementing class, then the standard approach is to use type traits (and multiple inheritance can prevent this being too verbose). What's lacking, compared with Java, is a single template which I can instantiate with my type, and which will compile if and only if all the required expressions are valid for my type. This would tell me whether I've implemented all the required bits, "before I use it". That's a convenience, but it's not the core of OOP (and it still doesn't test semantics, and code to test semantics would naturally also test the validity of the expressions in question).
STL may or may not be sufficiently OO for your taste, but it certainly separates interface cleanly from implementation. It does lack Java's ability to do reflection over interfaces, and it reports breaches of interface requirements differently.
you can tell the function ... expects a Forward Iterator only by
looking at its definition, where you'd need either to look at the
implementation or the documentation for ...
Personally I think that implicit types are a strength, when used appropriately. The algorithm says what it does with its template parameters, and the implementer makes sure those things work: it's exactly the common denominator of what "interfaces" should do. Furthermore with STL, you're unlikely to be using, say, std::copy based on finding its forward declaration in a header file. Programmers should be working out what a function takes based on its documentation, not just on the function signature. This is true in C++, Python, or Java. There are limitations on what can be achieved with typing in any language, and trying to use typing to do something it doesn't do (check semantics) would be an error.
That said, STL algorithms usually name their template parameters in a way which makes it clear what concept is required. However this is to provide useful extra information in the first line of the documentation, not to make forward declarations more informative. There are more things you need to know than can be encapsulated in the types of the parameters, so you have to read the docs. (For example in algorithms which take an input range and an output iterator, chances are the output iterator needs enough "space" for a certain number of outputs based on the size of the input range and maybe the values therein. Try strongly typing that.)
Here's Bjarne on explicitly-declared interfaces: http://www.artima.com/cppsource/cpp0xP.html
In generics, an argument must be of a
class derived from an interface (the
C++ equivalent to interface is
abstract class) specified in the
definition of the generic. That means
that all generic argument types must
fit into a hierarchy. That imposes
unnecessary constraints on designs
requires unreasonable foresight on the
part of developers. For example, if
you write a generic and I define a
class, people can't use my class as an
argument to your generic unless I knew
about the interface you specified and
had derived my class from it. That's
rigid.
Looking at it the other way around, with duck typing you can implement an interface without knowing that the interface exists. Or someone can write an interface deliberately such that your class implements it, having consulted your docs to see that they don't ask for anything you don't already do. That's flexible.