iterator() on parallel stream guarantee encounter order?

This is an oversight in the specification. If a stream has a defined encounter order, the intent was that its Iterator produce the elements in encounter order. If the stream has no defined encounter order, the Iterator will of course produce the elements in some order, but that order won't be defined.

I've filed bug JDK-8194952 to track the change to the specification.

It looks like others have crawled through enough of the implementation to show that it will indeed produce the elements in encounter order. In addition, our stream tests rely on this property. For example, the test for the toList collector asserts that the elements in the list are present in the same order as they are obtained from the stream's Iterator. So it's probably safe for you to rely on this behavior, even though it isn't formally specified (yet).

The Stream.of method, used to create a stream from otherwise un-associated values, returns an sequential, ordered stream.

Returns a sequential ordered stream whose elements are the specified values.

According to the package Javadocs for java.util.stream, Side Effects section:

IntStream.range(0,5).parallel().map(x -> x*2).toArray() must produce [0, 2, 4, 6, 8]

This implies that parallel() and map() preserve whether the stream is sequential/ordered.

I've traced the implementation of the Stream that Stream.of creates to a class called ReferencePipeline.

@Override
public final Iterator<P_OUT> iterator() {
    return Spliterators.iterator(spliterator());
}

That implementation's iterator() method defers to Spliterator.iterator(), whose code adapts to the Iterator interface by simply relying on the Spliterator's tryAdvance method, and does not change any stream characteristics:

public static<T> Iterator<T> iterator(Spliterator<? extends T> 
    spliterator) {
    Objects.requireNonNull(spliterator);
    class Adapter implements Iterator<T>, Consumer<T> {
        boolean valueReady = false;
        T nextElement;

        @Override
        public void accept(T t) {
            valueReady = true;
            nextElement = t;
        }

        @Override
        public boolean hasNext() {
            if (!valueReady)
                spliterator.tryAdvance(this);
            return valueReady;
        }

        @Override
        public T next() {
            if (!valueReady && !hasNext())
                throw new NoSuchElementException();
            else {
                valueReady = false;
                return nextElement;
            }
        }
    }

    return new Adapter();
}

In conclusion, yes, the order is guaranteed because Stream.of creates a "sequential ordered stream", and none of the operations you use above: parallel, map, or iterator change the characteristics. In fact, iterator uses the underlying Stream Spliterator to iterate over the stream elements.