book

C++ How to Program, 10/e

by Paul Deitel, Harvey Deitel

February 2016

Beginner

1080 pages

207h 57m

English

Pearson

Read now

Unlock full access

Deitel® Developer SeriesSimply SeriesVitalSource Web BooksLiveLessons Video Learning Products
Contacting the AuthorsJoin the Deitel & Associates, Inc. Social Media CommunitiesThe C++11 and C++14 StandardsKey Features of C++ How to Program, 10/eNew in This EditionObject-Oriented ProgrammingHundreds of Code ExamplesExercisesIllustrations and FiguresDependency ChartTeaching ApproachSecure C++ ProgrammingOnline Chapters, Appendices and Other ContentObtaining the Software Used in C++ How to Program, 10/eInstructor SupplementsOnline Practice and Assessment with MyProgrammingLab™ReviewersAbout the Authors About Deitel & Associates, Inc.
Objectives Outline

1.3.1 Moore’s Law1.3.2 Computer Organization
1.10.1 Compiling and Running an Application in Visual Studio 2015 for WindowsStep 1: Checking Your SetupStep 2: Launching Visual StudioStep 3: Creating a ProjectStep 4: Adding the GuessNumber.cpp File into the ProjectStep 5: Compiling and Running the ProjectStep 6: Entering Your First GuessStep 7: Entering Another GuessStep 8: Entering Additional GuessesStep 9: Playing the Game Again or Exiting the Application1.10.2 Compiling and Running Using GNU C++ on LinuxStep 1: Locating the Completed ApplicationStep 2: Compiling the ApplicationStep 3: Running the ApplicationStep 4: Entering Your First GuessStep 5: Entering Another GuessStep 6: Entering Additional GuessesStep 7: Playing the Game Again or Exiting the Application1.10.3 Compiling and Running with Xcode on Mac OS XStep 1: Checking Your SetupStep 2: Launching XcodeStep 3: Creating a ProjectStep 4: Deleting the main.cpp File from the ProjectStep 5: Adding the GuessNumber.cpp File into the ProjectStep 6: Compiling and Running the ProjectStep 7: Entering Your First GuessStep 8: Entering Another GuessStep 9: Entering Additional GuessesPlaying the Game Again or Exiting the Application
1.11.1 Windows—A Proprietary Operating System1.11.2 Linux—An Open-Source Operating System1.11.3 Apple’s OS X; Apple’s iOS for iPhone®, iPad® and iPod Touch® Devices1.11.4 Google’s Android
Objectives Outline
Objectives Outline
3.2.1 Instantiating an Object3.2.2 Headers and Source-Code Files3.2.3 Calling Class Account’s getName Member Function3.2.4 Inputting a string with getlinegetline Function Receiving a Line of Text from the User3.2.5 Calling Class Account’s setName Member FunctionDisplaying the Name That Was Entered by the User
3.3.1 Account Class Definition3.3.2 Keyword class and the Class BodyIdentifiers and Camel-Case Naming3.3.3 Data Member name of Type stringUse std:: with Standard Library Components in Headers3.3.4 setName Member FunctionsetName ParametersetName Parameter ListsetName Member Function BodyParameters Are Local VariablesArgument and Parameter Types Must Be Consistent3.3.5 getName Member Functionconst Member Functions3.3.6 Access Specifiers private and publicDefault Access for Class Members3.3.7 Account UML Class DiagramTop CompartmentMiddle CompartmentBottom CompartmentReturn TypesParameters
3.4.1 Defining an Account Constructor for Custom Object InitializationAccount Class’s Constructor Definitionexplicit KeywordUsing the Same Parameter Name in the Constructor and Member Function setName3.4.2 Initializing Account Objects When They’re CreatedDefault ConstructorThere’s No Default Constructor in a Class That Defines a Constructor3.4.3 Account UML Class Diagram with a Constructor
3.6.1 Data Member balanceAccount’s Member Functions Can All Use balance3.6.2 Two-Parameter Constructor with Validation3.6.3 deposit Member Function with Validation3.6.4 getBalance Member Function3.6.5 Manipulating Account Objects with BalancesDisplaying the Account Objects’ Initial BalancesReading a Deposit Amount from the User and Making a DepositDuplicated Code in the main Function3.6.6 Account UML Class Diagram with a Balance and Member Functions deposit and getBalance
Objectives Outline
4.4.1 Sequence Structure4.4.2 Selection Statements4.4.3 Iteration Statements4.4.4 Summary of Control Statements
4.6.1 Nested if…else Statements4.6.2 Dangling-else Problem4.6.3 BlocksSyntax and Logic ErrorsEmpty Statement4.6.4 Conditional Operator (?:)
4.9.1 Pseudocode Algorithm with Counter-Controlled Iteration4.9.2 Implementing Counter-Controlled IterationLocal Variables in mainInitialization Phase: Initializing Variables total and gradeCounterProcessing Phase: Reading 10 Grades from the UserTermination Phase: Calculating and Displaying the Class Average4.9.3 Notes on Integer Division and Truncation4.9.4 Arithmetic Overflow4.9.5 Input Validation
4.10.1 Top-Down, Stepwise Refinement: The Top and First Refinement4.10.2 Proceeding to the Second Refinement4.10.3 Implementing Sentinel-Controlled IterationProgram Logic for Sentinel-Controlled Iteration vs. Counter-Controlled IterationBraces in a while Statement4.10.4 Converting Between Fundamental Types Explicitly and Implicitlystatic_cast OperatorPromotionsCast Operators for Any Type4.10.5 Formatting Floating-Point Numberssetprecision Parameterized Stream Manipulatorfixed Nonparameterized Stream ManipulatorRounding Floating-Point Numbers4.10.6 Unsigned Integers and User Input
4.11.1 Problem StatementProblem Statement Observations4.11.2 Top-Down, Stepwise Refinement: Pseudocode Representation of the Top4.11.3 Top-Down, Stepwise Refinement: First Refinement4.11.4 Top-Down, Stepwise Refinement: Second Refinement4.11.5 Complete Second Refinement of the Pseudocode4.11.6 Program That Implements the Pseudocode Algorithm4.11.7 Preventing Narrowing Conversions with List InitializationA Look Back at Fig. 4.10
Objectives Outline
5.7.1 Demonstrating Class DollarAmountCalculating Compound Interest with DollarAmount5.7.2 Class DollarAmountC++11 Type int64_tDollarAmount ConstructorDollarAmount Member Functions add and subtractDollarAmount Member Function addInterestMember Function toStringBanker’s RoundingEven int64_t Is LimitedA Note About Arithmetic Operators and Modifying Operands
5.10.1 break Statement5.10.2 continue Statement
5.11.1 Logical AND (&&) Operator5.11.2 Logical OR (||) Operator5.11.3 Short-Circuit Evaluation5.11.4 Logical Negation (!) Operator5.11.5 Logical Operators ExamplePrecedence and Associativity of the Operators Presented So Far
Objectives Outline
6.5.1 Function Signatures and Function Prototypes6.5.2 Argument Coercion6.5.3 Argument-Promotion Rules and Implicit Conversions1Conversions Can Result in Incorrect Values
6.7.1 Rolling a Six-Sided Die6.7.2 Rolling a Six-Sided Die 60,000,000 TimesC++14 Digit Separators for Numeric Literals6.7.3 Randomizing the Random-Number Generator with srandDemonstrating srand6.7.4 Seeding the Random-Number Generator with the Current Time6.7.5 Scaling and Shifting Random Numbers
Section 6.11 Function-Call Stack and Activation RecordsSection 6.12 Inline FunctionsSection 6.13 References and Reference ParametersSection 6.14 Default ArgumentsSection 6.15 Unary Scope Resolution OperatorSection 6.16 Function OverloadingSection 6.17 Function TemplatesSection 6.18 RecursionSection 6.19 Example Using Recursion: Fibonacci SeriesSection 6.20 Recursion vs. Iteration
Objectives Outline
7.4.1 Declaring an array and Using a Loop to Initialize the array’s Elements7.4.2 Initializing an array in a Declaration with an Initializer ListFewer Initializers Than array ElementsMore Initializers Than array Elements7.4.3 Specifying an array’s Size with a Constant Variable and Setting array Elements with CalculationsConstant Variables7.4.4 Summing the Elements of an array7.4.5 Using a Bar Chart to Display array Data Graphically7.4.6 Using the Elements of an array as Counters7.4.7 Using arrays to Summarize Survey ResultsBounds Checking for array Subscripts7.4.8 Static Local arrays and Automatic Local arrays
7.7.1 Sorting7.7.2 Searching7.7.3 Demonstrating Functions sort and binary_search
Objectives Outline
8.2.1 Declaring Pointers8.2.2 Initializing Pointers8.2.3 Null Pointers Prior to C++11
8.3.1 Address (&) Operator8.3.2 Indirection (*) Operator8.3.3 Using the Address (&) and Indirection (*) OperatorsPrecedence and Associativity of the Operators Discussed So Far
8.5.1 Declaring and Accessing a Built-In Array8.5.2 Initializing Built-In Arrays8.5.3 Passing Built-In Arrays to Functions8.5.4 Declaring Built-In Array Parameters8.5.5 C++11: Standard Library Functions begin and end8.5.6 Built-In Array Limitations8.5.7 Built-In Arrays Sometimes Are Required
8.6.1 Nonconstant Pointer to Nonconstant Data8.6.2 Nonconstant Pointer to Constant Data8.6.3 Constant Pointer to Nonconstant Data8.6.4 Constant Pointer to Constant Data
8.8.1 Adding Integers to and Subtracting Integers from Pointers8.8.2 Subtracting Pointers8.8.3 Pointer Assignment8.8.4 Cannot Dereference a void*8.8.5 Comparing Pointers
8.9.1 Pointer/Offset Notation8.9.2 Pointer/Offset Notation with the Built-In Array’s Name as the Pointer8.9.3 Pointer/Subscript Notation8.9.4 Demonstrating the Relationship Between Pointers and Built-In Arrays
Objectives Outline
9.2.1 Interface of a Class9.2.2 Separating the Interface from the Implementation9.2.3 Time Class DefinitionInclude Guard19.2.4 Time Class Member Functions9.2.5 Scope Resolution Operator (::)9.2.6 Including the Class Header in the Source-Code File9.2.7 Time Class Member Function setTime and Throwing Exceptions9.2.8 Time Class Member Function toUniversalString and String Stream Processing9.2.9 Time Class Member Function toStandardString9.2.10 Implicitly Inlining Member Functions9.2.11 Member Functions vs. Global Functions9.2.12 Using Class TimeCalling setTime with Invalid Values9.2.13 Object Size
9.6.1 Constructors with Default ArgumentsNotes Regarding Class Time’s Set and Get Functions and Constructor9.6.2 Overloaded Constructors and C++11 Delegating Constructors
9.8.1 Constructors and Destructors for Objects in Global Scope9.8.2 Constructors and Destructors for Non-static Local Objects9.8.3 Constructors and Destructors for static Local Objects9.8.4 Demonstrating When Constructors and Destructors Are Called
9.14.1 Implicitly and Explicitly Using the this Pointer to Access an Object’s Data Members9.14.2 Using the this Pointer to Enable Cascaded Function Calls
9.15.1 Motivating Classwide Data9.15.2 Scope and Initialization of static Data Members9.15.3 Accessing static Data Members9.15.4 Demonstrating static Data Members
Objectives Outline
10.3.1 Operator Overloading Is Not Automatic10.3.2 Operators That You Do Not Have to Overload10.3.3 Operators That Cannot Be Overloaded10.3.4 Rules and Restrictions on Operator Overloading
10.10.1 Using the Array ClassCreating Arrays, Outputting Their Size and Displaying Their ContentsUsing the Overloaded Stream Extraction Operator to Fill an ArrayUsing the Overloaded Inequality OperatorInitializing a New Array with a Copy of an Existing Array’s ContentsUsing the Overloaded Assignment OperatorUsing the Overloaded Equality OperatorUsing the Overloaded Subscript Operator10.10.2 Array Class DefinitionOverloading the Stream Insertion and Stream Extraction Operators as friendsRange-Based for Does Not Work with Dynamically Allocated Built-In ArraysArray Default ConstructorArray Copy ConstructorArray DestructorgetSize Member FunctionOverloaded Assignment OperatorC++11: Move Constructor and Move Assignment OperatorC++11: Deleting Unwanted Member Functions from Your ClassOverloaded Equality and Inequality OperatorsOverloaded Subscript OperatorsC++11: Managing Dynamically Allocated Memory with unique_ptrC++11: Passing a List Initializer to a Constructor
Objectives Outline
11.2.1 CommunityMember Class Hierarchy11.2.2 Shape Class Hierarchy
11.3.1 Creating and Using a CommissionEmployee ClassCommissionEmployee ConstructorCommissionEmployee Member Functions earnings and toStringTesting Class CommissionEmployee11.3.2 Creating a BasePlusCommissionEmployee Class Without Using InheritanceDefining Class BasePlusCommissionEmployeeTesting Class BasePlusCommissionEmployeeExploring the Similarities Between Class BasePlusCommissionEmployee and Class CommissionEmployee11.3.3 Creating a CommissionEmployee–BasePlusCommissionEmployee Inheritance HierarchyCompilation Errors from Accessing Base-Class private MembersPreventing the Errors in BasePlusCommissionEmployeeIncluding the Base-Class Header in the Derived-Class Header with #includeLinking Process in an Inheritance Hierarchy11.3.4 CommissionEmployee–BasePlusCommissionEmployee Inheritance Hierarchy Using protected DataDefining Base-Class CommissionEmployee with protected DataClass BasePlusCommissionEmployeeTesting the Modified BasePlusCommissionEmployee ClassNotes on Using protected Data11.3.5 CommissionEmployee–BasePlusCommissionEmployee Inheritance Hierarchy Using private DataChanges to Class CommissionEmployee’s Member-Function DefinitionsChanges to Class BasePlusCommissionEmployee’s Member-Function DefinitionsBasePlusCommissionEmployee Member Function earningsBasePlusCommissionEmployee Member Function toStringTesting the Modified Class HierarchySummary of the CommissionEmployee–BasePlusCommissionEmployee Examples
Section 11.1 IntroductionSection 11.2 Base Classes and Derived ClassesSection 11.4 Constructors and Destructors in Derived ClassesSection 11.5 public, protected and private Inheritance
Objectives Outline
12.3.1 Invoking Base-Class Functions from Derived-Class ObjectsCreating Objects and Displaying Their ContentsAiming a Base-Class Pointer at a Base-Class ObjectAiming a Derived-Class Pointer at a Derived-Class ObjectAiming a Base-Class Pointer at a Derived-Class Object12.3.2 Aiming Derived-Class Pointers at Base-Class Objects12.3.3 Derived-Class Member-Function Calls via Base-Class PointersDowncasting
12.4.1 Why virtual Functions Are Useful12.4.2 Declaring virtual Functions12.4.3 Invoking a virtual Function Through a Base-Class Pointer or Reference12.4.4 Invoking a virtual Function Through an Object’s Name12.4.5 virtual Functions in the CommissionEmployee Hierarchy12.4.6 virtual Destructors12.4.7 C++11: final Member Functions and Classes
12.6.1 Pure virtual Functions12.6.2 Device Drivers: Polymorphism in Operating Systems
12.7.1 Creating Abstract Base Class EmployeeEmployee Class HeaderEmployee Class Member-Function Definitions12.7.2 Creating Concrete Derived Class SalariedEmployeeSalariedEmployee Class Member-Function Definitions12.7.3 Creating Concrete Derived Class CommissionEmployee12.7.4 Creating Indirect Concrete Derived Class BasePlusCommissionEmployee12.7.5 Demonstrating Polymorphic Processing
Section 12.1 IntroductionSection 12.2 Introduction to Polymorphism: Polymorphic Video GameSection 12.3 Relationships Among Objects in an Inheritance HierarchySection 12.4.2 Declaring virtual FunctionsSection 12.4.3 Invoking a virtual Function Through a Base-Class Pointer or ReferenceSection 12.4.4 Invoking a virtual Function Through an Object’s NameSection 12.4.5 virtual Functions in the CommissionEmployee HierarchySection 12.4.6 virtual DestructorsSection 12.4.7 C++11: final Member Functions and ClassesSection 12.5 Type Fields and switch StatementsSection 12.6 Abstract Classes and Pure virtual FunctionsSection 12.6.1 Pure Virtual FunctionsSection 12.8 (Optional) Polymorphism, Virtual Functions and Dynamic Binding “Under the Hood”Section 12.9 Case Study: Payroll System Using Polymorphism and Runtime Type Information with Downcasting, dynamic_cast, typeid and type_info
Objectives Outline
13.2.1 Classic Streams vs. Standard Streams13.2.2 iostream Library Headers13.2.3 Stream Input/Output Classes and Objectsiostream Library Aliases Are Defined with typedefStandard Stream Objects cin, cout, cerr and clog
13.3.1 Output of char* Variables13.3.2 Character Output Using Member Function put
13.4.1 get and getline Member FunctionsUsing Member Functions eof, get and putComparing cin and cin.getUsing Member Function getline13.4.2 istream Member Functions peek, putback and ignore13.4.3 Type-Safe I/O
13.6.1 Integral Stream Base: dec, oct, hex and setbase13.6.2 Floating-Point Precision (precision, setprecision)13.6.3 Field Width (width, setw)13.6.4 User-Defined Output Stream Manipulators
13.7.1 Trailing Zeros and Decimal Points (showpoint)13.7.2 Justification (left, right and internal)13.7.3 Padding (fill, setfill)13.7.4 Integral Stream Base (dec, oct, hex, showbase)13.7.5 Floating-Point Numbers; Scientific and Fixed Notation (scientific, fixed)13.7.6 Uppercase/Lowercase Control (uppercase)13.7.7 Specifying Boolean Format (boolalpha)13.7.8 Setting and Resetting the Format State via Member Function flags
Section 13.1 IntroductionSection 13.2 StreamsSection 13.2.2 iostream Library HeadersSection 13.2.3 Stream Input/Output Classes and ObjectsSection 13.3 Stream OutputSection 13.4 Stream InputSection 13.5 Unformatted I/O Using read, write and gcountSection 13.6 Stream Manipulators: A Deeper LookSection 13.7 Stream Format States and Stream ManipulatorsSection 13.8 Stream Error StatesSection 13.9 Tying an Output Stream to an Input Stream
Objectives Outline
14.3.1 Opening a File14.3.2 Opening a File via the open Member Function14.3.3 Testing Whether a File Was Opened Successfully14.3.4 Overloaded bool Operator14.3.5 Processing Data14.3.6 Closing a File14.3.7 Sample Execution
14.4.1 Opening a File for Input14.4.2 Reading from the File14.4.3 File-Position Pointers14.4.4 Case Study: Credit Inquiry Program
14.8.1 Writing Bytes with ostream Member Function write14.8.2 Converting Between Pointer Types with the reinterpret_cast Operator14.8.3 Credit-Processing Program14.8.4 Opening a File for Output in Binary Mode
14.9.1 Opening a File for Input and Output in Binary Mode14.9.2 Positioning the File-Position Pointer
Section 14.1 IntroductionSection 14.2 Files and StreamsSection 14.3 Creating a Sequential FileSection 14.4 Reading Data from a Sequential FileSection 14.5 C++14: Reading and Writing Quoted TextSection 14.6 Updating Sequential FilesSection 14.7 Random-Access FilesSection 14.8 Creating a Random-Access FileSection 14.9 Writing Data Randomly to a Random-Access FileSection 14.10 Reading from a Random-Access File SequentiallySection 14.12 Object SerializationSelf-Review Exercises
Objectives Outline
15.5.1 vector Sequence ContainerUsing vectors and IteratorsCreating a vectorvector Member Functions size and capacityvector Member Function push_backUpdated size and capacity After Modifying a vectorvector GrowthOutputting Built-in Array Contents with PointersOutputting vector Contents with IteratorsDisplaying the vector’s Contents in Reverse with const_reverse_iteratorsC++11: shrink_to_fitvector Element-Manipulation Functionsostream_iteratorcopy Algorithmvector Member Functions front and backAccessing vector Elementsvector Member Function insertvector Member Function erasevector Member Function insert with Three Arguments (Range insert)vector Member Function clear15.5.2 list Sequence ContainerC++11: forward_list Containerlist Member FunctionsCreating list Objectslist Member Function sortlist Member Function splicelist Member Function mergelist Member Function pop_frontlist Member Function uniquelist Member Function swaplist Member Functions assign and remove15.5.3 deque Sequence Container
15.6.1 multiset Associative ContainerCreating a multisetmultiset Member Function countmultiset Member Function insertmultiset Member Function findInserting Elements of Another Container into a multisetmultiset Member Functions lower_bound and upper_boundpair Objects and multiset Member Function equal_rangeC++11: Variadic Class Template tupleC++14: Heterogeneous Lookup15.6.2 set Associative Container15.6.3 multimap Associative ContainerC++11: List Initializing a Key–Value Pair Container15.6.4 map Associative Container
15.7.1 stack Adapter15.7.2 queue Adapter15.7.3 priority_queue Adapter
Section 15.1 IntroductionSection 15.2 Introduction to ContainersSection 15.3 Introduction to IteratorsSection 15.4 Introduction to AlgorithmsSection 15.5 Sequence ContainersSection 15.5.1 vector Sequence ContainerSection 15.5.2 list Sequence ContainerSection 15.5.3 deque Sequence ContainerSection 15.6 Associative ContainersSection 15.6.1 multiset Associative ContainerSection 15.6.2 set Associative ContainerSection 15.6.3 multimap Associative ContainerSection 15.6.4 map Associative ContainerSection 15.7 Container AdaptersSection 15.7.1 stack AdapterSection 15.7.2 queue AdapterSection 15.7.3 priority_queue AdapterSection 15.8 Class bitset
Discussion QuestionsProgramming Exercises
Objectives Outline
Iterator Invalidation
16.3.1 Algorithm for_each16.3.2 Lambda with an Empty Introducer16.3.3 Lambda with a Nonempty Introducer—Capturing Local Variables16.3.4 Lambda Return Types
16.4.1 fill, fill_n, generate and generate_nfill Algorithmfill_n Algorithmgenerate Algorithmgenerate_n AlgorithmUsing the generate_n Algorithm with a LambdaA Note About Reading Standard Library Algorithm Documentation16.4.2 equal, mismatch and lexicographical_compareequal Algorithmequal Algorithm with Binary Predicate Functionmismatch Algorithmauto Variables and List Initializationlexicographical_compare Algorithm16.4.3 remove, remove_if, remove_copy and remove_copy_ifremove Algorithmremove_copy Algorithmremove_if Algorithmremove_copy_if Algorithm16.4.4 replace, replace_if, replace_copy and replace_copy_ifreplace Algorithmreplace_copy Algorithmreplace_if Algorithmreplace_copy_if Algorithm16.4.5 Mathematical Algorithmsshuffle Algorithmcount Algorithmcount_if Algorithmmin_element Algorithmmax_element AlgorithmC++11: minmax_element Algorithmaccumulate Algorithmtransform Algorithm16.4.6 Basic Searching and Sorting Algorithmsfind AlgorithmStoring Lambdas in Variablesfind_if Algorithmsort Algorithmbinary_search AlgorithmC++11: all_of AlgorithmC++11: any_of AlgorithmC++11: none_of AlgorithmC++11: find_if_not Algorithm16.4.7 swap, iter_swap and swap_rangesswap Algorithmiter_swap Algorithmswap_ranges Algorithm16.4.8 copy_backward, merge, unique and reversecopy_backward Algorithmmerge Algorithmback_inserter, front_inserter and inserter Iterator Adaptersunique Algorithmreverse AlgorithmC++11: copy_if and copy_n Algorithms16.4.9 inplace_merge, unique_copy and reverse_copyinplace_merge Algorithmunique_copy Algorithmreverse_copy Algorithm16.4.10 Set Operationsincludes Algorithmset_difference Algorithmset_intersection Algorithmset_symmetric_difference Algorithmset_union Algorithm16.4.11 lower_bound, upper_bound and equal_rangelower_bound Algorithmupper_bound Algorithmequal_range AlgorithmLocating Insertion Points in Sorted Sequences16.4.12 min, max, minmax and minmax_elementAlgorithms min and max with Two ParametersC++11: min and max Algorithms with initializer_list ParametersC++11: minmax AlgorithmC++11: minmax_element Algorithm
Advantages of Function Objects over Function PointersPredefined Function Objects of the Standard Template LibraryUsing the accumulate AlgorithmFunction sumSquaresClass SumSquaresClassCalling Algorithm accumulate
Mutating Sequence AlgorithmsNonmodifying Sequence AlgorithmsSorting and Related AlgorithmsNumerical Algorithms
Section 16.1 IntroductionSection 16.3 Lambda ExpressionsSection 16.3.1 Algorithm for_eachSection 16.3.2 Lambda with an Empty IntroducerSection 16.3.3 Lambda with a Nonempty Introducer—Capturing Local VariablesSection 16.3.4 Lambda Return TypesSection 16.4.1 fill, fill_n, generate and generate_nSection 16.4.2 equal, mismatch and lexicographical_compareSection 16.4.3 remove, remove_if, remove_copy and remove_copy_ifSection 16.4.4 replace, replace_if, replace_copy and replace_copy_ifSection 16.4.5 Mathematical AlgorithmsSection 16.4.6 Basic Searching and Sorting AlgorithmsSection 16.4.7 swap, iter_swap and swap_rangesSection 16.4.8 copy_backward, merge, unique and reverseSection 16.4.9 inplace_merge, unique_copy and reverse_copySection 16.4.10 Set OperationsSection 16.4.11 lower_bound, upper_bound and equal_rangeSection 16.4.12 min, max, minmax and minmax_elementSection 16.5 Function Objects
Objectives Outline
17.2.1 Defining an Exception Class to Represent the Type of Problem That Might Occur17.2.2 Demonstrating Exception Handling17.2.3 Enclosing Code in a try Block
17.2.5 Termination Model of Exception Handling17.2.6 Flow of Program Control When the User Enters a Nonzero Denominator17.2.7 Flow of Program Control When the User Enters a Denominator of Zero
17.7.1 Destructors Called Due to Exceptions17.7.2 Initializing Local Objects to Acquire Resources
17.8.1 new Throwing bad_alloc on Failure17.8.2 new Returning nullptr on Failure17.8.3 Handling new Failures Using Function set_new_handler
Demonstrating unique_ptr17.9.1 unique_ptr Ownership17.9.2 unique_ptr to a Built-In Array
Section 17.1 IntroductionSection 17.2.1 Defining an Exception Class to Represent the Type of Problem That Might OccurSection 17.2.5 Termination Model of Exception HandlingSection 17.2.7 Flow of Program Control When the User Enters a Denominator of ZeroSection 17.3 Rethrowing an ExceptionSection 17.4 Stack UnwindingSection 17.5 When to Use Exception HandlingSection 17.6 noexcept: Declaring Functions That Do Not Throw ExceptionsSection 17.7.1 Destructors Called Due to ExceptionsSection 17.7.2 Initializing Local Objects to Acquire ResourcesSection 17.8 Processing new FailuresSection 17.9 Class unique_ptr and Dynamic Memory AllocationSection 17.10 Standard Library Exception Hierarchy
Objectives Outline
18.2.1 Creating Class Template Stack<T>Creating Class Template Stack<T>18.2.2 Class Template Stack<T>’s Data Representation18.2.3 Class Template Stack<T>’s Member Functions18.2.4 Declaring a Class Template’s Member Functions Outside the Class Template Definition18.2.5 Testing Class Template Stack<T>
Matching Process for Overloaded Functions
Section 18.1 IntroductionSection 18.2 Class TemplatesSection 18.4 Nontype ParametersSection 18.5 Default Arguments for Template Type ParametersSection 18.6 Overloading Function Templates
Objectives Outline
19.1.1 Always Prefer the Standard Library’s Containers, Iterators and Algorithms, if Possible19.1.2 Special Section: Building Your Own Compiler
19.3.1 Testing Our Linked List Implementation19.3.2 Class Template ListNode19.3.3 Class Template List19.3.4 Member Function insertAtFront19.3.5 Member Function insertAtBack19.3.6 Member Function removeFromFront19.3.7 Member Function removeFromBack19.3.8 Member Function print19.3.9 Circular Linked Lists and Double Linked Lists
19.4.1 Taking Advantage of the Relationship Between Stack and List19.4.2 Implementing a Class Template Stack Class Based By Inheriting from List19.4.3 Dependent Names in Class Templates19.4.4 Testing the Stack Class Template19.4.5 Implementing a Class Template Stack Class With Composition of a List Object
19.5.1 Applications of Queues19.5.2 Implementing a Class Template Queue Class Based By Inheriting from List19.5.3 Testing the Queue Class Template
19.6.1 Basic Terminology19.6.2 Binary Search TreesImplementing the Binary Search Tree Program19.6.3 Testing the Tree Class Template19.6.4 Class Template TreeNode19.6.5 Class Template Tree19.6.6 Tree Member Function insertNodeHelper19.6.7 Tree Traversal FunctionsInorder Traversal AlgorithmPreorder Traversal AlgorithmPostorder Traversal Algorithm19.6.8 Duplicate Elimination19.6.9 Overview of the Binary Tree Exercises
Objectives Outline
20.2.1 Linear SearchFunction Template linearSearchBig O: Constant RuntimeBig O: Linear RuntimeBig O: Quadratic RuntimeO(n2) PerformanceLinear Search’s Runtime20.2.2 Binary SearchBinary Search of 15 Integer ValuesBinary Search ExampleFunction Template binarySearchFunction mainEfficiency of Binary Search
20.3.1 Insertion SortInsertion Sort AlgorithmFirst IterationSecond IterationThird Iteration and BeyondFunction Template insertionSortBig O: Efficiency of Insertion Sort20.3.2 Selection SortSelection Sort AlgorithmFirst IterationSecond IterationThird IterationFunction Template selectionSortEfficiency of Selection Sort20.3.3 Merge Sort (A Recursive Implementation)Sample MergeRecursive ImplementationDemonstrating Merge SortFunction mergeSortFunction mergeEfficiency of Merge SortSummary of Searching and Sorting Algorithm Efficiencies
Objectives Outline
Objectives Outline
Objectives Outline
Objectives Outline

Content preview from C++ How to Program, 10/e

20 Searching and Sorting

Objectives

In this chapter you’ll:

Search for a given value in an array using linear search and binary search.
Sort an array using insertion sort, selection sort and the recursive merge sort algorithms.
Use Big O notation to express the efficiency of searching and sorting algorithms and to compare their performance.
Understand the nature of algorithms of constant, linear and quadratic runtime.

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Start your free trial

C++ How to Program, Sixth Edition

P. J. Deitel - Deitel & Associates, Inc., H. M. Deitel - Deitel & Associates, Inc.

C++ How to Program, Ninth Edition

Paul Deitel, Harvey Deitel

Programming: Principles and Practice Using C++, 3rd Edition

Bjarne Stroustrup

A Tour of C++, 3rd Edition

Bjarne Stroustrup

Publisher Resources

ISBN: 9780134448930Purchase book