{"id":3723,"date":"2010-10-25T15:20:49","date_gmt":"2010-10-25T15:20:49","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/vcblog\/2010\/10\/25\/video-introduction-to-the-stl-parts-6-and-7\/"},"modified":"2019-02-18T18:45:25","modified_gmt":"2019-02-18T18:45:25","slug":"video-introduction-to-the-stl-parts-6-and-7","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/cppblog\/video-introduction-to-the-stl-parts-6-and-7\/","title":{"rendered":"Video Introduction to the STL, Parts 6 and 7"},"content":{"rendered":"

\n

<\/p>\n

<\/span><\/p>\n

Part 6<\/a> and Part 7<\/a> of my video lecture series introducing the Standard Template Library are now available; they cover algorithms and functors.<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Previous parts: <\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Part 1<\/a> (sequence containers)<\/p>\n

<\/span><\/p>\n

Part 2<\/a> (associative containers)<\/p>\n

<\/span><\/p>\n

Part 3<\/a> (smart pointers)<\/p>\n

<\/span><\/p>\n

Part 4<\/a> (Nurikabe<\/a> solver introduction)<\/p>\n

<\/span><\/p>\n

Part 5<\/a> (Nurikabe solver conclusion)<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

My Nurikabe solver, available here<\/a>, demonstrates how I use the STL components that I’ve talked about.  I’ve continued to optimize it; there’s more work to do, but I’ve already obtained dramatic speedups:<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n
\n

Puzzle<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

Time (v1.1)<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

Time (v1.7)<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

Speedup<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n<\/tr>\n

\n

wikipedia_hard<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

87.1 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

5.9 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

14.8x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

wikipedia_easy<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

36.1 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

3.2 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

11.4x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_1<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

18.5 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

1.6 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

11.9x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_2<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

13.2 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

1.9 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

7.1x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_3<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

16.8 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

2.2 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

7.8x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_4<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

108.1 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

5.9 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

18.3x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_5<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

89.7 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

7.3 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

12.3x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_6<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

87.5 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

5.7 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

15.3x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_7<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

2123.97 seconds<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

496.0 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

4282.3x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_8<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

2784.7 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

316.7 ms<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

8.8x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_9<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

13518.2 seconds<\/span><\/p>\n

<\/span><\/p>\n<\/td>\n

\n

32.8 seconds<\/span><\/p>\n

<\/span><\/p>\n<\/td>\n

\n

412.4x<\/span><\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n

\n

nikoli_10<\/p>\n

<\/span><\/b><\/p>\n<\/td>\n

\n

11811.8 seconds<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

8.5 seconds<\/p>\n

<\/span><\/p>\n<\/td>\n

\n

1397.5x<\/p>\n

<\/span><\/p>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

Here’s the changelog:<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

1.0 (8\/24\/2010) – First version, appearing in Channel 9’s Video Introduction to the STL, Part 4.<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

1.1 (9\/1\/2010) – Added 1 more puzzle from Wikipedia and 10 puzzles from Nikoli. Improved time formatting with microseconds\/milliseconds\/seconds. The time taken by initial construction and each step of analysis is now recorded.<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

1.2 (9\/1\/2010) – Massively accelerated hypothetical contradiction analysis by guessing cells in a deterministic but pseudorandomized order.<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

1.3 (9\/8\/2010) – Reorganized Grid::solve() into smaller member functions. Thanks, Corrector2!<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

1.4 (9\/24\/2010) – Accelerated hypothetical contradiction analysis further by prioritizing guesses near white cells. Thanks, Michael B.!<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

1.5 (10\/19\/2010) – Increased performance by making Grid::confined() use vector<vector<Flag>> instead of set<pair<int, int>>. Further increased performance by postponing Grid::detect_contradictions() until just before Grid::analyze_confinement().<\/p>\n

<\/span><\/p>\n

<\/p>\n

 <\/p>\n

<\/span><\/p>\n

1.6 (10\/20\/2010) – Removed Grid::analyze_isolated_unknown_regions(), which was successful exactly once (on wikipedia_hard), during both top-level analysis and hypothetical contradiction analysis. Removed Grid::operator=()’s definition and entirely removed Grid::swap(), as they were unused. Avoided copying m_output in Grid’s private copy ctor, as it isn’t needed during hypothetical contradiction analysis. Even if, in the future, the solver is extended to capture the outp<\/span><\/p><\/p>\n","protected":false},"excerpt":{"rendered":"

Part 6 and Part 7 of my video lecture series introducing the Standard Template Library are now available; they cover algorithms and functors.   Previous parts:   Part 1 (sequence containers) Part 2 (associative containers) Part 3 (smart pointers) Part 4 (Nurikabe solver introduction) Part 5 (Nurikabe solver conclusion)   My Nurikabe solver, available here, […]<\/p>\n","protected":false},"author":289,"featured_media":35994,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[9,3,32],"class_list":["post-3723","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-cplusplus","tag-channel-9","tag-dev","tag-stl"],"acf":[],"blog_post_summary":"

Part 6 and Part 7 of my video lecture series introducing the Standard Template Library are now available; they cover algorithms and functors.   Previous parts:   Part 1 (sequence containers) Part 2 (associative containers) Part 3 (smart pointers) Part 4 (Nurikabe solver introduction) Part 5 (Nurikabe solver conclusion)   My Nurikabe solver, available here, […]<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/3723","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/users\/289"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/comments?post=3723"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/posts\/3723\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media\/35994"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/media?parent=3723"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/categories?post=3723"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/cppblog\/wp-json\/wp\/v2\/tags?post=3723"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}