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