You should probably try to avoid this flexibility. Quote from Item 2 "Beware the illusion of container-independent code" from Effective STL by Scott Meyers:
Face the truth: it's not worth it. The different containers are different, and they have strengths and weaknesses that vary in significant ways. They're not designed to be interchangeable, and there's littel you can do to paper that over. If you try, you're merely tempting fate, and fate doesn't like to be tempted.
If you really, positively, definitely have to maintain valid iterators, use std::list
. If you also need to have random access, try Boost.MultiIndex (although you'll lose contiguous memory access).
If you look at the standard container adapators (std::stack
, std::queue
) you see that they support the intersection of the adaptable containers interfaces, not their union.