> I doubt there are any vector implementations that don't use exponential growth.

Trivia fact time: Westwood Studios wrote their own vector implementation for the original Command&Conquer, and reused it for later games in the same series, until Renegade/Generals. That implementation uses linear growth, capacity grows by 10 elements each time.