Chyba raczej najpierw przesunąć, a potem dodać element.
Generalnie to takie coś dla dużych tablic zawsze będzie kosztowne. Wiele lepiej niż za pomocą memmove() z raczej tego nie zrobisz. Gdybyś chciał coś takiego naprawdę szybko załatwić, to najlepiej zrobić listę zamiast zwykłej tablicy.
Racja, to jest najtańsze rozwiązanie (chociaż niewiele bardziej od dwustronnej kolejki (czy jak to tam po polsku się nazywa) zaimplementowanej w STL-u, a jest mniej pisania jeśli korzystamy z STL-a). Jeśli chciałbyś wykorzystywać tę tablicę w wielu miejscach programu, to najlepiej opakować ją w klasę, która sama zajęłaby się zarządzaniem logicznymi indeksami (kwestia jednej dodatkowej zmiennej w klasie i dodawania/odejmowania jej od indeksu).