fork download
copy 
  1. #include <algorithm>
  2. #include <memory>
  3.  
  4. struct slist_node_base {
  5.   slist_node_base(slist_node_base *next) : next(next) {}
  6.   slist_node_base *next;
  7. };
  8.  
  9. template <typename T>
  10. class slist {
  11.   struct node : slist_node_base {
  12.     template <typename... Args>
  13.     node(slist_node_base *n, Args&&... args)
  14.       : slist_node_base(n), data(std::forward<Args>(args)...) {}
  15.     T data;
  16.   };
  17.   slist_node_base pointer_to_first;
  18.   slist_node_base* data() { return &pointer_to_first; }
  19.  
  20. public:
  21.   slist() : pointer_to_first(data()) {}
  22.  ~slist() {
  23.    for (iterator i = begin(); i!=end();) {
  24.      std::unique_ptr<node> tmp(i.as_node());
  25.      ++i;
  26.    }
  27.   }
  28.  
  29.   slist(slist const& o) =delete;
  30.   slist& operator=(slist const& o) =delete;
  31.  
  32.   class iterator {
  33.     friend class slist;
  34.     slist_node_base *n;
  35.     iterator (slist_node_base *n) : n(n) {}
  36.  
  37.     // UB wenn n == end()
  38.     node *as_node() { return static_cast<node*>(n); }
  39.  
  40.   public:
  41.     typedef std::ptrdiff_t               difference_type;
  42.     typedef std::forward_iterator_tag    iterator_category;
  43.     typedef T                            value_type;
  44.     typedef T*                           pointer;
  45.     typedef T&                           reference;
  46.  
  47.     iterator& operator++()    { n = n->next; return *this; }
  48.     iterator  operator++(int) { iterator tmp = this; n = n->next; return tmp; }
  49.  
  50.     bool operator==(const iterator& o) const { return n == o.n; }
  51.     bool operator!=(const iterator& o) const { return n != o.n; }
  52.  
  53.     T& operator* () { return  as_node()->data; }
  54.     T* operator->() { return &as_node()->data; }
  55.   };
  56.  
  57.   template <typename... Args>
  58.   iterator emplace_after(iterator i, Args&&... args)
  59.   {
  60.     node *n = new node(i.n->next, std::forward<Args>(args)...);
  61.     i.n->next = n;
  62.     return n;
  63.   }
  64.  
  65.   iterator erase_after(iterator i)
  66.   {
  67.     std::unique_ptr<node> to_be_deleted(static_cast<node*>(i.n->next));
  68.     slist_node_base *ret = to_be_deleted->next;
  69.     i.n->next = ret;
  70.     return ret;
  71.   }
  72.  
  73.   iterator insert_after(iterator i, T const& x) { return emplace_after(i, x); }
  74.   iterator insert_after(iterator i, T&& x)      { return emplace_after(i, std::move(x)); }
  75.  
  76.   iterator emplace_front(T const& x) { return emplace_after(end(), x); }
  77.   iterator push_front(T const& x) { return emplace_front(x); }
  78.   iterator push_front(T&&      x) { return emplace_front(std::move(x)); }
  79.  
  80.   void pop_front() { erase_after(data()); }  
  81.  
  82.   iterator begin() { return data()->next; }
  83.   iterator end()   { return data();       }
  84. };
  85.  
  86. #include <iostream>
  87. #include <iterator>
  88.  
  89. int main()
  90. {
  91.   srand(0);
  92.   slist<char> l;
  93.   slist<char>::iterator it = l.begin();
  94.  
  95.   for (int i = 10000000; --i;) {
  96.     if (it != l.end()) {
  97.       if (rand()%2) {
  98.         it = l.insert_after(it, 'a' + (unsigned char)rand() %26);
  99.       } else {
  100.         slist<char>::iterator after = it; ++after;
  101.         if (after == l.end()) goto add_front;
  102.         it = l.erase_after(it);
  103.       }
  104.     } else {
  105.     add_front:
  106.       l.push_front('a' + (unsigned char)rand() %26);
  107.       it = l.begin();
  108.     }
  109.   }
  110.  
  111.   std::ios_base::sync_with_stdio(false);
  112.   std::copy(l.begin(), l.end(), std::ostream_iterator<char>(std::cout, ""));
  113. }
  114.  
Success #stdin #stdout 0.76s 3156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
yxpkbooaaxeezylmxganlmcfbtdrqfnynkfsyijzfqcukaursqdmhkldxttktzdktfwvlsldzpheohhmiydfpzdrklomkbwkthvzeyrbjfjscqudeiolqlanjnunpnqjrqaunukhrxtkkzzgtrnaiwreetbfnpeycduvljkhidpqkkmnjuczuscrhbqqvnmarxglskmdzujmlijocjtfcroyxsyqunmdfqjcwjsdazwthtkxwmaflmczsocoxhmyhjajckrdxiqgzlbtvamnubfgoxmudctqgapkgpehthabwjdjevupdcpdshzajdgumyoinfkgkacteaqnpilrmpfukvqwegpnpxizwyuvlmjyjlaokocdrkdxldgwhpnrfzdzhxbyjqmmupcgusckyhtiazoptgfzogpfgouekivunoyziswqgeypofxsffrqjzuipqubousvryyafrxwjhnbevsxurzmzjzgiwhboecsvhznbfzuwxrjidxtlnwudaduosuzvveofjtoncuhhaiwkuzocqxufjwynsvldqfpztutzpcrwhwbvwsibjcmfarfnopqawhocjazrkqsgbjqryxojliwybmnktpqhnjqpobyrnuxhgzccoubvpdcdtkcstfhgfybptgjhgvmduuqnlamxkfotbpqiqwwatpdpmihjjaknenczbuspijuphnqwhjvrrqaqygbfqxlrizkfhejokugyinhfyuwwgnvnebwhiulajoeihdnzwvfsttcdwrbopneaaftyiliabiisqdnxnyyfqoqcxkdhklsqgwdonazwppqnzuiacdsjaxbqqszwmcbsuwlgtjojycmvxxfqpfrrjrzbokdnqiccrekgsnepbnrfqodtcgbfcleplvefflhylclejhrastdcpztuffehsmdsovqwwcsgiiuxdflheipdsgntewrcnmumqryoppuusigshoawuvicjyupndcywrwupbchxfitaaakagaovqfysoyvnekfgllczmmlaehqudiypanhkjdoxvqndwjapjkgogpvrotkrnilwlhjfrauczmygjrsxovogvjseencuxeoyytsfruocoofdxtjgcgroaovwyosjwjzrdoddcwxyuqpbuvetsrsmkbfjiyvziojmxjjmpccpcvselhxoosdixkopahlguzclfzmyulirqmblkhyvebrttppaqqehzxobsrkbzvvebuafvedkuskbblgktzfogtuhfdpmjuxeevpezficxzxufhxmhqptuhyisrvyvcxdzpihthxnijelmijtuvcvsclyckgvyzruqhhqsppdpbopzvrglczovlscijucvgoutvsphlgmmlgrjgxwqsygnuxqoqspsfibnvkmrbtzlfgcxblrpacsjttecuydmwvudvcwhwxxlztlkkrepkjbbgijeipupzzvjbglmfqtivjkqxnvcuoqzriadcsqkqvsvqcwfrcsymrrothwusrzmvjpcehgiwlnkmqlpmmhpaclrghcyaywnkstbmxmladcatvxwxhwgjrbioyjoslamxeroflnmpxyflitcayfmiitaawfihukeyglfgjujtyqumsywdeabqmzlrydimhjefkoicoxinddbwcwkverqteobzitkqlskvqjnwmkhmkkypnzznmbbumtedaciesicadugzndkrlvtmdmmvqjwsujpomgzldmufjrkiewjukecwlegntvslvwjpupqdahpfolcqzcnnygrnhyrfjrfbhploeeolqjhppptzoqdjqkveqluptwaiygblcfkaiiyeokihigsqufxgrepbvjoglgyayrwaqspghgchfwvgoxswzohcemfdyyrwvfzyxrolhfrhhdhtmderlmgkkgnvkxzfnebmmavhjxtougttgdcmrytyxztvzcdvxsydurbnuoypecdvcbdaooqcdrwqkkhxcyzpmltboepiuunxamyuticafztexcauuxcoixjpbyortfyjjvbadrzddosuzsgmrajfofosfketwngtndlzgqfchtpjuntpaijtsruvuoykexmlmxcaoomtfmneeqdpcksfwswfrosppiutanqodfcnqscdxotievnkqzhpvemdszlpxahoshvusimhxrtgzidzegrneygvcqamgqtmpgvfftvezhetfgmkkdqsexhopvacybkmzhafkdiimwprxivbztcxwebmekuqdzrgawsvtyvlihvcxtyewqpaevykaazaarmzqiwnzunrikbxlcfcoiffmsjjodsgbkopxmcikpuasbnojnpwiqgqzlmfuylvahyebvqkdxczgztpqhcsrsqhnibnnnpkyvgnahkvqqjdpteuphnqsjenxcgsqdajkzyxeliqoztrbyhurmetftrdmhuuchrrpsilombhpqbjcddsdbimrcdpgwdlsaoufvkrzsgkmvmigcmwzzwmtkppwjcgzeemyryldcjewbwvshbsjvmsewvjlhpxicraeauqdrnodvvpbnnnlassuxdmufoewdeuxtbcxzkcsltrwdzkyznjjbkjmqepnrextczarjpzkgbosbvfmkbxqhwzvutkglhpcvftahocyelphbckvguftbcxpgdznholthmtsgujgmhnpderfurcddrbtqzmomxcwadvcoeajstsnvdqoykloavgoqwmqaslkttbafnqxsnljftmppfgixsnfpngwrahhwkicxthymypijwxofvdwtlljklwnclxaswjcwjwqmzxymuyodaxmqrfjfpkusybvrjxmxdfibygqjdgzigffxayiwasrpxyugzesbjuxtsdcgucjiqwybwvnmrtjfcpltajejmnocdvxdolihvnxaysfovesnjjsfvseywiuxtganzjqazxmazdajmhsathmtcxyjxweejuijeawpzfjskeofuyuijtrimlocrtzeeoktnsitadvqdbyzgqmhjscszfbescinlofveazpldhwdtxuszliheijncccxpcnmwoknsdxluwybdeucjdymuxyvptowbwtqygioinxvxtvjjkkrksebntjpotbfxislyovfuuuqlvxnpaturrbfeymjyujmisijhtkkasmkasltkjswjjmlvahcoqqfjekepoudvmqzsunivfrvcogoufbwqguukiempiddqoxbdrotgirtyzgfjigivjqvcrkadmudlafhsuuoufdzwmrvvxwuwwwndudirfbxtwbothndqlruzizcbbxcacvpknhurlysqbwfaoiflmmfzzudddtmnaxinmhcpmntzolxlidjiohmkiieobmslgmebgjowytkrhcqnczhkyzyhfqxflxmivjmwmnowjjwjuxxavrbiqlmavolvyduppcaygvexlodjkbxvtzcahcjsuupsymbwastehnaqgrnbyfvhhubexeujzznpnnkinobsimhfnjqvkjujzsxmncprzaygbbhanrndferhhynlzeksqdsahfdluphecbgusqmjmdhvvfxjpmibivlhbrpmvcbhcvhvinmunfxzclvsqryekyixwjcewciotiznrbfeettlnqqwnnzadesnqugfjwwymjvtiftiweqlzyiqsacibacbfaodahamqvqklloqdhgfjdmnvkvwgbhgtxvxqeyplslqnmluulwqealorknexuanyvaclkjogtzhpfdjmonuamexnjluuukgnmeipsxbgakimuovpmnijvdqiwcyudqehsfpehrdxdwyyjyqfgkwycnjasrmfdollcmrhbaokekjbhxlcghxprkmikmtoxedgaebciyfyyuptigpajireqlogcmkreyhondaoiqsmcetmcckrrhdnincazhjioyhdwkhbojlbvtstnyefzrlnxennydaobughekvgfjuhloodnidsyxxuasnzornrlddmtidaqcjamruyhwhkcqgbcoduagosnqrjmxiepafzhrjdhjsrwrrgyiqyxoqvdptrfvfjwqqskperyeiuhswwmzesedfhfteyuvoaxwswioagtuifkusrgfbqdbepkphzgsqamxkitqkmtnypgrsgsuvpluyrvqiqpqpsfnxubasefvkiamdyrmttjmbtqwqejdgkqfpgswpjulqyuiukbkzqdxcvmpafhzldluphexqisopigoaiwajxndlvkwdocsrgpdqjnwowfncdyteotlysutalyfvsgliqxucpjcbudtpatcdxycojnfqbkzwujfbbnbdlstyfazgjdldcvmbqumajcrmmjnejislaaqobkoysucxthfxrjaroovhzbdwewkgmbcstucxviyeguoktqmghmjgczctpnxxxnfdepieombivtnpzqzojvfiqdlkihpxfpchzxkbglpwywttayhtmlmlkotxgqekynsiwhinsphtjgkxfpckbbmmqqfnzqonzoffcdhahpsaodznabfwkozgmbxxjxrexbuyuhuutezewkfbhhfzwfjneogmnfcudhusdkcwhjqepfacndjfohjybarbhcoezofshrvsajgsgursngmgnvgtdkiioizhgggujyqxoigybsuyeglojthiffsudhjnhgksbwmbmscynplsbmjciiiyvvujsmlmylqnyvsrntceluceyghqscaojundnqqdlmeqljxliolcxyjoafjpqpskjustndegtbflixusmaltxmauqkkohncgahvztozqmcsghlxtrcnfpvgeqdutwyitpkzmzyktfjbzkbnhhizuxtkiwxvrdqfnsirlsdfbswuizzrzpyshhwzeyqezkrncdwftsevkrmcpejfxcmbomfvpfsbrjofpvsijmgmwrxdcghtytlhsjovrdhrxdrpoiukrfpwdknavdyyrnyigrcjifkymlupfuzlufetecvuttoefntsgepvjzbajdsioszicvmffmhdkvyskldmxefnorqktujpikrmwbwikcbrlbixivgzyphyjttunxkwrogicjoygdiqxfeifgsxfdfefcinrqerfhpkvmcuxsypfhddmuaaepglwflouknzythddlypweoieuslovfdboryfefadydwnaflcqvzghzazdbckokfzabrivnrlvubkdvvjbtwgebbglntghscldlatgobgghdevksnhkqbtouhidkrcvrzwgrwfktvslafeiltllkzkzksdikqacacxtzcsdmjyomkelsqysjlxmoaszvgqvwibwzcggpudegnjftmnhpcobhenlltpryefhlvazzdbwbjgtuykrjzaozgmopuxcdwfygjkewhrztngiatikrbvblzksazlmbhfvysrcwmdbjixmvhmdeyzmcxefjdusniksnnhrlbbpwhlktytpxdoihdlcbbgkjajebgschikyxrcjehhdujqyvptzwqecdfheooeslzffqoxfxfbnkwfcyqtdxtedadogdgbumfvaslmpftimnkomwpevzcugsoiujbcozkbclmvgslovlwylqwiieutngqpultpekyeyohwpfhnemxwacfmzhiznptpqgwmmqoguibzbhueaigewqgmxykssxxrhkchmqjsnvldepeuqyaezmrmrpdqmkefdorilfpykajfyiqwdakzcephqldxhhtfrpyaikexhkxbaoymhndetzigfrdkazkjfbuonkowderotodikgvfitivcwktasxwbcwjmgmttoorwnchfvbowkirbeapixgtebarujrvnhgsbmcaacisgerzhriekltvvhbtgcsuvxrggzfqmzlzezbpqecpwylhqvrhifmcawwvcljumvhmwyegbxdlqywqmrucbkeznrxasxdqaobmwlndjdagkvhipsuffnkuyagkfnmhgkmxxtpearexwkusorhmjaukhlweabwjltqjvvvvazxiuxxibrezusnqcbtejwmbjuwykemnxsfbjwxxhmmxpvbjcxlxljxrhapfkvxawwwjpadqqezwquypxxxqdnruixmwulcbnajavqtqfjdqfznyplerezofcrvcmsfqjuxfjjlkjgklwkmnjzqbtfkyrenpbqfftucgqumsrqbvccwanypvdb
https://ideone.com/mHu6Ir
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!