# Video Introduction to the STL, Parts 6 and 7

### Video Introduction to the STL, Parts 6 and 7

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, 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:

 Puzzle Time (v1.1) Time (v1.7) Speedup wikipedia_hard 87.1 ms 5.9 ms 14.8x wikipedia_easy 36.1 ms 3.2 ms 11.4x nikoli_1 18.5 ms 1.6 ms 11.9x nikoli_2 13.2 ms 1.9 ms 7.1x nikoli_3 16.8 ms 2.2 ms 7.8x nikoli_4 108.1 ms 5.9 ms 18.3x nikoli_5 89.7 ms 7.3 ms 12.3x nikoli_6 87.5 ms 5.7 ms 15.3x nikoli_7 2123.97 seconds 496.0 ms 4282.3x nikoli_8 2784.7 ms 316.7 ms 8.8x nikoli_9 13518.2 seconds 32.8 seconds 412.4x nikoli_10 11811.8 seconds 8.5 seconds 1397.5x

Here's the changelog:

1.0 (8/24/2010) - First version, appearing in Channel 9's Video Introduction to the STL, Part 4.

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.

1.2 (9/1/2010) - Massively accelerated hypothetical contradiction analysis by guessing cells in a deterministic but pseudorandomized order.

1.3 (9/8/2010) - Reorganized Grid::solve() into smaller member functions. Thanks, Corrector2!

1.4 (9/24/2010) - Accelerated hypothetical contradiction analysis further by prioritizing guesses near white cells. Thanks, Michael B.!

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().

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 output of hypothetical contradiction analysis, copying the output of top-level analysis is pointless.

1.7 (10/20/2010) - Significantly accelerated Grid::confined() by using a linear vector<Flag>.

Take a look at the source code to see what's changed!

Stephan T. Lavavej

Visual C++ Libraries Developer

• pls tell me what Visual C++ is. I show 4 different years on my computer????????????  Ruth Amore

Page 1 of 1 (1 items)