9.4. How a vector Grows
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
9.4. How a vector Grows
To support fast random access, vector elements are stored contiguously—each element is adjacent to the previous element. Ordinarily, we should not care about how a library type is implemented; all we should care about is how to use it. However, in the case of vectors and strings, part of the implementation leaks into its interface.
Given that elements are contiguous, and that the size of the container is flexible, consider what must happen when we add an element to a vector or a string: If there is no room for the new element, the container can’t just add an element somewhere else in memory—the elements must be contiguous. Instead, the container must allocate new memory to hold the existing elements plus the new one, move the elements from the old location into the new space, add the new element, and deallocate the old memory. If vector did this memory allocation and deallocation each time we added an element, performance would be unacceptably slow.
Exercises Section 9.3.6
Exercise 9.31: The program on page 354 to remove even-valued elements and duplicate odd ones will not work on a list or forward_list. Why? Revise the program so that it works on these types as well.
Exercise 9.32: In the program onpage 354 would it be legal to write the call to insert as follows? If not, why not?
iter = vi.insert(iter, *iter++);
Exercise 9.33: In the final example in this section what would happen if we did not assign the result of insert to begin? Write a program that omits this assignment to see if your expectation was correct.
Exercise 9.34: Assuming vi is a container of ints that includes even and odd values, predict the behavior of the following loop. After you’ve analyzed this loop, write a program to test whether your expectations were correct.
iter = vi.begin();
while (iter != vi.end())
if (*iter % 2)
iter = vi.insert(iter, *iter);
++iter;
To avoid these costs, library implementors use allocation strategies that reduce the number of times the container is reallocated. When they have to get new memory, vector and string implementations typically allocate capacity beyond what is immediately needed. The container holds this storage in reserve and uses it to allocate new elements as they are added. Thus, there is no need to reallocate the container for each new element.
This allocation strategy is dramatically more efficient than reallocating the container each time an element is added. In fact, its performance is good enough that in practice a vector usually grows more efficiently than a list or a deque, even though the vector has to move all of its elements each time it reallocates memory.
-
No Comment