How to implement a list with an efficient "index of" operation? [closed]

I'm interesting in possible implementation approaches for a quite special variant of a list, with the following requirements:

• Efficient inverse lookup ("index of"): "give me an index of the element associated with handle handle"
  • This is the crucial requirement, that's why it's the one mentioned in the title. At the same time, other standard list operations are also required and can't be inefficient.
• Efficient lookup: "give me an element at index index"
• Efficient insertion: "insert element element after/before index index" or "insert element element after/before element associated with handle handle"
• Efficient deletion: "remove element at index index" or "remove element associated with handle handle"

By saying "handle" I mean an abstract object associated with a collection element, like non-invalidating C++ iterators. In the context of this question, no handles can be invalidated by any of the mentioned operations.

By saying "efficient" I mean O(log(N)) time complexity or faster. Clearly, if some operations can be O(1) - even better.

The implementation can't take arbitrary assumptions about the way the list will be used. In particular, it can't assume that e.g. the size of the list won't change, that the elements will only by appended, etc.

Ideally, the discussed implementation would either...

• be compatible with the interface of C++ std::vector
• implement Java java.util.List

If the description I included above is, by any chance, ambiguous, here is a sketch of a possible implementation, including the time complexity requirements:

C++:

// A sketch of a custom list class, similar to `std::vector` / `std::list`
template<typename T>
class my_list {
private:
    // Implementational details go here

public:
    // Iterator class
    class iterator {
    private:
        // Implementational details go here

    public:
        using value_type = T;

        // Other iterator functionality goes here
    };

    // Inserts an element at the given iterator position
    // Does not invalidate any iterators
    // Required time complexity: O(log(N)) or better
    iterator insert(iterator pos, const T& value);

    // Erases the element at the given iterator position
    // Does not invalidate any iterators
    // Required time complexity: O(log(N)) or better
    iterator erase(iterator pos);

    // Returns the index of the element at the given iterator position
    // Does not invalidate any iterators
    // Required time complexity: O(log(N)) or better
    int index_of(iterator pos);

    // Returns the iterator to the element at the given index
    // Does not invalidate any iterators
    // Required time complexity: O(log(N)) or better
    iterator get_at(std::size_t index) const;
};

Java:

// A sketch of a custom list class, similar to `java.util.List`
public class MyList<T> {
    // Implementation details go here

    // Custom Handle class (like an iterator, but by handle)
    public class Handle {
        // Implementation details go here
    }

    /**
     * Inserts an element at the given handle position.
     * Does not invalidate any handles.
     * Required time complexity: O(log N) or better.
     * @param pos The handle position to insert at.
     * @param value The value to insert.
     * @return Handle to the newly inserted element.
     */
    public Handle insert(Handle pos, T value) {
        // Implementation goes here
        throw RuntimeException("TODO: Implement");
    }

    /**
     * Erases the element at the given handle position.
     * Does not invalidate any handles.
     * Required time complexity: O(log N) or better.
     * @param pos The handle position to erase.
     * @return Handle to the element after the erased one.
     */
    public Handle erase(Handle pos) {
        // Implementation goes here
        throw RuntimeException("TODO: Implement");
    }

    /**
     * Returns the index of the element at the given handle position.
     * Does not invalidate any handles.
     * Required time complexity: O(log N) or better.
     * @param pos The handle position.
     * @return The index of the element.
     */
    public int indexOf(Handle pos) {
        // Implementation goes here
        throw RuntimeException("TODO: Implement");
    }

    /**
     * Returns the handle for the element at the given index.
     * Does not invalidate any handles.
     * Required time complexity: O(log N) or better.
     * @param index Index of the element.
     * @return Handle to the element at the given index.
     */
    public Handle getAt(int index) {
        // Implementation goes here
        throw RuntimeException("TODO: Implement");
    }
}