Você pode usar o método [`insert()`][1], mas precisa criar um iterador:

    #include <iostream>
    #include <vector>
     
    int main () {
        std::vector<int> vec {1, 2, 3, 4, 5, 6, 7, 8, 9};
        auto it = vec.begin();
        vec.insert(it + 3, 10);
        for (auto x: vec) std::cout << ' ' << x;
    }

Veja [funcionando no **ideone**][2]. E [no **repl.it**][3]. Também [coloquei no **GitHub** para referência futura][4].

Se fizer corretamente, medir e a performance não agradar, então precisa usar outra estrutura que tenha outros compromissos. Um `list` pode ser uma opção. Ela pode fazer inserção no meio com complexidade O(1). Mas outras operações não são tão rápidas quanto o `vector`.Não conserte uma coisa e quebre outra. Veja o que é prioridade. Quem sabe outra estrutura seja mais adequada. Não existe estrutura perfeita onde tudo ótimo.


  [1]: http://en.cppreference.com/w/cpp/container/vector/insert
  [2]: https://ideone.com/7bg4Er
  [3]: https://repl.it/@maniero/InsertElementscpp
  [4]: https://github.com/maniero/SOpt/blob/master/CPP/Vector/InsertElements.cpp