Feature request: shift_insert

[TethysSvensson]

I would like to be able to insert an element at a particular index in the indexmap (knowning full well, that this will cause O(n) move operations).

[cuviper]

I suppose if the item already exists at any index, you want it moved to the new location?

Rough sketch:

    pub fn insert_at(&mut self, index: usize, key: K, value: V) -> Option<V> {
        let (i, old) = self.insert_full(key, value);
        if i < index {
            // TODO: adjust `indices` too
            self.entries[i..=index].rotate_left(1);
        } else if i > index {
            // TODO: adjust `indices` too
            self.entries[index..=i].rotate_right(1);
        }
        old
    }

The crude way to update indices is IndexMapCore::rebuild_hash_table -- reinserting everything, but at least we have saved hashes. We can probably do better though, more like the heuristics in shift_remove.

[TethysSvensson]

I suppose if the item already exists at any index, you want it moved to the new location?

For my particular use-case I wish to keep the item at the current index, but I need to modify it as well. However, performance is not very critical at all, so I am completely okay with handling this by doing a second lookup.

I think you are right, that the most reasonable behavior would be to move the item it.

I guess the way to completely support my use-case would be to add shift_insert methods to both VacantEntry and OccupiedEntry, but I am not sure if this is worth the added complexity. Then I guess you could also add a or_shift_insert to Entry.

[cuviper]

Please see #176 for a move_index method that I think would be useful to you. That does the hard part of updating indices, and then we can possibly build new insertion or entry methods on top of that.