Back to course 'CS102: Introduction to Computer Science II'

Topic outline

  • Unit 3: C++ Standard Template Library

    Collapse all Expand all

    Nearly every C++ programmer uses the C++ Standard Template Library (STL), a powerful and highly useful library of generic-typed data structures and algorithms. In this unit, we will learn how and why the STL was originally developed. The unit will also introduce you to the history and basics of templates and generic programming before presenting the structures (Containers, Iterators, and Functors) and algorithms that the Standard Template Library contains. By the end of this unit, you will be familiar with the STL, its uses, and its structures and algorithms.

    Completing this unit should take you approximately 7 hours.

    • Upon successful completion of this unit, you will be able to:

      • describe the basic components used in the C++ Standard Template Library;
      • demonstrate the various components within the C++ Standard Template Library; and
      • solve simple problems using C++ template programming.

    • 3.1: History and Motivation

      • page icon
        History of the Standard Template Library Page
        Students must
        Mark as done

        Read this page to gain insight into the history of C++' Standard Template Library. You will see that it did not suddenly appear on the scene. Also, its ideas have been incorporated into other languages. In particular, its support of data-generic programming is important to the construction and flexibility of modern systems.

    • 3.2: Main Design Ideas

      • page icon
        Standard Template Library Background Page
        Students must
        Mark as done

        Paraphrasing the introduction, this video introduces STL, a formal part of the modern C++ language standard. The speaker demonstrates many STL core features (iterators, algorithms, and data structures). He elaborates on technical details in very substantive way. STL, is a C++ library of classes, algorithms, and iterators, while providing many fundamental algorithms, data structures, and templates.

      • page icon
        STL and its Design Principles Page
        Students must
        Mark as done

    • 3.3: The Elements of C++ STL

      Software engineering implements general computation using four fundamental steps: requirements, design, code, and validation. In process terms, this becomes defining a problem or task, designing a solution, coding the solution, and testing the solution. C++ STL supports the transition from designing to coding. To exploit the similarity among problems and tasks, it is beneficial to reuse existing designs and code on new problems and tasks. The principle concepts of modularity, abstraction and composition support reusability. This article shows how programming languages implement these principles using data, expressions, functions, and control statements. Essentially C++ STL, and also Java Container Library, are a set of pre-tested trusted modules that implement standard data structures, containers, traversals, and data manipulations.

      • Students must
        Mark as done

        Study these slides for a good foundation discussion of generic programming concepts. The examples are in C++ but the principles apply also to Java.

        The objective of the programming process is a solution to a problem or to complete task. The programming process itself includes requirements development (understanding the problem), design (formulating a plan or strategy), implementation in a programming language (completing the plan by providing details from previous or known solutions), verification and validation (checking the solution). Given a specific problem (program), we can develop a specific solution (specific program); or, we could use abstraction to view the program generically, and develop a generic solution. Using generic functions and generic data structures, a generic design and generic implementation can be developed that will solve, not just a specific problem, but a general class of problems. That is the idea of generic programming; a form of reuse on a large scale, of requirements, design, and implementation.

        Libraries of Templates and Containers are an approach to generic programming. One approach to generic programming is a capability that allows functions that apply to more than one type of data (polymorphism). For example, a generic search should work for searching data of any type, as long as the data is comparable.

      • page icon
        Iterators in the C++ STL Page
        Students must
        Mark as done

        Read this chapter, which covers iterators for groups of classes in contiguous memory.

      • page icon
        More on the Standard Template Library Page
        Students must
        Mark as done

        Read this article, which further discusses the STL.

      • book icon
        Making and Using STL Objects Book
        Students must
        Mark as done

        Read Chapter 2 for an introduction to basic STL classes and their application.

      • url icon
        C++ Reference URL
        Students must
        Mark as done

        Use this reference to get at the nuts and bolts of C++ Standard Template Library.

      • page icon
        Function Objects Page
        Students must
        Mark as done

        A functor is a name for a function object, which is an object that is called like a function.

    • Unit 3 Assessment

      • quiz icon
        Unit 3 Assessment Quiz
        Students must
        Receive a grade

        Take this assessment to see how well you understood this unit.

        • This assessment does not count towards your grade. It is just for practice!
        • You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
        • You can take this assessment as many times as you want, whenever you want.