...But Algorithms Do Depend on Element-Type Operations
by Barbara E. Moo, Josée Lajoie, Stanley B. Lippman
C++ Primer, Fifth Edition
- Title Page
- Copyright Page
- Dedication Page
- Contents
- New Features in C++11
- Preface
- Chapter 1. Getting Started
- Part I. The Basics
- Contents
- Chapter 2. Variables and Basic Types
- Chapter 3. Strings, Vectors, and Arrays
- Chapter 4. Expressions
- Contents
- 4.1. Fundamentals
- 4.2. Arithmetic Operators
- 4.3. Logical and Relational Operators
- 4.4. Assignment Operators
- 4.5. Increment and Decrement Operators
- 4.6. The Member Access Operators
- 4.7. The Conditional Operator
- 4.8. The Bitwise Operators
- 4.9. The sizeof Operator
- 4.10. Comma Operator
- 4.11. Type Conversions
- 4.12. Operator Precedence Table
- Chapter Summary
- Defined Terms
- Chapter 5. Statements
- Chapter 6. Functions
- Chapter 7. Classes
- Part II. The C++ Library
- Contents
- Chapter 8. The IO Library
- Chapter 9. Sequential Containers
- Chapter 10. Generic Algorithms
- Chapter 11. Associative Containers
- Chapter 12. Dynamic Memory
- Part III. Tools for Class Authors
- Contents
- Chapter 13. Copy Control
- Chapter 14. Overloaded Operations and Conversions
- Contents
- 14.1. Basic Concepts
- 14.2. Input and Output Operators
- 14.3. Arithmetic and Relational Operators
- 14.4. Assignment Operators
- 14.5. Subscript Operator
- 14.6. Increment and Decrement Operators
- 14.7. Member Access Operators
- 14.8. Function-Call Operator
- 14.9. Overloading, Conversions, and Operators
- Chapter Summary
- Defined Terms
- Chapter 15. Object-Oriented Programming
- Contents
- 15.1. OOP: An Overview
- 15.2. Defining Base and Derived Classes
- 15.3. Virtual Functions
- 15.4. Abstract Base Classes
- 15.5. Access Control and Inheritance
- 15.6. Class Scope under Inheritance
- 15.7. Constructors and Copy Control
- 15.8. Containers and Inheritance
- 15.9. Text Queries Revisited
- Chapter Summary
- Defined Terms
- Chapter 16. Templates and Generic Programming
- Part IV. Advanced Topics
- Contents
- Chapter 17. Specialized Library Facilities
- Chapter 18. Tools for Large Programs
- Chapter 19. Specialized Tools and Techniques
- Appendix A. The Library
- Contents
- A.1. Library Names and Headers
- A.2. A Brief Tour of the Algorithms
- A.2.1. Algorithms to Find an Object
- A.2.2. Other Read-Only Algorithms
- A.2.3. Binary Search Algorithms
- A.2.4. Algorithms That Write Container Elements
- A.2.5. Partitioning and Sorting Algorithms
- A.2.6. General Reordering Operations
- A.2.7. Permutation Algorithms
- A.2.8. Set Algorithms for Sorted Sequences
- A.2.9. Minimum and Maximum Values
- A.2.10. Numeric Algorithms
- A.3. Random Numbers
- Index
- Add Pages
...But Algorithms Do Depend on Element-Type Operations
Although iterators make the algorithms container independent, most of the algorithms use one (or more) operation(s) on the element type. For example, step 2, uses the element type’s == operator to compare each element to the given value.
Other algorithms require that the element type have the < operator. However, as we’ll see, most algorithms provide a way for us to supply our own operation to use in place of the default operator.
Exercises Section 10.1
Exercise 10.1: The algorithm header defines a function named count that, like find, takes a pair of iterators and a value. count returns a count of how often that value appears. Read a sequence of ints into a vector and print the count of how many elements have a given value.
Exercise 10.2: Repeat the previous program, but read values into a list of strings.
Key Concept: Algorithms Never Execute Container Operations
The generic algorithms do not themselves execute container operations. They operate solely in terms of iterators and iterator operations. The fact that the algorithms operate in terms of iterators and not container operations has a perhaps surprising but essential implication: Algorithms never change the size of the underlying container. Algorithms may change the values of the elements stored in the container, and they may move elements around within the container. They do not, however, ever add or remove elements directly.
As we’ll see in § 10.4.1 (p. 401), there is a special class of iterator, the inserters, that do more than traverse the sequence to which they are bound. When we assign to these iterators, they execute insert operations on the underlying container. When an algorithm operates on one of these iterators, the iterator may have the effect of adding elements to the container. The algorithm itself, however, never does so.
-
No Comment