#include <algorithm> #include <memory> struct slist_node_base { slist_node_base(slist_node_base *next) : next(next) {} slist_node_base *next; }; template <typename T> class slist { struct node : slist_node_base { template <typename... Args> node(node *n, Args&&... args) : slist_node_base(n), data(std::forward<Args>(args)...) {} node(node const&)=delete; node& operator=(node const&)=delete; node* next() { return static_cast<node*>(slist_node_base::next); } void set_next(node* n) { slist_node_base::next = n; } T data; }; slist_node_base pointer_to_first; node* data() { return static_cast<node*>(&pointer_to_first); } public: slist() : pointer_to_first(data()) {} ~slist() { for (node *n = data()->next(); n!=data();) { std::unique_ptr<node> tmp(n); // Keks für cooky451 n = n->next(); } } slist(slist const& o) =delete; // Ja, ich bin faul. slist& operator=(slist const& o) =delete; // Es fehlen noch die ganzen Range-Funktionen class iterator { friend class slist; slist_node_base *n; iterator (node *n) : n(n) {} // UB wenn n == end() node *as_node() { return static_cast<node*>(n); } public: typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; typedef T value_type; typedef T* pointer; typedef T& reference; iterator& operator++() { n = n->next; return *this; } iterator operator++(int) { iterator tmp = this; n = n->next; return tmp; } bool operator==(const iterator& o) const { return n == o.n; } bool operator!=(const iterator& o) const { return n != o.n; } T& operator* () { return as_node()->data; } T* operator->() { return &as_node()->data; } }; template <typename... Args> iterator emplace_after(iterator i, Args&&... args) { node *n = new node(i.as_node()->next(), std::forward<Args>(args)...); i.as_node()->set_next(n); return n; } iterator erase_after(iterator i) { std::unique_ptr<node> to_be_deleted(i.as_node()->next()); // Keks für cooky451 node *ret = to_be_deleted->next(); i.as_node()->set_next(ret); return ret; } iterator insert_after(iterator i, T const& x) { return emplace_after(i, x); } iterator insert_after(iterator i, T&& x) { return emplace_after(i, std::move(x)); } iterator emplace_front(T const& x) { return emplace_after(end(), x); } iterator push_front(T const& x) { return emplace_front(x); } iterator push_front(T&& x) { return emplace_front(std::move(x)); } void pop_front() { erase_after(data()); } iterator begin() { return data()->next(); } iterator end() { return data(); } }; #include <iostream> #include <iterator> int main() { srand(0); slist<char> l; slist<char>::iterator it = l.begin(); for (int i = 10000000; --i;) { if (it != l.end()) { if (rand()%2) { it = l.insert_after(it, 'a' + (unsigned char)rand() %26); } else { slist<char>::iterator after = it; ++after; if (after == l.end()) goto add_front; it = l.erase_after(it); } } else { add_front: l.push_front('a' + (unsigned char)rand() %26); it = l.begin(); } } std::ios_base::sync_with_stdio(false); std::copy(l.begin(), l.end(), std::ostream_iterator<char>(std::cout, "")); }
Standard input is empty
yxpkbooaaxeezylmxganlmcfbtdrqfnynkfsyijzfqcukaursqdmhkldxttktzdktfwvlsldzpheohhmiydfpzdrklomkbwkthvzeyrbjfjscqudeiolqlanjnunpnqjrqaunukhrxtkkzzgtrnaiwreetbfnpeycduvljkhidpqkkmnjuczuscrhbqqvnmarxglskmdzujmlijocjtfcroyxsyqunmdfqjcwjsdazwthtkxwmaflmczsocoxhmyhjajckrdxiqgzlbtvamnubfgoxmudctqgapkgpehthabwjdjevupdcpdshzajdgumyoinfkgkacteaqnpilrmpfukvqwegpnpxizwyuvlmjyjlaokocdrkdxldgwhpnrfzdzhxbyjqmmupcgusckyhtiazoptgfzogpfgouekivunoyziswqgeypofxsffrqjzuipqubousvryyafrxwjhnbevsxurzmzjzgiwhboecsvhznbfzuwxrjidxtlnwudaduosuzvveofjtoncuhhaiwkuzocqxufjwynsvldqfpztutzpcrwhwbvwsibjcmfarfnopqawhocjazrkqsgbjqryxojliwybmnktpqhnjqpobyrnuxhgzccoubvpdcdtkcstfhgfybptgjhgvmduuqnlamxkfotbpqiqwwatpdpmihjjaknenczbuspijuphnqwhjvrrqaqygbfqxlrizkfhejokugyinhfyuwwgnvnebwhiulajoeihdnzwvfsttcdwrbopneaaftyiliabiisqdnxnyyfqoqcxkdhklsqgwdonazwppqnzuiacdsjaxbqqszwmcbsuwlgtjojycmvxxfqpfrrjrzbokdnqiccrekgsnepbnrfqodtcgbfcleplvefflhylclejhrastdcpztuffehsmdsovqwwcsgiiuxdflheipdsgntewrcnmumqryoppuusigshoawuvicjyupndcywrwupbchxfitaaakagaovqfysoyvnekfgllczmmlaehqudiypanhkjdoxvqndwjapjkgogpvrotkrnilwlhjfrauczmygjrsxovogvjseencuxeoyytsfruocoofdxtjgcgroaovwyosjwjzrdoddcwxyuqpbuvetsrsmkbfjiyvziojmxjjmpccpcvselhxoosdixkopahlguzclfzmyulirqmblkhyvebrttppaqqehzxobsrkbzvvebuafvedkuskbblgktzfogtuhfdpmjuxeevpezficxzxufhxmhqptuhyisrvyvcxdzpihthxnijelmijtuvcvsclyckgvyzruqhhqsppdpbopzvrglczovlscijucvgoutvsphlgmmlgrjgxwqsygnuxqoqspsfibnvkmrbtzlfgcxblrpacsjttecuydmwvudvcwhwxxlztlkkrepkjbbgijeipupzzvjbglmfqtivjkqxnvcuoqzriadcsqkqvsvqcwfrcsymrrothwusrzmvjpcehgiwlnkmqlpmmhpaclrghcyaywnkstbmxmladcatvxwxhwgjrbioyjoslamxeroflnmpxyflitcayfmiitaawfihukeyglfgjujtyqumsywdeabqmzlrydimhjefkoicoxinddbwcwkverqteobzitkqlskvqjnwmkhmkkypnzznmbbumtedaciesicadugzndkrlvtmdmmvqjwsujpomgzldmufjrkiewjukecwlegntvslvwjpupqdahpfolcqzcnnygrnhyrfjrfbhploeeolqjhppptzoqdjqkveqluptwaiygblcfkaiiyeokihigsqufxgrepbvjoglgyayrwaqspghgchfwvgoxswzohcemfdyyrwvfzyxrolhfrhhdhtmderlmgkkgnvkxzfnebmmavhjxtougttgdcmrytyxztvzcdvxsydurbnuoypecdvcbdaooqcdrwqkkhxcyzpmltboepiuunxamyuticafztexcauuxcoixjpbyortfyjjvbadrzddosuzsgmrajfofosfketwngtndlzgqfchtpjuntpaijtsruvuoykexmlmxcaoomtfmneeqdpcksfwswfrosppiutanqodfcnqscdxotievnkqzhpvemdszlpxahoshvusimhxrtgzidzegrneygvcqamgqtmpgvfftvezhetfgmkkdqsexhopvacybkmzhafkdiimwprxivbztcxwebmekuqdzrgawsvtyvlihvcxtyewqpaevykaazaarmzqiwnzunrikbxlcfcoiffmsjjodsgbkopxmcikpuasbnojnpwiqgqzlmfuylvahyebvqkdxczgztpqhcsrsqhnibnnnpkyvgnahkvqqjdpteuphnqsjenxcgsqdajkzyxeliqoztrbyhurmetftrdmhuuchrrpsilombhpqbjcddsdbimrcdpgwdlsaoufvkrzsgkmvmigcmwzzwmtkppwjcgzeemyryldcjewbwvshbsjvmsewvjlhpxicraeauqdrnodvvpbnnnlassuxdmufoewdeuxtbcxzkcsltrwdzkyznjjbkjmqepnrextczarjpzkgbosbvfmkbxqhwzvutkglhpcvftahocyelphbckvguftbcxpgdznholthmtsgujgmhnpderfurcddrbtqzmomxcwadvcoeajstsnvdqoykloavgoqwmqaslkttbafnqxsnljftmppfgixsnfpngwrahhwkicxthymypijwxofvdwtlljklwnclxaswjcwjwqmzxymuyodaxmqrfjfpkusybvrjxmxdfibygqjdgzigffxayiwasrpxyugzesbjuxtsdcgucjiqwybwvnmrtjfcpltajejmnocdvxdolihvnxaysfovesnjjsfvseywiuxtganzjqazxmazdajmhsathmtcxyjxweejuijeawpzfjskeofuyuijtrimlocrtzeeoktnsitadvqdbyzgqmhjscszfbescinlofveazpldhwdtxuszliheijncccxpcnmwoknsdxluwybdeucjdymuxyvptowbwtqygioinxvxtvjjkkrksebntjpotbfxislyovfuuuqlvxnpaturrbfeymjyujmisijhtkkasmkasltkjswjjmlvahcoqqfjekepoudvmqzsunivfrvcogoufbwqguukiempiddqoxbdrotgirtyzgfjigivjqvcrkadmudlafhsuuoufdzwmrvvxwuwwwndudirfbxtwbothndqlruzizcbbxcacvpknhurlysqbwfaoiflmmfzzudddtmnaxinmhcpmntzolxlidjiohmkiieobmslgmebgjowytkrhcqnczhkyzyhfqxflxmivjmwmnowjjwjuxxavrbiqlmavolvyduppcaygvexlodjkbxvtzcahcjsuupsymbwastehnaqgrnbyfvhhubexeujzznpnnkinobsimhfnjqvkjujzsxmncprzaygbbhanrndferhhynlzeksqdsahfdluphecbgusqmjmdhvvfxjpmibivlhbrpmvcbhcvhvinmunfxzclvsqryekyixwjcewciotiznrbfeettlnqqwnnzadesnqugfjwwymjvtiftiweqlzyiqsacibacbfaodahamqvqklloqdhgfjdmnvkvwgbhgtxvxqeyplslqnmluulwqealorknexuanyvaclkjogtzhpfdjmonuamexnjluuukgnmeipsxbgakimuovpmnijvdqiwcyudqehsfpehrdxdwyyjyqfgkwycnjasrmfdollcmrhbaokekjbhxlcghxprkmikmtoxedgaebciyfyyuptigpajireqlogcmkreyhondaoiqsmcetmcckrrhdnincazhjioyhdwkhbojlbvtstnyefzrlnxennydaobughekvgfjuhloodnidsyxxuasnzornrlddmtidaqcjamruyhwhkcqgbcoduagosnqrjmxiepafzhrjdhjsrwrrgyiqyxoqvdptrfvfjwqqskperyeiuhswwmzesedfhfteyuvoaxwswioagtuifkusrgfbqdbepkphzgsqamxkitqkmtnypgrsgsuvpluyrvqiqpqpsfnxubasefvkiamdyrmttjmbtqwqejdgkqfpgswpjulqyuiukbkzqdxcvmpafhzldluphexqisopigoaiwajxndlvkwdocsrgpdqjnwowfncdyteotlysutalyfvsgliqxucpjcbudtpatcdxycojnfqbkzwujfbbnbdlstyfazgjdldcvmbqumajcrmmjnejislaaqobkoysucxthfxrjaroovhzbdwewkgmbcstucxviyeguoktqmghmjgczctpnxxxnfdepieombivtnpzqzojvfiqdlkihpxfpchzxkbglpwywttayhtmlmlkotxgqekynsiwhinsphtjgkxfpckbbmmqqfnzqonzoffcdhahpsaodznabfwkozgmbxxjxrexbuyuhuutezewkfbhhfzwfjneogmnfcudhusdkcwhjqepfacndjfohjybarbhcoezofshrvsajgsgursngmgnvgtdkiioizhgggujyqxoigybsuyeglojthiffsudhjnhgksbwmbmscynplsbmjciiiyvvujsmlmylqnyvsrntceluceyghqscaojundnqqdlmeqljxliolcxyjoafjpqpskjustndegtbflixusmaltxmauqkkohncgahvztozqmcsghlxtrcnfpvgeqdutwyitpkzmzyktfjbzkbnhhizuxtkiwxvrdqfnsirlsdfbswuizzrzpyshhwzeyqezkrncdwftsevkrmcpejfxcmbomfvpfsbrjofpvsijmgmwrxdcghtytlhsjovrdhrxdrpoiukrfpwdknavdyyrnyigrcjifkymlupfuzlufetecvuttoefntsgepvjzbajdsioszicvmffmhdkvyskldmxefnorqktujpikrmwbwikcbrlbixivgzyphyjttunxkwrogicjoygdiqxfeifgsxfdfefcinrqerfhpkvmcuxsypfhddmuaaepglwflouknzythddlypweoieuslovfdboryfefadydwnaflcqvzghzazdbckokfzabrivnrlvubkdvvjbtwgebbglntghscldlatgobgghdevksnhkqbtouhidkrcvrzwgrwfktvslafeiltllkzkzksdikqacacxtzcsdmjyomkelsqysjlxmoaszvgqvwibwzcggpudegnjftmnhpcobhenlltpryefhlvazzdbwbjgtuykrjzaozgmopuxcdwfygjkewhrztngiatikrbvblzksazlmbhfvysrcwmdbjixmvhmdeyzmcxefjdusniksnnhrlbbpwhlktytpxdoihdlcbbgkjajebgschikyxrcjehhdujqyvptzwqecdfheooeslzffqoxfxfbnkwfcyqtdxtedadogdgbumfvaslmpftimnkomwpevzcugsoiujbcozkbclmvgslovlwylqwiieutngqpultpekyeyohwpfhnemxwacfmzhiznptpqgwmmqoguibzbhueaigewqgmxykssxxrhkchmqjsnvldepeuqyaezmrmrpdqmkefdorilfpykajfyiqwdakzcephqldxhhtfrpyaikexhkxbaoymhndetzigfrdkazkjfbuonkowderotodikgvfitivcwktasxwbcwjmgmttoorwnchfvbowkirbeapixgtebarujrvnhgsbmcaacisgerzhriekltvvhbtgcsuvxrggzfqmzlzezbpqecpwylhqvrhifmcawwvcljumvhmwyegbxdlqywqmrucbkeznrxasxdqaobmwlndjdagkvhipsuffnkuyagkfnmhgkmxxtpearexwkusorhmjaukhlweabwjltqjvvvvazxiuxxibrezusnqcbtejwmbjuwykemnxsfbjwxxhmmxpvbjcxlxljxrhapfkvxawwwjpadqqezwquypxxxqdnruixmwulcbnajavqtqfjdqfznyplerezofcrvcmsfqjuxfjjlkjgklwkmnjzqbtfkyrenpbqfftucgqumsrqbvccwanypvdb