Versuchs mal mit List.

Der einzige Nachteil ist, dass man nur in linearer Zeit auf ein beliebig indexiertes Element zugreifen kann. (Das geht bei Vector in constant time.)
Ansonsten sind die idR als doppeltverlinkte Zeigerliste implementiert und bieten somit Insertion und Loeschung an beliebigen Stellen sowie vor- und ruecklaeufige Iteration und Vertauschung von Elementen in contant time.
Zudem sind sie Teil der STL. Das wird wohl das beste sein, was du kriegen kannst. Alle von dir genannten Eigenschaften sind in Contant Time einfach nicht umsetzbar.