fork download
copy 
  1. #include <algorithm>
  2. #include <memory>
  3.  
  4. template <typename T>
  5. class linked_list
  6. {
  7.     struct node;
  8.  
  9. 	template <typename Node>
  10. 	class node_iterator;
  11.  
  12. 	typedef std::unique_ptr<node> node_ptr;
  13.  
  14. public:
  15. 	typedef T value_type;
  16. 	typedef std::size_t size_type;
  17. 	typedef std::ptrdiff_t difference_type;
  18. 	typedef T& reference;
  19. 	typedef const T& const_reference;
  20. 	typedef node_iterator<node> iterator;
  21. 	typedef node_iterator<const node> const_iterator;
  22.  
  23. private:
  24. 	struct node
  25. 	{
  26. 		node_ptr next;
  27. 		value_type value;
  28.  
  29. 		template <typename U>
  30. 		node(node_ptr&& next, U&& value)
  31. 			: next(std::move(next))
  32. 			, value(std::forward<U>(value))
  33. 		{}
  34. 	};
  35.  
  36. 	template <typename Node>
  37. 	class node_iterator
  38. 	{
  39. 	public:
  40. 		typedef T value_type;
  41. 		typedef std::ptrdiff_t difference_type;
  42. 		typedef T* pointer;
  43. 		typedef T& reference;
  44. 		typedef std::forward_iterator_tag iterator_category;
  45.  
  46. 	private:
  47. 		friend class linked_list;
  48. 		typedef node_iterator<const Node> const_iterator_type;
  49. 		Node* this_;
  50.  
  51. 	public:
  52. 		node_iterator(Node* this_)
  53. 			: this_(this_)
  54. 		{}
  55.  
  56. 		operator const_iterator_type () const
  57. 		{
  58. 			return this_;
  59. 		}
  60.  
  61. 		bool operator == (const node_iterator& rhs) const
  62. 		{
  63. 			return this_ == rhs.this_;
  64. 		}
  65.  
  66. 		bool operator != (const node_iterator& rhs) const
  67. 		{
  68. 			return !(*this == rhs);
  69. 		}
  70.  
  71. 		const node_iterator& operator ++ ()
  72. 		{
  73. 			this_ = this_->next.get();
  74. 			return *this;
  75. 		}
  76.  
  77. 		node_iterator operator ++ (int)
  78. 		{
  79. 			auto r = *this;
  80. 			this_ = this_->next.get();
  81. 			return r;
  82. 		}
  83.  
  84. 		auto operator * () -> decltype(this_->value)&
  85. 		{
  86. 			return this_->value;
  87. 		}
  88.  
  89. 		auto operator -> () -> decltype(this_->value)*
  90. 		{
  91. 			return &this_->value;
  92. 		}
  93. 	};
  94.  
  95. 	node_ptr front_;
  96.  
  97. public:
  98. 	template <typename U>
  99. 	void push_front(U&& value)
  100. 	{
  101. 		front_ = node_ptr(new node(std::move(front_), std::forward<U>(value)));
  102. 	}
  103.  
  104. 	void pop_front()
  105. 	{
  106. 		front_ = std::move(front_->next);
  107. 	}
  108.  
  109. 	iterator insert_after(const_iterator pos, const value_type& value)
  110. 	{
  111. 		auto& next = const_cast<node_ptr&>(pos.this_->next);
  112. 		next = node_ptr(new node(std::move(next), value));
  113. 		return pos.this_->next.get();
  114. 	}
  115.  
  116. 	iterator erase_after(const_iterator position)
  117. 	{
  118. 		const_cast<node_ptr&>(position.this_->next) = std::move(position.this_->next->next);
  119. 		return position.this_->next.get();
  120. 	}
  121.  
  122. 	iterator begin()
  123. 	{
  124. 		return front_.get();
  125. 	}
  126.  
  127. 	const_iterator begin() const
  128. 	{
  129. 		return front_.get();
  130. 	}
  131.  
  132. 	iterator end()
  133. 	{
  134. 		return nullptr;
  135. 	}
  136.  
  137. 	const_iterator end() const
  138. 	{
  139. 		return nullptr;
  140. 	}
  141. };
  142.  
  143. #include <iostream>
  144. #include <iterator>
  145.  
  146. int main()
  147. {
  148. 	typedef linked_list<char> llist;
  149.  
  150.   srand(0);
  151.   llist l;
  152.   llist::iterator it = l.begin();
  153.  
  154.   for (int i = 10000000; --i;) {
  155.     if (it != l.end()) {
  156.       if (rand()%2) {
  157.         it = l.insert_after(it, 'a' + (unsigned char)rand() %26);
  158.       } else {
  159.         llist::iterator after = it; ++after;
  160.         if (after == l.end()) goto add_front;
  161.         it = l.erase_after(it);
  162.       }
  163.     } else {
  164.     add_front:
  165.       l.push_front('a' + (unsigned char)rand() %26);
  166.       it = l.begin();
  167.     }
  168.   }
  169.  
  170.   std::ios_base::sync_with_stdio(false);
  171.   std::copy(l.begin(), l.end(), std::ostream_iterator<char>(std::cout, ""));
  172. }
Success #stdin #stdout 0.76s 3156KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
yxpkbooaaxeezylmxganlmcfbtdrqfnynkfsyijzfqcukaursqdmhkldxttktzdktfwvlsldzpheohhmiydfpzdrklomkbwkthvzeyrbjfjscqudeiolqlanjnunpnqjrqaunukhrxtkkzzgtrnaiwreetbfnpeycduvljkhidpqkkmnjuczuscrhbqqvnmarxglskmdzujmlijocjtfcroyxsyqunmdfqjcwjsdazwthtkxwmaflmczsocoxhmyhjajckrdxiqgzlbtvamnubfgoxmudctqgapkgpehthabwjdjevupdcpdshzajdgumyoinfkgkacteaqnpilrmpfukvqwegpnpxizwyuvlmjyjlaokocdrkdxldgwhpnrfzdzhxbyjqmmupcgusckyhtiazoptgfzogpfgouekivunoyziswqgeypofxsffrqjzuipqubousvryyafrxwjhnbevsxurzmzjzgiwhboecsvhznbfzuwxrjidxtlnwudaduosuzvveofjtoncuhhaiwkuzocqxufjwynsvldqfpztutzpcrwhwbvwsibjcmfarfnopqawhocjazrkqsgbjqryxojliwybmnktpqhnjqpobyrnuxhgzccoubvpdcdtkcstfhgfybptgjhgvmduuqnlamxkfotbpqiqwwatpdpmihjjaknenczbuspijuphnqwhjvrrqaqygbfqxlrizkfhejokugyinhfyuwwgnvnebwhiulajoeihdnzwvfsttcdwrbopneaaftyiliabiisqdnxnyyfqoqcxkdhklsqgwdonazwppqnzuiacdsjaxbqqszwmcbsuwlgtjojycmvxxfqpfrrjrzbokdnqiccrekgsnepbnrfqodtcgbfcleplvefflhylclejhrastdcpztuffehsmdsovqwwcsgiiuxdflheipdsgntewrcnmumqryoppuusigshoawuvicjyupndcywrwupbchxfitaaakagaovqfysoyvnekfgllczmmlaehqudiypanhkjdoxvqndwjapjkgogpvrotkrnilwlhjfrauczmygjrsxovogvjseencuxeoyytsfruocoofdxtjgcgroaovwyosjwjzrdoddcwxyuqpbuvetsrsmkbfjiyvziojmxjjmpccpcvselhxoosdixkopahlguzclfzmyulirqmblkhyvebrttppaqqehzxobsrkbzvvebuafvedkuskbblgktzfogtuhfdpmjuxeevpezficxzxufhxmhqptuhyisrvyvcxdzpihthxnijelmijtuvcvsclyckgvyzruqhhqsppdpbopzvrglczovlscijucvgoutvsphlgmmlgrjgxwqsygnuxqoqspsfibnvkmrbtzlfgcxblrpacsjttecuydmwvudvcwhwxxlztlkkrepkjbbgijeipupzzvjbglmfqtivjkqxnvcuoqzriadcsqkqvsvqcwfrcsymrrothwusrzmvjpcehgiwlnkmqlpmmhpaclrghcyaywnkstbmxmladcatvxwxhwgjrbioyjoslamxeroflnmpxyflitcayfmiitaawfihukeyglfgjujtyqumsywdeabqmzlrydimhjefkoicoxinddbwcwkverqteobzitkqlskvqjnwmkhmkkypnzznmbbumtedaciesicadugzndkrlvtmdmmvqjwsujpomgzldmufjrkiewjukecwlegntvslvwjpupqdahpfolcqzcnnygrnhyrfjrfbhploeeolqjhppptzoqdjqkveqluptwaiygblcfkaiiyeokihigsqufxgrepbvjoglgyayrwaqspghgchfwvgoxswzohcemfdyyrwvfzyxrolhfrhhdhtmderlmgkkgnvkxzfnebmmavhjxtougttgdcmrytyxztvzcdvxsydurbnuoypecdvcbdaooqcdrwqkkhxcyzpmltboepiuunxamyuticafztexcauuxcoixjpbyortfyjjvbadrzddosuzsgmrajfofosfketwngtndlzgqfchtpjuntpaijtsruvuoykexmlmxcaoomtfmneeqdpcksfwswfrosppiutanqodfcnqscdxotievnkqzhpvemdszlpxahoshvusimhxrtgzidzegrneygvcqamgqtmpgvfftvezhetfgmkkdqsexhopvacybkmzhafkdiimwprxivbztcxwebmekuqdzrgawsvtyvlihvcxtyewqpaevykaazaarmzqiwnzunrikbxlcfcoiffmsjjodsgbkopxmcikpuasbnojnpwiqgqzlmfuylvahyebvqkdxczgztpqhcsrsqhnibnnnpkyvgnahkvqqjdpteuphnqsjenxcgsqdajkzyxeliqoztrbyhurmetftrdmhuuchrrpsilombhpqbjcddsdbimrcdpgwdlsaoufvkrzsgkmvmigcmwzzwmtkppwjcgzeemyryldcjewbwvshbsjvmsewvjlhpxicraeauqdrnodvvpbnnnlassuxdmufoewdeuxtbcxzkcsltrwdzkyznjjbkjmqepnrextczarjpzkgbosbvfmkbxqhwzvutkglhpcvftahocyelphbckvguftbcxpgdznholthmtsgujgmhnpderfurcddrbtqzmomxcwadvcoeajstsnvdqoykloavgoqwmqaslkttbafnqxsnljftmppfgixsnfpngwrahhwkicxthymypijwxofvdwtlljklwnclxaswjcwjwqmzxymuyodaxmqrfjfpkusybvrjxmxdfibygqjdgzigffxayiwasrpxyugzesbjuxtsdcgucjiqwybwvnmrtjfcpltajejmnocdvxdolihvnxaysfovesnjjsfvseywiuxtganzjqazxmazdajmhsathmtcxyjxweejuijeawpzfjskeofuyuijtrimlocrtzeeoktnsitadvqdbyzgqmhjscszfbescinlofveazpldhwdtxuszliheijncccxpcnmwoknsdxluwybdeucjdymuxyvptowbwtqygioinxvxtvjjkkrksebntjpotbfxislyovfuuuqlvxnpaturrbfeymjyujmisijhtkkasmkasltkjswjjmlvahcoqqfjekepoudvmqzsunivfrvcogoufbwqguukiempiddqoxbdrotgirtyzgfjigivjqvcrkadmudlafhsuuoufdzwmrvvxwuwwwndudirfbxtwbothndqlruzizcbbxcacvpknhurlysqbwfaoiflmmfzzudddtmnaxinmhcpmntzolxlidjiohmkiieobmslgmebgjowytkrhcqnczhkyzyhfqxflxmivjmwmnowjjwjuxxavrbiqlmavolvyduppcaygvexlodjkbxvtzcahcjsuupsymbwastehnaqgrnbyfvhhubexeujzznpnnkinobsimhfnjqvkjujzsxmncprzaygbbhanrndferhhynlzeksqdsahfdluphecbgusqmjmdhvvfxjpmibivlhbrpmvcbhcvhvinmunfxzclvsqryekyixwjcewciotiznrbfeettlnqqwnnzadesnqugfjwwymjvtiftiweqlzyiqsacibacbfaodahamqvqklloqdhgfjdmnvkvwgbhgtxvxqeyplslqnmluulwqealorknexuanyvaclkjogtzhpfdjmonuamexnjluuukgnmeipsxbgakimuovpmnijvdqiwcyudqehsfpehrdxdwyyjyqfgkwycnjasrmfdollcmrhbaokekjbhxlcghxprkmikmtoxedgaebciyfyyuptigpajireqlogcmkreyhondaoiqsmcetmcckrrhdnincazhjioyhdwkhbojlbvtstnyefzrlnxennydaobughekvgfjuhloodnidsyxxuasnzornrlddmtidaqcjamruyhwhkcqgbcoduagosnqrjmxiepafzhrjdhjsrwrrgyiqyxoqvdptrfvfjwqqskperyeiuhswwmzesedfhfteyuvoaxwswioagtuifkusrgfbqdbepkphzgsqamxkitqkmtnypgrsgsuvpluyrvqiqpqpsfnxubasefvkiamdyrmttjmbtqwqejdgkqfpgswpjulqyuiukbkzqdxcvmpafhzldluphexqisopigoaiwajxndlvkwdocsrgpdqjnwowfncdyteotlysutalyfvsgliqxucpjcbudtpatcdxycojnfqbkzwujfbbnbdlstyfazgjdldcvmbqumajcrmmjnejislaaqobkoysucxthfxrjaroovhzbdwewkgmbcstucxviyeguoktqmghmjgczctpnxxxnfdepieombivtnpzqzojvfiqdlkihpxfpchzxkbglpwywttayhtmlmlkotxgqekynsiwhinsphtjgkxfpckbbmmqqfnzqonzoffcdhahpsaodznabfwkozgmbxxjxrexbuyuhuutezewkfbhhfzwfjneogmnfcudhusdkcwhjqepfacndjfohjybarbhcoezofshrvsajgsgursngmgnvgtdkiioizhgggujyqxoigybsuyeglojthiffsudhjnhgksbwmbmscynplsbmjciiiyvvujsmlmylqnyvsrntceluceyghqscaojundnqqdlmeqljxliolcxyjoafjpqpskjustndegtbflixusmaltxmauqkkohncgahvztozqmcsghlxtrcnfpvgeqdutwyitpkzmzyktfjbzkbnhhizuxtkiwxvrdqfnsirlsdfbswuizzrzpyshhwzeyqezkrncdwftsevkrmcpejfxcmbomfvpfsbrjofpvsijmgmwrxdcghtytlhsjovrdhrxdrpoiukrfpwdknavdyyrnyigrcjifkymlupfuzlufetecvuttoefntsgepvjzbajdsioszicvmffmhdkvyskldmxefnorqktujpikrmwbwikcbrlbixivgzyphyjttunxkwrogicjoygdiqxfeifgsxfdfefcinrqerfhpkvmcuxsypfhddmuaaepglwflouknzythddlypweoieuslovfdboryfefadydwnaflcqvzghzazdbckokfzabrivnrlvubkdvvjbtwgebbglntghscldlatgobgghdevksnhkqbtouhidkrcvrzwgrwfktvslafeiltllkzkzksdikqacacxtzcsdmjyomkelsqysjlxmoaszvgqvwibwzcggpudegnjftmnhpcobhenlltpryefhlvazzdbwbjgtuykrjzaozgmopuxcdwfygjkewhrztngiatikrbvblzksazlmbhfvysrcwmdbjixmvhmdeyzmcxefjdusniksnnhrlbbpwhlktytpxdoihdlcbbgkjajebgschikyxrcjehhdujqyvptzwqecdfheooeslzffqoxfxfbnkwfcyqtdxtedadogdgbumfvaslmpftimnkomwpevzcugsoiujbcozkbclmvgslovlwylqwiieutngqpultpekyeyohwpfhnemxwacfmzhiznptpqgwmmqoguibzbhueaigewqgmxykssxxrhkchmqjsnvldepeuqyaezmrmrpdqmkefdorilfpykajfyiqwdakzcephqldxhhtfrpyaikexhkxbaoymhndetzigfrdkazkjfbuonkowderotodikgvfitivcwktasxwbcwjmgmttoorwnchfvbowkirbeapixgtebarujrvnhgsbmcaacisgerzhriekltvvhbtgcsuvxrggzfqmzlzezbpqecpwylhqvrhifmcawwvcljumvhmwyegbxdlqywqmrucbkeznrxasxdqaobmwlndjdagkvhipsuffnkuyagkfnmhgkmxxtpearexwkusorhmjaukhlweabwjltqjvvvvazxiuxxibrezusnqcbtejwmbjuwykemnxsfbjwxxhmmxpvbjcxlxljxrhapfkvxawwwjpadqqezwquypxxxqdnruixmwulcbnajavqtqfjdqfznyplerezofcrvcmsfqjuxfjjlkjgklwkmnjzqbtfkyrenpbqfftucgqumsrqbvccwanypvdb
https://ideone.com/hQgd90
language:
C++14 (gcc 8.3)
created:
11 years ago
visibility:
secret

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!