Как реализовать список с эффективной операцией «индекс»? [закрыто] ⇐ C++

[Anonymous]

Меня интересуют возможные подходы к реализации совершенно особого варианта списка со следующими требованиями:

• Эффективный обратный поиск («индекс»): «дайте мне индекс элемента, связанного с дескриптором дескриптора»
  
  Это важнейшее требование, поэтому оно упомянуто в заголовке. В то же время другие стандартные операции со списками также необходимы и не могут быть неэффективными.

[*]Эффективный поиск: «дайте мне элемент по индексу индекса»
[*]Эффективная вставка: «вставить элемент элемента после/перед индексом индекса» или «вставить элемент элемент после/перед элементом, связанным с дескриптором» handle"
[*]Эффективное удаление: "удалить элемент по индексу index" или "удалить элемент, связанный с дескриптором handle"

Под словом "handle" я имею в виду абстрактный объект, связанный с элементом коллекции, например, неинвалидирующие итераторы C++. В контексте этого вопроса никакие дескрипторы не могут быть признаны недействительными ни одной из упомянутых операций.
Говоря «эффективный», я имею в виду временную сложность O(log(N)) или быстрее. Очевидно, что если некоторые операции могут быть O(1) — даже лучше.
Реализация не может принимать произвольных предположений о том, как будет использоваться список. В частности, он не может предполагать, что, например. размер списка не изменится, элементы будут только добавляться и т. д.
В идеале обсуждаемая реализация должна либо...

• быть совместимой с интерфейсом C++ std::vector
• реализовать Java java.util.List

Если описание, которое я включил выше, случайно не соответствует неоднозначно, вот набросок возможной реализации, включая требования к временной сложности:
C++:
// A sketch of a custom list class, similar to `std::vector` / `std::list`
template
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 {
// 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");
}
}


Подробнее здесь: https://stackoverflow.com/questions/798 ... -operation