I'm wondering which abstract type (set, map, ...) is the most useful to
implement the following 3 methods: given a set of values, that are
unique and ordered (it exists a "compare" function), it is necessary, in
addition to the "add" and "remove element" methods, to have a "next"
method. The next method takes as parameter one element of the set, and
must return the immediatelly next element of the set, according to the
provided compare function.
    

If I understand correctly your needs, you could use sets as provided
by the standard library with the following definition of "next":

module S = Set.Make(...)

let next elt s =
  let (below, present, above) = S.split elt s in
  assert (present);
  S.min_elt above

This should run in logarithmic time, although the constant factor
might be a little high.

Hope this helps,

- Xavier Leroy