I was recently faced with this (luckily I realized it before coming across any strange bugs), and realized std::deque works great for this if you don’t need random access (which was fine for my use-case because I just grabbed references immediately after insertion).