{"id":17003,"date":"2024-03-07T15:35:29","date_gmt":"2024-03-07T15:35:29","guid":{"rendered":"http:\/\/www.max-sperling.bplaced.net\/?p=17003"},"modified":"2025-05-05T08:22:20","modified_gmt":"2025-05-05T08:22:20","slug":"data-structures-time-complexity-libstdc","status":"publish","type":"post","link":"http:\/\/www.max-sperling.bplaced.net\/?p=17003","title":{"rendered":"Data structures &#8211; Time complexity (libstdc++)"},"content":{"rendered":"<p><strong>Cases<\/strong><\/p>\n<ul>\n<li>B &#8230; Best case<\/li>\n<li>A &#8230; Average case<\/li>\n<li>W &#8230; Worst case<\/li>\n<\/ul>\n<p>If there is nothing mentioned, it matches all cases.<\/p>\n<hr>\n<p><strong>1. Sequence containers<\/strong><\/p>\n<table>\n<tr>\n<th>Operation<\/th>\n<th>Array<\/th>\n<th>Vector<\/th>\n<th>Deque<\/th>\n<th>Forward_list<\/th>\n<th>List<\/th>\n<\/tr>\n<tr>\n<td>Access Head<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<\/tr>\n<tr>\n<td>Access Index<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<\/tr>\n<tr>\n<td>Access Tail<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightcoral\">\u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<\/tr>\n<tr>\n<td>Insert Head<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">\u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<\/tr>\n<tr>\n<td>Insert Index<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<\/tr>\n<tr>\n<td>Insert Tail<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightgreen\">B, A: \u0398(1)<br \/>W<sup>[1]<\/sup>: \u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightcoral\">\u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<\/tr>\n<tr>\n<td>Remove Head<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">\u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<\/tr>\n<tr>\n<td>Remove Index<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<\/tr>\n<tr>\n<td>Remove Tail<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightcoral\">\u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<\/tr>\n<tr>\n<td>Search by Value<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<\/tr>\n<\/table>\n<hr>\n<p><strong>2. Associative containers<\/strong><\/p>\n<table>\n<tr>\n<th>Operation<\/th>\n<th>Set<\/th>\n<th>Map<\/th>\n<th>Unordered_set<\/th>\n<th>Unordered_map<\/th>\n<\/tr>\n<tr>\n<td>Insert Key (+Val)<\/td>\n<td bgcolor=\"lightyellow\">\u0398(log(n))<\/td>\n<td bgcolor=\"lightyellow\">\u0398(log(n))<\/td>\n<td bgcolor=\"lightgreen\">B, A: \u0398(1)<br \/>W<sup>[2]<\/sup>: \u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">B, A: \u0398(1)<br \/>W<sup>[2]<\/sup>: \u0398(n)<\/td>\n<\/tr>\n<tr>\n<td>Search by Key<\/td>\n<td bgcolor=\"lightyellow\">B: \u0398(1)<br \/>A, W: \u0398(log(n))<\/td>\n<td bgcolor=\"lightyellow\">B: \u0398(1)<br \/>A, W: \u0398(log(n))<\/td>\n<td bgcolor=\"lightgreen\">B, A: \u0398(1)<br \/>W<sup>[\u03b1]<\/sup>: \u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">B, A: \u0398(1)<br \/>W<sup>[\u03b1]<\/sup>: \u0398(n)<\/td>\n<\/tr>\n<tr>\n<td>Search by Value<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<\/tr>\n<tr>\n<td>Remove by Key<\/td>\n<td bgcolor=\"lightyellow\">\u0398(log(n))<\/td>\n<td bgcolor=\"lightyellow\">\u0398(log(n))<\/td>\n<td bgcolor=\"lightgreen\">B, A: \u0398(1)<br \/>W<sup>[\u03b1]<\/sup>: \u0398(n)<\/td>\n<td bgcolor=\"lightgreen\">B, A: \u0398(1)<br \/>W<sup>[\u03b1]<\/sup>: \u0398(n)<\/td>\n<\/tr>\n<tr>\n<td>Remove by Value<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">B: \u0398(1)<br \/>A, W: \u0398(n)<\/td>\n<\/tr>\n<\/table>\n<p><sup>[\u03b1]<\/sup> &#8230; All items are in one bucket.<\/p>\n<hr>\n<p><strong>3. Container adaptors<\/strong><\/p>\n<table>\n<tr>\n<th>Operation<\/th>\n<th>Stack<sup>[\u03b11]<\/sup><\/th>\n<th>Queue<sup>[\u03b11]<\/sup><\/th>\n<th>Priority_queue<sup>[\u03b12]<\/sup><\/th>\n<\/tr>\n<tr>\n<td>Access Head<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td>Access Tail<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<\/tr>\n<tr>\n<td>Insert Head<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td>Insert Tail<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td>Insert Value<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightgreen\">B, A<sup>[\u03b2]<\/sup>: \u0398(1)<br \/>W<sup>[1]<\/sup>: \u0398(n)<\/td>\n<\/tr>\n<tr>\n<td>Remove Head<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightgreen\">\u0398(1)<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<\/tr>\n<tr>\n<td>Remove Tail<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightcoral\">&#8211;<\/td>\n<td bgcolor=\"lightyellow\">B<sup>[\u03b3]<\/sup>: \u0398(1)<br \/>A, W: \u0398(log(n))<\/td>\n<\/tr>\n<\/table>\n<p><sup>[\u03b11]<\/sup> &#8230; Container underneath is std::deque (default).<br \/>\n<sup>[\u03b12]<\/sup> &#8230; Container underneath is std::vector (default).<br \/>\n<sup>[\u03b2]<\/sup> &#8230; &#8220;<a href=\"https:\/\/webdocs.cs.ualberta.ca\/~hayward\/papers\/heap.pdf\">Average Case Analysis of Heap Building by Repeated Insertion<\/a>&#8221; (by Hayward &#038; McDiarmid)<br \/>\n<sup>[\u03b3]<\/sup> &#8230; All nodes have the same value.<\/p>\n<hr>\n<p><strong>Notes<\/strong><\/p>\n<p><sup>[1]<\/sup> &#8230; Insert element triggers a relocation.<br \/>\n<sup>[2]<\/sup> &#8230; Insert element triggers a rehashing.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Cases B &#8230; Best case A &#8230; Average case W &#8230; Worst case If there is nothing mentioned, it matches<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false},"categories":[81,80],"tags":[],"_links":{"self":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17003"}],"collection":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=17003"}],"version-history":[{"count":54,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17003\/revisions"}],"predecessor-version":[{"id":17115,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=\/wp\/v2\/posts\/17003\/revisions\/17115"}],"wp:attachment":[{"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=17003"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=17003"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.max-sperling.bplaced.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=17003"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}