Can't you have a regular vector and place the place the appended items on the even indices and prepended items on the odd? If you keep count of how many prepended and appended items you have you have identical performance to a regular vector except a worst case doubling of memory.