#include <algorithm>
#include <iostream>
#include <iomanip>
#include <memory>
#include <map>
#include <vector>
#include <utility>
#include <string>
#include <locale>
#include <list>
using namespace std;
int main(void)
{
#define DBG(x) cout << left << setw(30) << #x << boolalpha << (x) << endl;
list<string> l = { "one", "two", "three", "four" };
auto one_it = begin(l);
l.emplace_front("zero"); // doesn't invalidate any iterators
l.emplace_front("minus one");
l.emplace_front("minus two");
l.emplace_front("minus three");
l.erase(one_it); // O(1)
for(auto const& s : l) DBG(s);
return 0;
}
I2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8aW9tYW5pcD4KI2luY2x1ZGUgPG1lbW9yeT4KI2luY2x1ZGUgPG1hcD4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPHV0aWxpdHk+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxsb2NhbGU+CiNpbmNsdWRlIDxsaXN0Pgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKCmludCBtYWluKHZvaWQpCnsKI2RlZmluZSBEQkcoeCkgY291dCA8PCBsZWZ0IDw8IHNldHcoMzApIDw8ICN4IDw8IGJvb2xhbHBoYSA8PCAoeCkgPDwgZW5kbDsKCgoJbGlzdDxzdHJpbmc+IGwgPSB7ICJvbmUiLCAidHdvIiwgInRocmVlIiwgImZvdXIiIH07CgoJYXV0byBvbmVfaXQgPSBiZWdpbihsKTsKCglsLmVtcGxhY2VfZnJvbnQoInplcm8iKTsgLy8gZG9lc24ndCBpbnZhbGlkYXRlIGFueSBpdGVyYXRvcnMKCWwuZW1wbGFjZV9mcm9udCgibWludXMgb25lIik7CglsLmVtcGxhY2VfZnJvbnQoIm1pbnVzIHR3byIpOwoJbC5lbXBsYWNlX2Zyb250KCJtaW51cyB0aHJlZSIpOwoKCglsLmVyYXNlKG9uZV9pdCk7IC8vIE8oMSkKCglmb3IoYXV0byBjb25zdCYgcyA6IGwpIERCRyhzKTsKCgoJcmV0dXJuIDA7Cn0K