TECH-THINKER: 1/16/11

Friday, January 21, 2011

C++ Primer, Fourth Edition:Notes Chapter 10 Associative Containers

Associative containers differ in a fundamental respect from the sequential containers: Elements in an associative container are stored and retrieved by a key, in contrast to elements in a sequential container, which are stored and accessed sequentially by their position within the container

Associative containers support efficient lookup and retrieval by a key. The two primary associative-container types are map and set. The elements in a map are keyvalue pairs: The key serves as an index into the map, and the value represents the data that are stored and retrieved. A set contains only a key and supports efficient queries to whether a given key is present

In general, a set is most useful when we want to store a collection of distinct values efficiently, and a map is most useful when we wish to store (and possibly modify) a value associated with each key

We might use a set to hold words that we want to ignore when doing some kind of text processing. A dictionary would be a good use for a map: The word would be the key, and its definition would be the value

An object of the map or set type may contain only a single element with a given key. There is no way to add a second element with the same key. If we need to have multiple instances with a single key, then we can use multimap or multi set, which do allow multiple elements with a given key

Table 10.1. Associative Container Types
`map`	Associative array; elements stored and retrieved by key
`set`	Variable-sized collection with fast retrieval by key
`multimap`	`map` in which a key can appear multiple times
`multiset`	`set` in which a key can appear multiple times

Section 10.1 Preliminaries: the pair Type

Before we look at the associative containers, we need to know about a simple companion library type named pair, which is defined in the utility header.

Creating and Initializing pairs

A pair holds two data values. Like the containers, pair is a template type. Unlike the containers we've seen so far, we must supply two type names when we create a pair: A pair holds two data members, each of which has the corresponding named type
When we create pair objects with no initializer, the default constructor value-initializes the members

The pair type can be unwieldy to type, so when we wish to define a number of objects of the same pair type, it is convenient to use a typedef

Table 10.2. Operations on `pairs`
`pair<T1, T2> p1;`	Create an empty `pair` with two elements of types `T1` and `T2`. The elements are value-initialized (Section 3.3.1, p. 92).
`pair<T1, T2> p1(v1, v2);`
	Create a `pair` with types `T1` and `T2` initializing the `first` member from `v1` and the `second` from `v2`.
`make_pair(v1, v2)`	Creates a new `pair` from the values `v1` and `v2`. The type of the `pair` is inferred from the types of `v1` and `v2`.
`p1 < p2`	Less than between two pair objects. Less than is defined as dictionary ordering: Returns `true` if `p1.first < p2.first` or if `!(p2.first < p1.first) && p1.second < p2.second`.
`p1 == p2`	Two `pair`s are equal if their `first` and `second` members are respectively equal. Uses the underlying element `==` operator.
`p.first`	Returns the (`public`) data member of `p` named `first`.
`p.second`	Returns the (`public`) data member of `p` named `second`.

Operations on pairs
1. Unlike other library types, the pair class gives us direct access to its data members: Its members are public

Generating a New pair

In addition to the constructors, the library defines the make_pair function, which generates a new pair from its two arguments. We might use this function to make a new pair to assign to an existing pair

// EXE-10.1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <utility>
#include <string>
#include <iostream>
#include <vector>

using namespace std;

int main()
{
	typedef pair<string, string> Author;
	if("Creating and Initializing pairs")
	{
		pair<string, string> anon;       // holds two strings
		pair<string, int> word_count;    // holds a string and an int
		pair< string, vector<int> > line; // holds string and vector<int>
		pair<string, string> author("James", "Joyce");
		
		Author proust("Marcel", "Proust");
		Author joyce("James", "Joyce");

	}
	if("Operations on pairs")
	{
		Author author("James","Joyce");
		string firstBook;
		// access and test the data members of the pair
		if (author.first == "James" && author.second == "Joyce")
			firstBook = "Stephen Hero";

	}
	if("Generating a New pair")
	{
		pair<string, string> next_auth;
		string first, last;
		while (cin >> first >> last) {
			// generate a pair from first and last
			next_auth = make_pair(first, last);

			// use pair constructor to make first and last into a pair
			//next_auth = pair<string, string>(first, last);

			// process next_auth...
		}
	}

	int screen_hold;
	cin >> screen_hold;

	return 0;
}

Section 10.2 Associative Containers

The operations common to sequential and associative containers are
1. The first three constructors described in Table 9.2 (p. 307):
2. ```
     C<T> c;          // creates an empty container
     // c2 must be same type as c1
     C<T> c1(c2);    // copies elements from c2 into c1
     // b and e are iterators denoting a sequence
     C<T> c(b, e);   // copies elements from the sequence into c
```
3. The relational operations described in Section 9.3.4 (p. 321
4. The begin, end, rbegin, and rend operations of Table 9.6 (p. 317
5. The typedefs listed in Table 9.5 (p. 316). Note that for map, the value_type is not the same as the element type. Instead, value_type is a pair representing the types of the keys and associated values. Section 10.3.2 (p. 361) explains the typedefs for maps in more detail
6. The swap and assignment operator described in Table 9.11 (p. 329). Associative containers do not provide the assign functions
7. The clear and erase operations from Table 9.10 (p. 326), except that the erase operation on an associative container returns void
8. The size operations in Table 9.8 (p. 324) except for resize, which we cannot use on an associative container
Elements Are Ordered by Key
1. The associative container types define additional operations beyond the ones just listed. They also redefine the meaning or return type of operations that are in common with the sequential containers. The differences in these common operations reflect the use of keys in the associative containers
2. There is one important consequence of the fact that elements are ordered by key: When we iterate across an associative container, we are guaranteed that the elements are accessed in key order, irrespective of the order in which the elements were placed in the container

Section 10.3 The map Type

A map is a collection of keyvalue pairs. The map type is often referred to as an associative array: It is like the built-in array type, in that the key can be used as an index to fetch a value. It is associative in that values are associated with a particular key rather than being fetched by position in the array

10.3.1. Defining a map

To use a map, we must include the map header

Table 10.3. Constructors for `map`
`map<k, v> m;`	Create an empty `map` named `m` with key and value types `k` and `v`.
`map<k, v> m(m2);`	Create `m` as a copy of `m2`; `m` and `m2` must have the same key and value types.
`map<k, v> m(b, e);`	Create `m` as a copy of the elements from the range denoted by iterators `b` and `e`. Elements must have a type that can be converted to `pair<const k, v>`.

Constraints on the Key Type
1. Whenever we use an associative container, its keys have not only a type, but also an associated comparison function. By default, the library uses the < operator for the key type to compare the keys
2. Whichever comparison function we use must define a strict weak ordering over the key type. We can think of a strict weak ordering as "less than," although we might choose to define a more complicated comparison function. However we define it, such a comparison function must always yield false when we compare a key with itself. Moreover, if we compare two keys, they cannot both be "less than" each other, and if k1 is "less than" k2, which in turn is "less than" k3, then k1 must be "less than" k3. If we have two keys, neither of which is "less than" the other, the container will treat them as equal. When used as a key to a map, either value could be used to access the corresponding element
3. In practice, what's important is that the key type must define the < operator and that that operator should "do the right thing."
4. The key type needs to support only the < operator. There is no requirement that it support the other relational or equality operators

10.3.2. Types Defined by map

The elements of a map are keyvalue pairs That is, each element has two parts: its key and the value associated with that key. The value_type for a map reflects this fact. This type is more complicated than those we've seen for other containers: value_type is a pair that holds the key and value of a given element. Moreover, the key is const

Table 10.4. Types Defined by the `map` Class
`map<K, V>::key_type`	The type of the keys used to index the `map`.
`map<K, V>::mapped_type`	The type of the values associated with the keys in the `map`.
`map<K, V>::value_type`	A pair whose first element has type `const`
	`map<K, V>::key_type` and `second` has type
	`map<K, V>::mapped_type`.

When learning the map interface, it is essential to remember that the value_type is a pair and that we can change the value but not the key member of that pair
Dereferencing a map Iterator Yields a pair
1. When we dereference an iterator, we get a reference to a value of the container's value_type
Additional map Typedefs
1. The map class defines two additional types, key_type and mapped_type, that let us access the type of either the key or the value

10.3.3. Adding Elements to a map
1. We can do so either by using the insert member or by fetching an element using the subscript operator and then assigning a value to the element returned. In both cases, the fact that there can be only a single element for a given key affects the behavior of these operations
2. The following steps take place
  1. word_count is searched for the element whose key is Anna. The element is not found.
  2. A new keyvalue pair is inserted into word_count. The key is a const string holding Anna. The value is value initialized, meaning in this case that the value is 0.
  3. The new keyvalue pair is inserted into word_count.
  4. The newly inserted element is fetched and is given the value 1.
3. Subscripting a map behaves quite differently from subscripting an array or vector: Using an index that is not already present adds an element with that index to the map
4. As with other subscript operators, the map subscript takes an index (that is, a key) and fetches the value associated with that key. When we look for a key that is already in the map, then the behavior is the same for a map subscript or a vector subscript: The value associated with the key is returned. For maps only, if the key is not already present, a new element is created and inserted into the map for that key. The associated value is value-initialized: An element of class type is initialized using the default constructor for the element type; a built-in type is initialized to 0
5. Using the Value Returned from a Subscript Operation
  1. Unlike vector or string, the type returned by map subscript operator differs from the type obtained by dereferencing a map iterator
6. Programming Implications of the Subscript Behavior
10.3.4. Subscripting a map

10.3.5. Using map::insert

The insert members operate similarly to the operations on sequential containers (Section 9.3.3, p. 318), with one important caveat: We must account for the effect of the key.
The key impacts the argument types: The versions that insert a single element take a value that is a keyvalue pair. Similarly, for the version that takes an iterator pair, the iterators must refer to elements that are keyvalue pairs. The other difference is the return type from the version of insert that takes a single value, which we will cover in the remainder of this section

Using insert Instead of Subscripting

Alternatively, we could insert the element directly by using the syntactically more intimidating insert member

Table 10.5. `insert` Operations on maps
`m.insert(e)`	`e` is a value of the `value_type` for `m`. If the key(`e.first)` is not in `m`, inserts a new element with value `e.second`. If the key is in `m`, then `m` is unchanged. Returns a `pair` containing a `map` iterator referring to the element with key `e.first` and a `bool` indicating whether the element was inserted or not.
`m.insert(beg, end)`	`beg` and `end` are iterators that denote a range of values that are keyvalue `pair`s with the same type as `m`'s `value_type`. For each element in the range, if the given key is not already in `m`, it inserts the key and its associated value into `m`. Returns `void`.
`m.insert(iter, e)`	`e is` a value of the `value_type` for `m`. If the key(`e.first)` is not in `m`, inserts the new element using the iterator `iter` as a hint for where to begin the search for where the new element should be stored. Returns an iterator that refers to the element in `m` with given key.

// if Anna not already in word_count, inserts new element with value 1
     word_count.insert(map<string, int>::value_type("Anna", 1));

Remember that value_type is a synonym for the type pair<const K, V>, where K is the key type and V is the type of the associated value. The argument to insert constructs a new object of the appropriate pair type to insert into the map
By using insert, we can avoid the extraneous initialization of the value that happens when we insert a new map element as a side-effect of using a subscript

Testing the Return from insert
1. However, the version of insert that takes a single keyvalue pair does return a value. That value is a pair that contains an iterator that refers to the element in the map with the corresponding key, and a bool that indicates whether the element was inserted
Unwinding the Syntax

10.3.6. Finding and Retrieving a map Element
10.3.7. Erasing Elements from a map
10.3.8. Iterating across a map
10.3.9. A Word Transformation Map

Section 10.4 The set Type

1. In contrast, a set is simply a collection of keys

2. A set is most useful when we simply want to know whether a value is present

3. With two exceptions, set supports the same operations as map

o All the common container operations listed in Section 10.2 (p. 358).

o The constructors described in Table 10.3 (p. 360).

o The insert operations described in Table 10.5 (p. 365).

o The count and find operations described in Table 10.6 (p. 367).

o The erase operations described in Table 10.7 (p. 369).

4. The exceptions are that set does not provide a subscript operator and does not define mapped_type. In a set, the value_type is not a pair; instead it and key_type are the same type. They are each the type of the elements stored in the set

5. As with map, the keys of a set must be unique and may not be changed

6. 10.4.1. Defining and Using sets

1. To use a set, we must include the set header. The operations on sets are essentially identical to those on maps

2. Adding Elements to a set

3. Fetching an Element from a set

1. There is no subscript operator on sets

2. To fetch an element from a set by its key, we use the find operation. If we just want to know whether the element is present, we could also use count, which returns the number of elements in the set with a given key

3. Just as we cannot change the key part of a map element, the keys in a set are also const

7. 10.4.2. Building a Word-Exclusion Set

Section 10.5 The multimap and multiset Types

1. The types multiset and a multimap allow multiple instances of a key.
2. The multimap and multiset types are defined in the same headers as the corresponding single-element versions: the map and set headers, respectively
3. The operations supported by multimap and multiset are the same as those on map and set, respectively, with one exception: multimap does not support subscripting
4. We cannot subscript a multimap because there may be more than one value associated with a given key
5. The insert operations described in Table 10.5 (p. 365) and the erase operations described in Table 10.7 (p. 369) are used to add and remove elements of a multimap or multiset
6. Because keys need not be unique, insert always adds an element
7. The version of erase that takes a key removes all elements with that key. It returns a count of how many elements were removed
8. The versions that take an iterator or an iterator pair remove only the indicated element(s).
10.5.1. Adding and Removing Elements
- We noted that maps and sets store their elements in order
- The multimap and multiset types do so as well. As a result, when a multimap or multiset has multiple instances of a given key, those instances will be adjacent elements within the container
- We are guaranteed that iterating across a multimap or multiset returns all the elements with a given key in sequence
10.5.2. Finding Elements in a multimap or multiset
- It turns out that there are three strategies we might use to find and print all the books by a given author. Each of these strategies relies on the fact that we know that all the entries for a given author will be adjacent within the multimap
Using find and count

A Different, Iterator-Oriented Solution

They can be used with (plain) maps or sets but are most often used with multimaps or multisets. Each of these operations takes a key and returns an iterator
Calling lower_bound and upper_bound on the same key yields an iterator range (Section 9.2.1, p. 314) that denotes all the elements with that key. If the key is in the container, the iterators will differ: the one returned from lower_bound will refer to the first instance of the key, whereas upper_bound will return an iterator referring just after the last instance. If the element is not in the multimap, then lower_bound and upper_bound will return equal iterators; both will refer to the point at which the key could be inserted without disrupting the order
The iterator returned from lower_bound may or may not refer to an element with the given key. If the key is not in the container, then lower_bound refers to the first point at which this key could be inserted while preserving the element order within the container
These operations say nothing about whether the key is present. The important point is that the return values act like an iterator range

If there is no element for this key, then lower_bound and upper_bound will be equal: They will both refer to the same element or they will both point one past the end of the multimap. They both will refer to the point at which this key could be inserted while maintaining the container order

Table 10.8. Associative Container Operations Returning Iterators
`m.lower_bound(k)`	Returns an iterator to the first element with key not less than `k`.
`m.upper_bound(k)`	Returns an iterator to the first element with key greater than `k`.
`m.equal_range(k)`	Returns a `pair` of iterators. The `first` member is equivalent to `m.lower_bound(k)` and `second` is equivalent to `m.upper_bound(k)`.

The equal_range Function
- Instead of calling upper_bound and lower_bound, we can call equal_range. This function returns a pair of iterators. If the value is present, then the first iterator refers to the first instance of the key and the second iterator refers one past the last instance of the key. If no matching element is found, then both the first and second iterator refer to the position where this key could be inserted

Section 10.6 Using Containers: Text-Query Program

To conclude this chapter, we'll implement a simple text-query program
10.6.1. Design of the Query Program
1. A good way to start the design of a program is to list the program's operations. Knowing what operations we need to provide can then help us see what data structures we'll need and how we might implement those actions
  1. It must allow the user to indicate the name of a file to process. The program will store the contents of the file so that we can display the original line in which each word appears
  2. The program must break each line into words and remember all the lines in which each word appears. When it prints the line numbers, they should be presented in ascending order and contain no duplicates
  3. The result of querying for a particular word should be the line numbers on which that word appeared
  4. To print the text in which the word appeared, it must be possible to fetch the line from the input file corresponding to a given line number
10.6.2. TextQuery Class
1. Our class will have two data members: a vector to hold the input file and a map to associate each input word with the set of line numbers on which it appears
2. For the reasons described on page 80, this class definition uses fully qualified std:: names for all references to library entities
10.6.3. Using the TextQuery Class
10.6.4. Writing the Member Functions

Monday, January 17, 2011

C++ Primer, Fourth Edition Notes Chapter 18. Specialized Tools and Techniques

Section 18.1 Optimizing Memory Allocation

Section 18.2 Run-Time Type Identification

Section 18.3 Pointer to Class Member

Section 18.4 Nested Classes

Section 18.5 Union: A Space-Saving Class

Section 18.6 Local Classes

Section 18.7 Inherently Nonportable Features

C++ Primer, Fourth Edition Notes Chapter 17. Tools for Large Programs

Part V covers additional features that, although useful in the right context, are not needed by every C++ programmer. These features divide into two clusters: those that are useful for large-scale problems and those that are applicable to specialized problems rather than general ones.

Section 17.1 Exception Handling

Section 17.2 Namespaces

Section 17.3 Multiple and Virtual Inheritance

C++ Primer, Fourth Edition Notes Chapter 15. Object-Oriented Programming

Writing our own object-oriented or generic types requires a fairly good understanding of C++. Fortunately, we can use OO and generic types without understanding the details of how to build them. In fact, the standard library uses the facilities we'll study in Chapters 15 and 16 extensively, and we've used the library types and algorithms without needing to know how they are implemented. Readers, therefore, should understand that Part IV covers advanced topics. Writing templates or object-oriented classes requires a good understanding of the basics of C++ and a good grasp of how to define more basic classes

Section 15.1 OOP: An Overview

Section 15.2 Defining Base and Derived Classes

Section 15.3 Conversions and Inheritance

Section 15.4 Constructors and Copy Control

Section 15.5 Class Scope under Inheritance

Section 15.6 Pure Virtual Functions

Section 15.7 Containers and Inheritance

Section 15.8 Handle Classes and Inheritance

Section 15.9 Text Queries Revisited

Reading Plan

Reading plan

C++ primer

C++ - Data Structures And Algorithms With Object-oriented Design Patterns In C++3.Pratical Algorithms

Windows via C/C++, Fifth Edition

Practical.Algorithms.for.Programmers

Writing Secure Code

Programming.Pearls

Mastering Algorithms with C

Algorithms in a Nutshell

C++ Reserved or Non-graphic Characters

Character	ASCII Representation	ASCII Value	Escape Sequence
Newline	NL (LF)	10	\n
Horizontal tab	HT	9	\t
Vertical tab	VT	11	\v
Backspace	BS	8	\b
Carriage return	CR	13	\r
Formfeed	FF	12	\f
Alert	BEL	7	\a
Backslash	\	92	\\
Question mark	?	63	\?
Single quotation mark	'	39	\'
Double quotation mark	"	34	\"
Octal number	ooo	--	\ooo
Hexadecimal number	hhh	--	\xhhh
Null character	NUL	0	\0

Pro.ASP.NET.4.in.CSharp.2010.4th-Introducing ASP.NET

The Seven Pillars of ASP.NET

ASP.NET Is Integrated with the .NET Framework
ASP.NET Is Compiled, Not Interpreted
ASP.NET Is Multilanguage
ASP.NET Is Hosted by the Common Language Runtime
ASP.NET Is Object-Oriented
ASP.NET Supports all Browser
ASP.NET Is Easy to Deploy and Configure

The Evolution of ASP.NET

ASP.NET 1.0 and 1.1
ASP.NET 2.0
ASP.NET 3.5
LINQ
ASP.NET AJAX
ASP.NET 4
ASP.NET MVC
ASP.NET Dynamic Data
Silverlight

Visual Studio

Web Forms

Server Controls

ASP.NET Applications

State Management

Algorithms in a Nutshell-Note:Chapter 1: Algorithms Matter

It’s the question that drives us, Neo. It’s the question that brought you here.You know the question, just as I did.

We intend this book to be used frequently by experienced programmers looking for appropriate solutions to their problems. Here you will find solutions to the problems you must overcome as a programmer every day. You will learn what decisions lead to an improved performance of key algorithms that are essential for the success of your software applications. You will find real code that can be adapted to your needs and solution methods that you can learn.

C++ Primer, Fourth Edition Notes Chapter 9 Exercise

Exercise 9.1:

Explain the following initializations. Indicate if any are in error, and if so, why.

     int ia[7] = { 0, 1, 1, 2, 3, 5, 8 };
     string sa[6] = {
         "Fort Sumter", "Manassas", "Perryville",
         "Vicksburg", "Meridian", "Chancellorsville" };
     (a) vector<string> svec(sa, sa+6);
     (b) list<int> ilist( ia+4, ia+6);
     (c) vector<int> ivec(ia, ia+8);
     (d) list<string> slist(sa+6, sa);

Exercise 9.2:

Show an example of each of the four ways to create and initialize a vector. Explain what values each vector contains.

Exercise 9.3:

Explain the differences between the constructor that takes a container to copy and the constructor that takes two iterators.

Exercise 9.4:

Define a list that holds elements that are deques that hold ints.

Exercise 9.5:

Why can we not have containers that hold iostream objects?

Exercise 9.6:

Given a class type named Foo that does not define a default constructor but does define a constructor that takes int values, define a list of Foo that holds 10 elements.

Exercise 9.7:

What is wrong with the following program? How might you correct it?

     list<int> lst1;
     list<int>::iterator iter1 = lst1.begin(),
                         iter2 = lst1.end();
     while (iter1 < iter2) /* . . . */

Exercise 9.8:

Assuming vec_iter is bound to an element in a vector that holds strings, what does this statement do?

     if (vec_iter->empty()) /* . . . */

Exercise 9.9:

Write a loop to write the elements of a list in reverse order.

Exercise 9.10:

Which, if any, of the following iterator uses are in error?

     const vector< int > ivec(10);
     vector< string >    svec(10);
     list< int >         ilist(10);

     (a) vector<int>::iterator    it = ivec.begin();
     (b) list<int>::iterator      it = ilist.begin()+2;
     (c) vector<string>::iterator it = &svec[0];
     (d) for (vector<string>::iterator
                  it = svec.begin(); it != 0; ++it)
                     // ...

Exercise 9.11:

What are the constraints on the iterators that form iterator ranges?

Exercise 9.12:

Write a function that takes a pair of iterators and an int value. Look for that value in the range and return a bool indicating whether it was found.

Exercise 9.13:

Rewrite the program that finds a value to return an iterator that refers to the element. Be sure your function works correctly if the element does not exist.

Exercise 9.14:

Using iterators, write a program to read a sequence of strings from the standard input into a vector. Print the elements in the vector.

Exercise 9.15:

Rewrite the program from the previous exercise to use a list. List the changes you needed to change the container type.

Exercise 9.16:

What type should be used as the index into a vector of ints?

Exercise 9.17:

What type should be used to read the elments in a list of strings?

Exercise 9.18:

Write a program to copy elements from a list of ints into two deques. The list elements that are even should go into one deque and those that are odd into the second.

Exercise 9.19:

Assuming iv is a vector of ints, what is wrong with the following program? How might you correct the problem(s)?

     vector<int>::iterator mid = iv.begin() + iv.size()/2;
     while (vector<int>::iterator iter != mid)
         if (iter == some_val)
             iv.insert(iter, 2 * some_val);

Exercise 9.20:

Write a program to compare whether a vector<int> contains the same elements as a list<int>.

Exercise 9.21:

Assuming c1 and c2 are containers, what constraints does the following usage place on the element types in c1 and c2?

     if (c1 < c2)

What, if any, constraints are there on c1 and c2?

Exercise 9.22:

Given that vec holds 25 elements, what does vec.resize(100) do? What if we next wrote vec.resize(10)?

Exercise 9.23:

What, if any, restrictions does using resize with a single size argument place on the element types?

Exercise 9.24:
Write a program that fetches the first element in a vector. Do so using at, the subscript operator, front, and begin. Test the program on an empty vector.

Exercise 9.25:

What happens in the program that erased a range of elements if val1 is equal to val2. What happens if either val1 or val2 or both are not present.

Exercise 9.26:

Using the following definition of ia, copy ia into a vector and into a list. Use the single iterator form of erase to remove the elements with odd values from your list and the even values from your vector.

     int ia[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 89 };

Exercise 9.27:

Write a program to process a list of strings. Look for a particular value and, if found, remove it. Repeat the program using a deque.

Exercise 9.28:

Write a program to assign the elements from a list of char* pointers to C-style character strings to a vector of strings.

Exercise 9.29:
Explain the difference between a vector's capacity and its size. Why is it necessary to support the notion of capacity in a container that stores elements contiguously but not, for example, in a list?
Exercise 9.30:
Write a program to explore the allocation stragegy followed by the library you use for vector objects.
Exercise 9.31:
Can a container have a capacity less than its size? Is a capacity equal to its size desirable? Initially? After an element is inserted? Why or why not?
Exercise 9.32:
Explain what the following program does:
     vector<string> svec;
     svec.reserve(1024);
     string text_word;
     while (cin >> text_word)
             svec.push_back(text_word);
     svec.resize(svec.size()+svec.size()/2);
If the program reads 256 words, what is its likely capacity after it is resized? What if it reads 512? 1,000? 1,048?

Exercise 9.33:

Which is the most appropriatea vector, a deque, or a listfor the following program tasks? Explain the rationale for your choice. If there is no reason to prefer one or another container explain why not?

Read an unknown number of words from a file for the purpose of generating English language sentences.
Read a fixed number of words, inserting them in the container alphabetically as they are entered. We'll see in the next chapter that associative containers are better suited to this problem.
Read an unknown number of words. Always insert new words at the back. Remove the next value from the front.
Read an unknown number of integers from a file. Sort the numbers and then print them to standard output.

Exercise 9.34:

Use iterators to change the characters in a string to uppercase.

Exercise 9.35:

Use iterators to find and to erase each capital letter from a string.

Exercise 9.36:

Write a program that initializes a string from a vector<char>.

Exercise 9.37:

Given that you want to read a character at a time into a string, and you know that the data you need to read is at least 100 characters long, how might you improve the performance of your program?

Exercise 9.38:

Write a program that, given the string

     "ab2c3d7R4E6"

finds each numeric character and then each alphabetic character. Write two versions of the program. The first should use find_first_of, and the second find_first_not_of.

Exercise 9.39:

Write a program that, given the strings

     string line1 = "We were her pride of 10 she named us:";
     string line2 = "Benjamin, Phoenix, the Prodigal"
     string line3 = "and perspicacious pacific Suzanne";

     string sentence = line1 + ' ' + line2 + ' ' + line3;

counts the number of words in sentence and identifies the largest and smallest words. If several words have the largest or smallest length, report all of them.

Exercise 9.40:

Write a program that accepts the following two strings:

     string q1("When lilacs last in the dooryard bloom'd");
     string q2("The child is father of the man");

Using the assign and append operations, create the string

     string sentence("The child is in the dooryard");

Exercise 9.41:

Write a program that, given the strings

     string generic1("Dear Ms Daisy:");
     string generic2("MrsMsMissPeople");

implements the function

     string greet(string form, string lastname, string title,
                  string::size_type pos, int length);

using the replace operations, where lastname replaces Daisy and pos indexes into generic2 of length characters replacing Ms. For example, the following

     string lastName("AnnaP");
     string salute = greet(generic1, lastName, generic2, 5, 4);

returns the string

     Dear Miss AnnaP:

Exercise 9.42:

Write a program to read a series of words into a stack.

Exercise 9.43:

Use a stack to process parenthesized expressions. When you see an open parenthesis, note that it was seen. When you see a close parenthesis after an open parenthesis, pop elements down to and including the open parenthesis off the stack. push a value onto the stack to indicate that a parenthesized expression was replaced

C++ Primer, Fourth Edition Notes Chapter 9 Sequential Containers

We've said that C++ is about efficient programming with abstractions. The Standard Library is a good example: The library defines a number of container classes and a family of generic algorithms that let us write programs that are succinct, abstract, and efficient. The library worries about bookkeeping detailsin particular, taking care of memory managementso that our programs can worry about the actual problems we need to solve

The library is designed so that the container types provide a common interface: If two containers offer a similar operation, then that operation will be defined identically for both containers

Because the container operations and algorithms are defined consistently, learning the library becomes easier: Once you understand how an operation works, you can apply that same operation to other containers. More importantly, this commonality of interface leads to more flexible programs. It is often possible to take a program written to use one container type and change it to use a different container without having to rewrite code. As we'll see, the containers offer different performance tradeoffs, and the ability to change container types can be valuable when fine-tuning the performance of a system

Each container type offers a different set of time and functionality tradeoffs.

The library defines three kinds of sequential containers: vector, list, and deque (short for "double-ended queue" and pronounced "deck"). These types differ in how elements are accessed and the relative run-time cost of adding or removing element. The library also provides three container adaptors. Effectively, an adaptor adapts an underlying container type by defining a new interface in terms of the operations provided by the original type. The sequential container adaptors are stack, queue, and priority_queue.

Table 9.1. Sequential Container Types
Sequential Containers
`vector`	Supports fast random access
`list`	Supports fast insertion/deletion
`deque`	Double-ended queue
Sequential Container Adaptors
`stack`	Last in/First out stack
`queue`	First in/First out queue
`priority_queue`	Priority-managed queue

Section 9.1 Defining a Sequential Container

For reasons that shall become clear shortly, the most commonly used container constructor is the default constructor. In most programs, using the default constructor gives the best run-time performance and makes using the container easier.

9.1.1. Initializing Container Elements

Table 9.2. Container Constructors
`C<T> c;`	Create an empty container named `c`. `C` is a container name, such as `vector`, and `T` is the element type, such as `int` or `string`. Valid for all containers.
`C c(c2);`	Create `c` as a copy of container `c2`; `c` and `c2` must be the same container type and hold values of the same type. Valid for all containers.
`C c(b, e);`	Create `c` with a copy of the elements from the range denoted by iterators `b` and `e`. Valid for all containers.
`C c(n, t);`	Create `c` with `n` elements, each with value `t`, which must be a value of the element type of `C` or a type convertible to that type. Sequential containers only.
`C c(n);`	Create `c` with `n` value-initialized (Section 3.3.1, p. 92) elements. Sequential containers only.

Intializing a Container as a Copy of Another Container
1. When we initialize a sequential container using any constructor other than the default constructor, we must indicate how many elements the container will have. We must also supply initial values for those elements
2. When we copy one container into another, the types must match exactly: The container type and element type must be the same
Initializing as a Copy of a Range of Elements
1. Although we cannot copy the elements from one kind of container to another directly, we can do so indirectly by passing a pair of iterators (Section 3.4, p. 95). When we use iterators, there is no requirement that the container types be identical. The element types in the containers can differ as long as they are compatible. It must be possible to convert the element we copy into the type held by the container we are constructing
2. The iterators denote a range of elements that we want to copy. These elements are used to initialize the elements of the new container. The iterators mark the first and one past the last element to be copied. We can use this form of initialization to copy a container that we could not copy directly. More importantly, we can use it to copy only a subsequence of the other container
3. Recall that pointers are iterators, so it should not be surprising that we can initialize a container from a pair of pointers into a built-in array
Allocating and Initializing a Specified Number of Elements
2. The constructors that take a size are valid only for sequential containers; they are not supported for the associative containers

9.1.2. Constraints on Types that a Container Can Hold
1. Most types meet these minimal element type requirements. All of the built-in or compound types, with the exception of references, can be used as the element type
2. References do not support assignment in its ordinary meaning, so we cannot have containers of references
3. With the exception of the IO library types (and the auto_ptr type, which we cover in Section 17.1.9 (p. 702)), all the library types are valid container element types
4. The IO library types do not support copy or assignment. Therefore, we cannot have a container that holds objects of the IO types
5. Container Operations May Impose Additional Requirements
  1. In addition, some container operations impose additional requirements on the element type. If the element type doesn't support the additional requirement, then we cannot perform that operation: We can define a container of that type but may not use that particular operation
6. Containers of Containers
  1. Note the spacing used when specifying a container element type as a container
  2. We must separate the two closing > symbols with a space to indicate that these two characters represent two symbols. Without the space, >> is treated as a single symbol, the right shift operator, and results in a compile-time error

// EXE-9.1.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <list>
#include <deque>
#include <string>
#include <iostream>

using namespace std;
class Foo
{
public:
	Foo( int size)
	{
		this->size = size;
	}
	Foo():size(0){};
	void Foo::PrintOut();
protected:
private:
	int size;
};
int main(int argc, _TCHAR* argv[])
{
	vector<string>    svec;       // empty vector that can hold strings
	list<int>         ilist;      // empty list that can hold ints
	//deque<Sales_item> items;      // empty deque that holds Sales_items


	if("Intializing a Container as a Copy of Another Container")
	{
		vector<int> ivec;
		vector<int> ivec2(ivec);   // ok: ivec is vector<int>
		//list<int>   ilist(ivec);   // error: ivec is not list<int>
		//vector<double> dvec(ivec); // error: ivec holds int not double
		
	}
	if("Initializing as a Copy of a Range of Elements")
	{
		vector<string> svec(10,"*");
		vector<string>::iterator it = svec.begin();
		while(it != svec.end())
		{
			cout << *it++ << endl;
		}
		// initialize slist with copy of each element of svec
		list<string> slist(svec.begin(), svec.end());

		cout << "The list size is:" << slist.size() << endl;
		// find midpoint in the vector
		vector<string>::iterator mid = svec.begin() + svec.size()/2;

		// initialize front with first half of svec: The elements up to but not including *mid
		deque<string> front(svec.begin(), mid);
		cout << "The deque is copied from begin to mid and its size is:" << front.size() << endl;
		// initialize back with second half of svec: The elements *mid through end of svec
		deque<string> back(mid, svec.end());
		cout << "The deque is copied from mid to end and its size is:" << back.size() << endl;

		char *words[] = {"stately", "plump", "buck", "mulligan","a","ab"};

		// calculate how many elements in words
		// to get the size of the string array
		size_t words_size = sizeof(words)/sizeof(char *);

		// use entire array to initialize words2
		list<string> words2(words, words + words_size);
		list<string>::iterator itL = words2.begin();
		while( itL != words2.end())
		{
			cout << *itL++ << endl;
		}

	}

	if("Allocating and Initializing a Specified Number of Elements")
	{
		const list<int>::size_type list_size = 64;
		list<string> slist(list_size, "eh?"); // 64 strings, each is eh?
		list<string>::iterator it_slist = slist.begin();
		while(it_slist != slist.end())
			cout << *it_slist ++ ;
		cout << endl;
		
		list<int> ilist(list_size); // 64 elements, each initialized to 0
		list<int>::iterator it_ilist = ilist.begin();
		while( it_ilist != ilist.end())
			cout << *it_ilist++ ;
		cout << endl;

		// svec has as many elements as the return value from get_word_count
		extern unsigned get_word_count(const string &file_name);
		vector<string> svec(get_word_count("Chimera"));
		vector<string>::iterator it_svec = svec.begin();
		while( it_svec != svec.end())
			cout << *it_svec ++ ;
		cout << endl;

	}
	if("Container Operations May Impose Additional Requirements")
	{
		vector<Foo> empty;     // ok: no need for element default constructor
		vector<Foo> bad(10);   // it's ok to call now with the default constructor // error: no default constructor for Foo
		vector<Foo> ok(10, 1); // ok: each element initialized to 1
		vector<Foo>::iterator it = ok.begin();
		while( it != ok.end())
		{
			it->PrintOut();
			++it;
		}
	}
	if("Containers of Containers")
	{
		// note spacing: use ">>" not ">>" when specifying a container element type
		vector< vector<string> > lines0; // vector of vectors
		vector< vector<string> > lines1; // ok: space required between close >
		// actually not comple error in VSTS 2010
		vector<vector<string>> lines2; // error: >> treated as shift operator

	}

	int i;
	cin >> i;

	return 0;
}

unsigned get_word_count(const string &file_name)
{
	return file_name.size();
}
inline void Foo::PrintOut()
{
	cout << "The fool's size is:" << this->size << endl;
}

Section 9.2 Iterators and Iterator Ranges

Table 9.3. Common Iterator Operations
`*iter`	Return a reference to the element referred to by the iterator `iter`.
`iter->mem`	Dereference `iter` and fetch the member named `mem` from the underlying element. Equivalent to `(*iter).mem`.
`++iter iter++`	Increment `iter` to refer to the next element in the container.
`--iter iter--`	Decrement `iter` to refer to the previous element in the container.
`iter1 == iter2 iter1 != iter2`	Compare two iterators for equality (inequality). Two iterators are equal if they refer to the same element of the same container or if they are the off-the-end iterator (Section 3.4, p. 97) for the same container.

Iterators on vector and deque Support Additional Operations

There are two important sets of operations that only vector and deque support: iterator arithmetic (Section 3.4.1, p. 100) and the use of the relational operators (in addition to == and !=) to compare two iterators

Table 9.4. Operations Supported by `vector` and `deque` Iterators
`iter + n iter - n`	Adding (subtracting) an integral value `n` to (from) an iterator yields an iterator that many elements forward (backward) within the container. The resulting iterator must refer to an element in the container or one past the end of the container.
`iter1 += iter2 iter1 -= iter2`	Compound-assignment versions of iterator addition and subtraction. Assigns the value of adding or subtracting `iter1` and `iter2` into `iter1`.
`iter1 - iter2`	Subtracting two iterators yields the number that when added to the right-hand iterator yields the left-hand iterator. The iterators must refer to elements in the same container or one past the end of the container. Supported only for `vector` and `deque`.
`>, >=, <, <=`	Relational operators on iterators. One iterator is less than another if it refers to an element whose position in the container is ahead of the one referred to by the other iterator. The iterators must refer to elements in the same container or one past the end of the container. Supported only for `vector` and `deque`.

The reason that only vector and deque support the relational operators is that only vector and deque offer fast, random access to their elements

9.2.1. Iterator Ranges

The concept of an iterator range is fundamental to the standard library.
An iterator range is denoted by a pair of iterators that refer to two elements, or to one past the last element, in the same container. These two iterators, often referred to as first and last, or beg and end, mark a range of elements from the container.
The second iterator never refers to the last element of the range. Instead, it refers to a point one past the last element. The elements in the range include the element referred to by first and every element from first tHRough the element just before last. If the iterators are equal, then the range is empty

This element range is called a left-inclusive interval

Requirements on Iterators Forming an Iterator Range

Two iterators, first and last, form an iterator range, if

They refer to elements of, or one-past-the-end of, the same container.
If the iterators are not equal, then it must be possible to reach last by repeatedly incrementing first. In other words, last must not precede first in the container.

The compiler cannot itself enforce these requirements. It does not know to which container an iterator is bound, nor does it know how many elements are in a container. Failing to meet these requirements results in undefined run-time behavior
Programming Implications of Using Left-Inclusive Ranges

9.2.2. Some Container Operations Invalidate Iterators
1. In the sections that follow, we'll see that some container operations change the internal state of a container or cause the elements in the container to be moved. Such operations invalidate all iterators that refer to the elements that are moved and may invalidate other iterators as well. Using an invalidated iterator is undefined, and likely to lead to the same kinds of problems as using a dangling pointer
2. When writing programs that use iterators, we must be aware of which operations can invalidate the iterators. It is a serious run-time error to use an iterator that has been invalidated
3. There is no way to examine an iterator to determine whether it has been invalidated. There is no test we can perform to detect that it has gone bad. Any use of an invalidated iterator is likely to yield a run-time error, but there is no guarantee that the program will crash or otherwise make it easy to detect the problem
4. When using iterators, it is usually possible to write the program so that the range of code over which an iterator must stay valid is relatively short. It is important to examine each statement in this range to determine whether elements are added or removed and adjust iterator values accordingly

Section 9.3 Sequence Container Operations

Each sequential container defines a set of useful typedefs and supports operations that let us

Add elements to the container
Delete elements from the container
Determine the size of the container
Fetch the first and last elements from the container, if any

9.3.1. Container Typedefs

Table 9.5. Container-Defined Typedefs
`size_type`	Unsigned integral type large enough to hold size of largest possible container of this container type
`iterator`	Type of the iterator for this container type
`const_iterator`	Type of the iterator that can read but not write the elements
`reverse_iterator`	Iterator that addresses elements in reverse order
`const_reverse_iterator`	Reverse iterator that can read but not write the elements
`difference_type`	Signed integral type large enough to hold the difference, which might be negative, between two iterators
`value_type`	Element type
`reference`	Element's lvalue type; synonym for `value_type&`
`const_reference`	Element's const lvalue type; same as `const value_type&`

9.3.2. begin and end Members

The begin and end operations yield iterators that refer to the first and one past the last element in the container.

Table 9.6. Container `begin` and `end` Operations
`c.begin()`	Yields an iterator referring to the first element in `c`
`c.end()`	Yields an iterator referring to the one past the last element in `c`
`c.rbegin()`	Yields a reverse iterator referring to the last element in `c`
`c.rend()`	Yields a reverse iterator referring one past (i.e., before) the first element in `c`

9.3.3. Adding Elements to a Sequential Container

Every sequential container supports push_back, which appends an element to the back of the container
The call to push_back creates a new element at the end of container, increasing the size of container by one. The value of that element is a copy of text_word. The type of container can be any of list, vector, or deque

In addition to push_back, the list and deque containers support an analogous operation named push_front. This operation inserts a new element at the front of the container

Key Concept: Container Elements Are Copies

When we add an element to a container, we do so by copying the element value into the container. Similarly, when we initialize a container by providing a range of elements, the new container contains copies of the original range of elements. There is no relationship between the element in the container and the value from which it was copied. Subsequent changes to the element in the container have no effect on the value that was copied, and vice versa.

Table 9.7. Operations that Add Elements to a Sequential Container
`c.push_back(t)`	Adds element with value `t` to the end of `c`. Returns `void`.
`c.push_front(t)`	Adds element with value `t` to front of `c`. Returns `void`. Valid only for `list` or `deque`.
`c.insert(p,t)`	Inserts element with value `t` before the element referred to by iterator `p`. Returns an iterator referring to the element that was added.
`c.insert(p,n,t)`	Inserts `n` elements with value `t` before the element referred to by iterator `p`. Returns `void`.
`c.insert(p,b,e)`	Inserts elements in the range denoted by iterators `b` and `e` before the element referred to by iterator `p`. Returns `void`.

Adding Elements at a Specified Point in the Container
Inserting a Range of Elements
Inserting Elements Can Invalidate Iterators
1. As we'll see in Section 9.4 (p. 330), adding elements to a vector can cause the entire container to be relocated. If the container is relocated, then all iterators into the container are invalidated. Even if the vector does not have to be relocated, any iterator to an element after the one inserted is invalidated
2. Iterators may be invalidated after doing any insert or push operation on a vector or deque. When writing loops that insert elements into a vector or a deque, the program must ensure that the iterator is refreshed on each trip through the loop
Avoid Storing the Iterator Returned from end
1. When we add elements to a vector or deque, some or all of the iterators may be invalidated. It is safest to assume that all iterators are invalid. This advice is particularly true for the iterator returned by end. That iterator is always invalidated by any insertion anywhere in the container
2. Don't cache the iterator returned from end. Inserting or deleting elements in a deque or vector will invalidate the cached iterator

9.3.4. Relational Operators
1. The containers must be the same kind of container and must hold elements of the same type
2. Comparing two containers is based on a pairwise comparison of the elements of the containers. The comparison uses the same relational operator as defined by the element type: Comparing two containers using != uses the != operator for the element type
  These operators work similarly to the string relationals (Section 3.2.3, p. 85):
  - If both containers are the same size and all the elements are equal, then the two containers are equal; otherwise, they are unequal.
  - If the containers have different sizes but every element of the shorter one is equal to the corresponding element of the longer one, then the shorter one is considered to be less than the other.
  - If neither container is an initial subsequence of the other, then the comparison depends on comparing the first unequal elements
3. Relational Operators Use Their Element's Relational Operator
  1. We can compare two containers only if the same relational operator defined for the element types

9.3.5. Container Size Operations

Table 9.8. Sequential Container Size Operations
`c.size()`	Returns the number of elements in `c`. Return type is `c::size_type`.
`c.max_size()`	Returns maximum number of elements `c` can contain. Return type is `c::size_type`.
`c.empty()`	Returns a `bool` that indicates whether `size` is 0 or not.
`c.resize(n)`	Resize `c` so that it has `n` elements. If `N < c.size()`, the excess elements are discarded. If new elements must be added, they are value initialized.
`c.resize(n,t)`	Resize `c` to have `n` elements. Any elements added have value `t`.

resize can invalidate iterators. A resize operation on a vector or deque potentially invalidates all iterators
For any container type, if resize shrinks the container, then any iterator to an element that is deleted is invalidated

9.3.6. Accessing Elements

If a container is not empty, then the front and back members return references bound to the first or last elements in the container

Table 9.9. Operations to Access Elements in a Sequential Container
`c.back()`	Returns a reference to the last element in `c`. Undefined if `c` is empty.
`c.front()`	Returns a reference to the first element in `c`. Undefined if `c` is empty.
`c[n]`	Returns a reference to the element indexed by `n`. Undefined if `n <0` or `n >= c.size()`. Valid only for `vector` and `deque`.
`c.at(n)`	Returns a reference to the element indexed by `n`. If index is out of range, throws `out_of_range` exception. Valid only for `vector` and `deque`.

This program uses two different approaches to fetch a reference to the first and last elements in ilist. The direct approach is to call front or back. Indirectly, we can obtain a reference to the same element by dereferencing the iterator returned by begin or the element one before the iterator returned by end. Two things are noteworthy in this program: The end iterator refers "one past the end" of the container so to fetch the last element we must first decrement that iterator. The other important point is that before calling front or back or dereferencing the iterators from begin or end we check that ilist isn't empty. If the list were empty all of the operations in the if would be undefined
```
            // check that there are elements before dereferencing an iterator
		// or calling front or back
		list<int> ilist;
		if (!ilist.empty()) {
			// val and val2 refer to the same element
			list<int>::reference val = *ilist.begin();
			list<int>::reference val2 = ilist.front();

			// last and last2 refer to the same element
			list<int>::reference last = *--ilist.end();
			list<int>::reference last2 = ilist.back(); 
		}
```
When we introduced subscripting in Section 3.3.2 (p. 94), we noted that the programmer must ensure that an element exists at the indicated subscript location. The subscript operator itself does not check. The same caution applies to using the front or back operations. If the container is empty, these operations yield an undefined result
Using a subscript that is out-of-range or calling front or back on an empty container are serious programming errors
An alternative to subscripting is to use the at member. This function acts like the subscript operation but if the index is invalid, at throws an out_of_range exception

9.3.7. Erasing Elements

specific push_front and push_back operations to add elements only at the front or back. Similarly, there is a general erase and specific pop_front and pop_back operations to remove elements

Removing the First or Last Element

The pop_front and pop_back functions remove the first and last elements in the container. There is no pop_front operation for vectors.These operations remove the indicated element and return void

The pop_front and pop_back return void; they do not return the value of the element popped. To examine that value, it is necessary to call front or back prior to popping the element

Table 9.10. Operations to Remove Elements from a Sequential Container
`c.erase(p)`	Removes element referred to by the iterator `p`. Returns an iterator referring to the element after the one deleted, or an off-the-end iterator if `p` referred to the last element. Undefined if `p` is an off-the-end iterator.
`c.erase(b,e)`	Removes the range of elements denoted by the iterators `b` and `e`. Returns an iterator referring after the last one in the range that was deleted, or an off-the-end iterator if `e` is itself an off-the-end iterator.
`c.clear()`	Removes all the elements in `c`. Returns `void`.
`c.pop_back()`	Removes the last element in `c`. Returns `void`. Undefined if `c` is empty.
`c.pop_front()`	Removes the first element in `c`. Returns `void`. Undefined if `c` is empty. Valid only for `list` or `deque`.

Removing an Element From within the Container
1. The more general way to remove an element, or range of elements, is through erase.
2. As usual, the erase operations don't check their argument(s). It is up to the programmer to ensure that the iterator or iterator range is valid
3. The easiest way to find a given element is to use the library find algorithm. We'll see more about find in Section 11.1 (p. 392). To use find or any other generic algorithm, we must include the algorithm header. The find function takes a pair of iterators that denote a range in which to look, and a value to look for within that range. find returns an iterator referring to the first element with that value or the off-the-end iterator
4. Note that we check that the iterator is not the end iterator before erasing the element. When we ask erase to erase a single element, the element must existthe behavior of erase is undefined if we ask it to erase an off-the-end iterator
Removing All the Elements in a Container
1. To delete all the elements in a container, we could either call clear or pass the iterators from begin and end to erase
2. The erase, pop_front, and pop_back functions invalidate any iterators that refer to the removed elements. For vectors, iterators to elements after the erasure point are also invalidated. For deque, if the erase does not include either the first or last element, all iterators into the deque are invalidated

9.3.8. Assignment and swap

The assignment-related operators act on the entire container. Except for swap, they can be expressed in terms of erase and insert operations. The assignment operator erases the entire range of elements in the left-hand container and then inserts the elements of the right-hand container object into the left-hand container
Assignment and the assign operations invalidate all iterators into the left-hand container. swap does not invalidate iterators. After swap, iterators continue to refer to the same elements, although those elements are now in a different container

Using assign

The assign operation deletes all the elements in the container and then inserts new elements as specified by the arguments. Like the constructor that copies elements from a container, the assignment operator (=) can be used to assign one container to another only if the container and element type are the same. If we want to assign elements of a different but compatible element type and/or from a different container type, then we must use the assign operation.

Table 9.11. Sequential Container Assignment Operations
`c1 = c2`	Deletes elements in `c1` and copies elements from `c2` into `c1`. `c1` and `c2` must be the same type.
`c1.swap(c2)`	Swaps contents: After the call `c1` has elements that were in `c2`, and `c2` has elements that were in `c1`. `c1` and `c2` must be the same type. Execution time usually much faster than copying elements from `c2` to `c1`.
`c.assign(b,e)`	Replaces the elements in `c` by those in the range denoted by iterators `b` and `e`. The iterators `b` and `e` must not refer to elements in `c`.
`c.assign(n,t)`	Replaces the elements in `c` by `n` elements with value `t`.

Because the original elements are deleted, the iterators passed to assign must not refer to elements in the container on which assign is called
The assign operator that takes an iterator pair lets us assign elements of one container type to another

Using swap to Avoid the Cost of Deleting Elements
1. The swap operation swaps the values of its two operands. The types of the containers must match: The operands must be the same kind of container, and they must hold values of the same type. After the call to swap, the elements that had been in the right-hand operand are in the left, and vice versa
2. The important thing about swap is that it does not delete or insert any elements and is guaranteed to run in constant time. No elements are moved, and so iterators are not invalidated
3. The fact that elements are not moved means that iterators are not invalidated. They refer to the same elements as they did before the swap. However, after the swap, those elements are in a different container. For example, had iter referred to the string at position svec1[3] before the swap it will refer to the element at position svec2[3] after the swap

// EXE-9.3.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <string>
#include <iostream>
#include <list>
#include <deque>
#include <exception>
#include <cassert>
#include <algorithm>

using namespace std;

void PrintOut(list<string> & l);
void clearstream(istream &in);
void PrintOut(vector<string> &svect);
void PrintOut(list<int> & slst);
void process(const list<int>::reference re);
void PrintOut(vector<int> & ivect);

int main(int argc, _TCHAR* argv[])
{

	if("9.3.1. Container Typedefs")
	{
		// iter is the iterator type defined by list<string>
		list<string>::iterator iter;

		// cnt is the difference_type type defined by vector<int>
		vector<int>::difference_type cnt;

	}

	if("9.3.3. Adding Elements to a Sequential Container")
	{
		// read from standard input putting each word onto the end of container
		deque<string> container;
		string text_word;
		/*while (cin >> text_word)
		container.push_back(text_word);*/

		clearstream(cin);

		list<int> ilist;
		// add elements at the end of ilist
		for (size_t ix = 0; ix != 4; ++ix)
			ilist.push_back(ix);

		// add elements to the start of ilist
		for (size_t ix = 0; ix != 4; ++ix)
			ilist.push_front(ix);


		if("Adding Elements at a Specified Point in the Container")
		{
			vector<string> svec;
			list<string> slist;
			string spouse("Beth");

			// equivalent to calling slist.push_front (spouse);
			slist.insert(slist.begin(), spouse);

			// no push_front on vector but we can insert before begin()
			// warning: inserting anywhere but at the end of a vector is an expensive operation
			svec.insert(svec.begin(), spouse);

			list<string> lst;
			list<string>::iterator iter = lst.begin();
			string word;
			/*while (cin >> text_word)
			container.push_back(text_word);*/

			while (cin >> word)
			{
				iter = lst.insert(iter, word); // same as calling push_front
			}
			clearstream(cin);

			PrintOut(lst);
		}

		if("Inserting a Range of Elements")
		{
			vector<string> svec;
			list<string> slist;

			svec.insert(svec.end(), 10, "Anna");

			PrintOut(svec);

			string sarray[4] = {"quasi", "simba", "frollo", "scar"};
			// insert all the elements in sarray at end of slist
			slist.insert(slist.end(), sarray, sarray+4);
			PrintOut(slist);

			list<string>::iterator slist_iter = slist.begin();
			// insert last two elements of sarray before slist_iter
			slist.insert(slist_iter, sarray+2, sarray+4);
			PrintOut(slist);
		}

		if("Avoid Storing the Iterator Returned from end")
		{
			vector<int> v(1,0);

			vector<int>::iterator first = v.begin(), last = v.end(); // cache end iterator
			// diaster: behavior of this loop is undefined
			//while (first != last) {
			//	// do some processing
			//	// insert new value and reassign first, which otherwise would be invalid
			//	first = v.insert(first, 42);
			//	++first;  // advance first just past the element we added
			//}

			// safer: recalculate end on each trip whenever the loop adds/erases elements
			int k(0);
			while (first != v.end() && k != 42) {
				// do some processing
				first = v.insert(first, ++k); // insert new value
				++first; // advance first just past the element we added
			}
		}

	}

	if("9.3.4. Relational Operators")
	{
		//ivec1: 1 3 5 7 9 12
		int ivec1_array[] = {1,3, 5, 7 ,9 ,12};
		vector<int> ivec1(ivec1_array,ivec1_array + sizeof(ivec1_array)/ sizeof(int));
		//ivec2: 0 2 4 6 8 10 12
		int ivec2_array[] = {0,2,4,6,8,10,12};
		vector<int> ivec2(ivec2_array, ivec2_array + sizeof(ivec2_array)/sizeof(int));
		//ivec3: 1 3 9
		int ivec3_array[] = {1,3,9};
		vector<int> ivec3(ivec3_array,ivec3_array + sizeof(ivec3_array)/sizeof(int));
		//ivec4: 1 3 5 7
		int ivec4_array[] = {1,3,5,7};
		vector<int> ivec4(ivec4_array,ivec4_array + sizeof(ivec4_array)/sizeof(int));
		//ivec5: 1 3 5 7 9 12
		int ivec5_array[] = {1,3,5,7,9,12};
		vector<int> ivec5(ivec5_array,ivec5_array + sizeof(ivec5_array)/sizeof(int));

		// ivec1 and ivec2 differ at element[0]: ivec1 greater than ivec2
		cout << "ivec1 < ivec2 = " << (ivec1 < ivec2) << endl; // false
		cout << "ivec2 < ivec1 = " << (ivec2 < ivec1) << endl; // true

		// ivec1 and ivec3 differ at element[2]: ivec1 less than ivec3
		cout << "ivec1 < ivec3 = " << (ivec1 < ivec3 ) << endl; // true

		// all elements equal, but ivec4 has fewer elements, so ivec1 is greater than ivec4
		cout << "ivec1 < ivec4 = " << (ivec1 < ivec4 )<< endl; // false

		cout << "ivec1 == ivec5 = " << (ivec1 == ivec5 )<< endl; // true; each element equal and same number of elements
		cout << "ivec1 == ivec4 = " << (ivec1 == ivec4 )<< endl; // false; ivec4 has fewer elements than ivec1
		cout << "ivec1 != ivec4 = " << (ivec1 != ivec4 )<< endl; // true; ivec4 has fewer elements than ivec1

	}

	if("9.3.5. Container Size Operations")
	{
		list<int> ilist(10, 42);   // 10 ints: each has value 42
		PrintOut(ilist);
		ilist.resize(15);          // adds 5 elements of value 0 to back of ilist
		PrintOut(ilist);
		ilist.resize(25, -1);      // adds 10 elements of value -1 to back of ilist
		PrintOut(ilist);
		ilist.resize(5);           // erases 20 elements from the back of ilist
		PrintOut(ilist);
	}

	if("9.3.6. Accessing Elements")
	{
		// check that there are elements before dereferencing an iterator
		// or calling front or back
		list<int> ilist;
		int i(10);
		while( i != 0)
			ilist.push_front(--i);

		if (!ilist.empty()) {
			// val and val2 refer to the same element
			list<int>::reference val = *ilist.begin();
			list<int>::reference val2 = ilist.front();
			assert(val == val2);
			// last and last2 refer to the same element
			list<int>::reference last = *--ilist.end();
			list<int>::reference last2 = ilist.back(); 
			assert(last == last2);
		}
		// empty vector
		vector<string> svec;
		//try
		//{
		//	cout << svec[0];         // run-time error: There are no elements in svec!
		//}		
		//catch (runtime_error* e)
		//{
		//	cout << "the index access failed!" << endl;
		//	//goto atmethod;
		//}
		//catch (out_of_range* e)
		//{
		//	cout << "the at method access failed!" << endl;
		//}
		//catch (exception& e)
		//{
		//	cout << e.what()<< endl;
		//}
		//try
		//{
		//	cout << svec.at(0);      // throws out_of_range exception
		//}
		//catch (out_of_range* e)
		//{
		//	// do nothing and only print message
		//	cout << "the at method access failed!" << endl;
		//}
		//catch (exception& e)
		//{
		//	cout << e.what()<< endl;
		//}	

	}
	if("9.3.7. Erasing Elements")
	{
		list<int> ilist;
		int i(10);
		while( i!=0)
			ilist.push_back(--i);

		PrintOut(ilist);
		while (!ilist.empty()) {			
			process(ilist.front()); // do something with the current top of ilist
			ilist.pop_front();      // done; remove first element
			PrintOut(ilist);
		}

		if("Removing an Element From within the Container")
		{
			char * words[] = {"a","b","c","d","e","f","Quasimodo","g","Quasimodo","h"};
			list<string> slist(words, words + sizeof(words)/sizeof(char *));
			PrintOut(slist);

			string searchValue("Quasimodo");
			list<string>::iterator iter;
			while( iter = find(slist.begin(), slist.end(), searchValue),iter != slist.end())
			{
				slist.erase(iter);
				PrintOut(slist);
			}

		}

		if("Removing All the Elements in a Container")
		{
			char * words[] = {"a","b","c","d","e","f","Quasimodo","g","Quasimodo","h"};
			list<string> slist(words, words + sizeof(words)/sizeof(char *));
			PrintOut(slist);
			slist.clear(); // delete all the elements within the container
			PrintOut(slist);
			slist.erase(slist.begin(), slist.end()); // equivalent

		}

	}

	if("9.3.8. Assignment and swap")
	{
		vector<int> ivect1(10,1);
		PrintOut(ivect1);
		vector<int> ivect2(20,2);
		PrintOut(ivect2);

		ivect1 = ivect2; // replace contents of c1 with a copy of elements in ivect2
		// equivalent operation using erase and insert
		ivect1.erase(ivect1.begin(), ivect1.end()); // delete all elements in c1
		ivect1.insert(ivect1.begin(), ivect2.begin(), ivect2.end()); // insert ivect2

		if("Using assign")
		{
			list<string> slist1(10,"1");
			list<string> slist2(20,"2");
			PrintOut(slist1);
			PrintOut(slist2);
			// equivalent to slist1 = slist2
			slist1.assign(slist2.begin(), slist2.end());
			PrintOut(slist1);

			// equivalent to: slist1.clear();
			// followed by slist1.insert(slist1.begin(), 10, "Hiya!");
			slist1.assign(10, "Hiya!"); // 10 elements; each one is Hiya!
			PrintOut(slist1);

		}
		if("Using swap to Avoid the Cost of Deleting Elements")
		{
			vector<string> svec1(10,"1"); // vector with 10 elements
			vector<string> svec2(24,"2"); // vector with 24 elements
			vector<string>::iterator it_svec1 = svec1.begin() + 2;
			vector<string>::iterator it_svec2 = svec2.begin() + 3;
			assert(it_svec1 == svec1.begin()  + 2 );
			assert(it_svec2 == svec2.begin() + 3 );
			PrintOut(svec1);
			PrintOut(svec2);
			svec1.swap(svec2);
			assert(it_svec1 == svec2.begin()  + 2 );
			assert(it_svec2 == svec1.begin() + 3 );
			PrintOut(svec1);
			PrintOut(svec2);

		}

	}
	int i;
	cin >> i;
	return 0;
}
void process(const list<int>::reference re)
{
	// print out value
	cout << re << endl;
}
void clearstream(istream &in)
{
	//in.clear(istream::goodbit);
	//in.clear(istream::eofbit);
	in.clear();
	//in.seekg(0,ios_base::beg);
	in.seekg(0);
}
void PrintOut(list<string> & slst)
{
	string a(30,'*');
	cout << a << endl;
	cout << "list size:" << slst.size() << " element: ";

	list<string>::iterator it = slst.begin();
	while( it != slst.end())
		cout << *it++ << ", " ;

	cout << endl;
}
void PrintOut(vector<int> & ivect)
{
	string a(30,'*');
	cout << a << endl;
	cout << "vector size:" << ivect.size() << " element: ";

	vector<int>::iterator it = ivect.begin();
	while( it != ivect.end())
		cout << *it++ << ", " ;

	cout << endl;
}
void PrintOut(list<int> & ilst)
{
	string a(30,'*');
	cout << a << endl;
	cout << "list size:" << ilst.size() << " element: ";

	list<int>::iterator it = ilst.begin();
	while( it != ilst.end())
		cout << *it++ << ", " ;

	cout << endl;
}
void PrintOut(vector<string> &sivect)
{
	string a(30,'*');
	cout << a << endl;
	cout << "vector size:" << sivect.size() << " element: ";

	vector<string>::iterator it = sivect.begin();
	while( it != sivect.end())
		cout << *it++ << ", " ;

	cout << endl;
}

Section 9.4 How a vector Grows

Ordinarily, we should not care about how a library type works: All we should care about is how to use it. However, in the case of vectors, a bit of the implementation leaks into its interface. To support fast random access, vector elements are stored contiguouslyeach element is adjacent to the previous element
Given that elements are contiguous, let's think about what happens when we add an element to a vector: If there is no room in the vector for the new element, it cannot just add an element somewhere else in memory because the elements must be contiguous for indexing to work. Instead, the vector must allocate new memory to hold the existing elements plus the new one, copy 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, then performance would be unacceptably slow
There is no comparable allocation issue for containers that do not hold their elements contiguously
One might conclude, therefore, that in general it is a good idea to use a list rather than a vector. However, the contrary is usually the case: For most applications the best container to use is a vector. The reason is that library implementors use allocation strategies that minimize the costs of storing elements contiguously. That cost is usually offset by the advantages in accessing elements that contiguous storage allows
The way vectors achieve fast allocation is by allocating capacity beyond what is immediately needed. The vector 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. The exact amount of additional capacity allocated varies across different implementations of the library. 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
9.4.1. capacity and reserve Members
1. The vector class includes two members, capacity and reserve, that let us interact with the memory-allocation part of vector's implementation. The capacity operation tells us how many elements the container could hold before it must allocate more space. The reserve operation lets us tell the vector how many elements it should be prepared to hold
2. It is important to understand the difference between capacity and size. The size is the number of elements in the vector; capacity is how many it could hold before new space must be allocated
3. We know that the size of an empty vector is zero, and evidently our library also sets capacity of an empty vector to zero
4. Because we used only reserved capacity, there is no need for the vector to do any allocation. In fact, as long as there is excess capacity, the vector must not reallocate its elements
5. this vector implementation appears to follow a strategy of doubling the current capacity each time it has to allocate new storage
6. Each implementation of vector is free to choose its own allocation strategy. However, it must provide the reserve and capacity functions, and it must not allocate new memory until it is forced to do so. How much memory it allocates is up to the implementation. Different libraries will implement different strategies
7. Moreover, every implementation is required to follow a strategy that ensures that it is efficient to use push_back to populate a vector. Technically speaking, the execution time of creating an n-element vector by calling push_back n times on an initially empty vector is never more than a constant multiple of n
```
// EXE-9.4.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <string>

using namespace std;

int main(int argc, _TCHAR* argv[])
{
	if("9.4.1. capacity and reserve Members")
	{
		vector<int> ivec;

		// size should be zero; capacity is implementation defined
		cout << "ivec: size: " << ivec.size()
			<< " capacity: "  << ivec.capacity() << endl;

		// give ivec 24 elements
		for (vector<int>::size_type ix = 0; ix != 24; ++ix)
			ivec.push_back(ix);

		// size should be 24; capacity will be >= 24 and is implementation defined
		cout << "ivec: size: " << ivec.size()
			<< " capacity: "  << ivec.capacity() << endl;

		ivec.reserve(50);  // sets capacity to at least 50; might be more
		// size should be 24; capacity will be >= 50 and is implementation defined
		cout << "ivec: size: " << ivec.size()
			<< " capacity: "  << ivec.capacity() << endl;

		// add elements to use up the excess capacity
		while (ivec.size() != ivec.capacity())
			ivec.push_back(0);
		// size should be 50; capacity should be unchanged
		cout << "ivec: size: " << ivec.size()
			<< " capacity: "  << ivec.capacity() << endl;
		
		ivec.push_back(42); // add one more element
		// size should be 51; capacity will be >= 51 and is implementation defined
		cout << "ivec: size: " << ivec.size()
			<< " capacity: "  << ivec.capacity() << endl;

	}
	int i;
	cin >> i;

	return 0;
}
```

Section 9.5 Deciding Which Container to Use

Whether elements are stored contiguously has other significant impacts on:

The costs to add or delete elements from the middle of the container
The costs to perform nonsequential access to elements of the container

The degree to which a program does these operations should be used to determine which type of container to use. The vector and deque types provide fast non-sequential access to elements at the cost of making it expensive to add or remove elements anywhere other than the ends of the container. The list type supports fast insertion and deletion anywhere but at the cost of making nonsequential access to elements expensive
How Insertion Affects Choice of Container
1. A list represents noncontiguous memory and allows for both forward and backward traversal one element at a time. It is efficient to insert or erase an element at any point. Inserting or removing an element in a list does not move any other elements. Random access, on the other hand, is not supported. Accessing an element requires traversing the intervening elements
  A deque is a more complicated data structure. We are guaranteed that adding or removing elements from either end of the deque is a fast operation. Adding or removing from the middle will be more expensive. A deque offers some properties of both list and vector:
  - Like vector, it is inefficient to insert or erase elements in the middle of the deque.
  - Unlike vector, a deque offers efficient insert and erase at the front as well as at the back.
  - Unlike list and like vector, a deque supports fast random access to any element.
  - Inserting elements at the front or back of a deque does not invalidate any iterators. Erasing the front or back element invalidates only iterators referring to the element(s) erased. Inserting or erasing anywhere else in the deque invalidates all iterators referring to elements of the deque
How Access to the Elements Affects Choice of Container
1. It is much slower to jump around in a list. the only way to move between the elements of a list is to sequentially follow the pointers. Moving from the 5th to the 15th element requires visiting every element between them
2. In general, unless there is a good reason to prefer another container, vector is usually the right one to use
Hints on Selecting Which Container to Use
1. Deciding which container to use may require profiling the performance of each container type doing the kinds of operations the application requires
2. When you are not certain which container the application should use, try to write your code so that it uses only operations common to both vectors and lists: Use iterators, not subscripts, and avoid random access to elements. By writing your programs this way, it will be easier to change the container from a vector to a list if necessary

Section 9.6 strings Revisited

Table 9.12. `string` Operations Introduced in Section 3.2
`string s;`	Defines a new, empty `string` named `s`.
`string s(cp);`	Defines a new `string` initialized from the null-terminated C-style string pointed to by `cp`.
`string s(s2);`	Defines a new `string` initialized as a copy of `s2`.
`is >> s;`	Reads a whitespace-separated string from the input stream `is` into `s`.
`os << s;`	Writes `s` to the output stream `os`.
`getline(is, s)`	Reads characters up to the first newline from input stream `is` into `s`.
`s1 + s2`	Concatenates `s1` and `s2`, yielding a new `string`.
`s1 += s2`	Appends `s2` to `s1`.
Relational Operators	The equality (`==` and `!=`) and relational (`<, <=, >`, and `>=)` can be used to compare `string`s. `string` comparison is equivalent to (case-sensitive) dictionary ordering.

In addition to the operations we've already used, strings also supports most of the sequential container operations. In some ways, we can think of a string as a container of characters
The container operations that string supports are:
- The typedefs, including the iterator types, listed in Table 9.5 (p. 316).
- The constructors listed in Table 9.2 (p. 307) except for the constructor that takes a single size parameter.
- The operations to add elements listed in Table 9.7 (p. 319) that vector supports. Note: Neither vector nor string supports push_front.
- The size operations in Table 9.8 (p. 324).
- The subscript and at operations listed in Table 9.9 (p. 325); string does not provide back or front operations listed in that table.
- The begin and end operations of Table 9.6 (p. 317).
- The erase and clear operations of Table 9.10 (p. 326); string does not support either pop_back or pop_front.
- The assignment operations in Table 9.11 (p. 329).
- Like the elements in a vector, the characters of a string are stored contiguously. Therefore, string supports the capacity and reserve operations described in Section 9.4 (p. 330).
The string library defines a great number of functions, which use repeated patterns. Given the number of functions supported, this section can be mind-numbing on first reading

9.6.1. Other Ways to Construct strings

The definition of s4 is an error. This form of initialization may be called only with a null-terminated array. Passing an array that does not contain a null is a serious error (Section 4.3, p. 130), although it is an error that the compiler cannot detect. What happens at run time is undefined

Table 9.13. Additional Ways to Construct `string`s
`string s(cp, n)`	Create `s` as a copy of `n` characters from array pointed to by `cp`.
`string s(s2, pos2)`	Create `s` as a copy of characters in the `string s2` starting at index `pos2`. Undefined if `pos2 > s2.size()`.
`string s(s2, pos2, len2)`
	Create `s` as a copy of `len2` characters from `s2` starting at index `pos2`. Undefined if `pos2 > s2.size()`. Regardless of the value of `len2`, copies at most `s2.size() - pos2` characters.
Note: `n, len2` and `pos2` are all `unsigned` values

Using a Substring as the Initializer

9.6.2. Other Ways to Change a string

Table 9.14. `string` Operations in Common with the Containers
`s.insert(p, t)`	Insert copy of value `t` before element referred to by iterator `p`. Returns an iterator referring to the inserted element.
`s.insert(p, n, t)`	Insert `n` copies of `t` before `p`. Returns `void`.
`s.insert(p, b, e)`	Insert elements in range denoted by iterators `b` and `e` before `p`. Returns `void`.
`s.assign(b, e)`	Replace `s` by elements in range denoted by `b` and `e`. For `string`, returns `s`, for the containers, returns `void`.
`s.assign(n, t)`	Replace `s` by `n` copies of value `t`. For `string`, returns `s`, for the containers, returns `void`.
`s.erase(p)`	Erase element referred to by iteartor `p`. Returns an iterator to the element after the one deleted.
`s.erase(b, e)`	Remove elements in range denoted by `b` and `e`. Returns an iterator to the first element after the range deleted.

Table 9.15. `string`-Specific Versions
`s.insert(pos, n, c)`	Insert `n` copies of character `c` before element at index `pos`.
`s.insert(pos, s2)`	Insert copy of `string s2` before `pos`.
`s.insert(pos, s2, pos2, len)`
	Insert `len` characters from `s2` starting at `pos2` before `pos`.
`s.insert(pos, cp, len)`	Insert `len` characters from array pointed to by `cp` before `pos`.
`s.insert(pos, cp)`	Insert copy of null-terminated string pointed to by `cp` before `pos`.
`s.assign(s2)`	Replace `s` by a copy of `s2`.
`s.assign(s2, pos2, len)`	Replace `s` by a copy of `len` characters from `s2` starting at index `pos2` in `s2`.
`s.assign(cp, len)`	Replace `s` by `len` characters from array pointed to by `cp`.
`s.assign(cp)`	Replace `s` by null-terminated array pointed to by `cp`.
`s.erase(pos, len)`	Erase `len` characters starting at `pos`.
Unless noted otherwise, all operations return a reference to `s`.

Position-Based Arguments
Specifying the New Contents
1. The characters to insert or assign into the string can be taken from a character array or another string

9.6.3. string-Only Operations

The string type provides several other operations that the containers do not:
- The substr function that returns a substring of the current string
- The append and replace functions that modify the string
- A family of find functions that search the string
The substr Operation
The append and replace Functions

Table 9.17. Operations to Modify `string`s (args defined in Table 9.18)
`s.append(` args`)`	Append args to `s`. Returns reference to `s`.
`s.replace(pos, len`, args`)`	Remove `len` characters from `s` starting at `pos` and replace them by characters formed by args. Returns reference to `s`. This version does not take args equal to `b2`, `e2`.
`s.replace(b, e`, args`)`	Remove characters in the range denoted by iterators `b` and `e` and replace them by args. Returns reference to `s`. This version does not take args equal to `s2, pos2, len2`.

There is no requirement that the size of the text removed and inserted be the same

Table 9.18. Arguments to `append` and `replace`
`s2`	The `string s2`.
`s2, pos2, len2`	up to `len2` characters from `s2` starting at `pos2`.
`cp`	Null-terminated array pointed to by pointer `cp`.
`cp, len2`	up to `len2` characters from character array pointed to by `cp`.
`n, c`	`n` copies of character `c`.
`b2, e2`	Characters in the range formed by iterators `b2` and `e2`.

9.6.4. string Search Operations

Table 9.19. `string` Search Operations (Arguments in Table 9.20)
`s.find(` args`)`	Find first occurrence of args in `s`.
`s.rfind(` args`)`	Find last occurrence of args in `s`.
`s.find_first_of(` args`)`	Find first occurrence of any character from args in `s`.
`s.find_last_of(` args`)`	Find last occurrence of any character from args in `s`.
`s.find_first_not_of(` args`)`	Find first character in `s` that is not in args.
`s.find_last_not_of(` args`)`	Find last character in `s` that is not in args.

Table 9.20. Arguments to `string find` Operations
`c, pos`	Look for the character `c` starting at position `pos` in `s`. `pos` defaults to 0.
`s2, pos`	Look for the `string s2` starting at position `pos` in `s`. `pos` defaults to 0.
`cp, pos`	Look for the C-style null-terminated string pointed to by the pointer `cp`. Start looking starting at position `pos` in `s`. `pos` defaults to 0.
`cp, pos, n`	Look for the first `n` characters in the array pointed to by the pointer `cp`. Start looking starting at position `pos` in `s`. No default for `pos` or `n`.

Finding an Exact Match
1. By default, the find operations (and other string operations that deal with characters) use the built-in operators to compare characters in the string. As a result, these operations (and other string operations) are case sensitive
2. The find operations return a string::size_type. Use an object of that type to hold the return from find
3. It is essential that we increment pos. Doing so ensures that we start looking for the next number at a point after the number we just found
Find Any Character
Specifying Where to Start the Search
Looking for a Nonmatch
Searching Backward
The find_last Functions

9.6.5. Comparing strings

the string type defines all the relational operators so that we can compare two strings for equality (==), inequality (!=), and the less- or greater-than operations (<, <=, >, >=). Comparison between strings is lexicographicalthat is, string comparison is the same as a case-sensitive, dictionary ordering

The compare Functions

In addition to the relational operators, string provides a set of compare operations that perform lexicographical comparions. The results of these operations are similar to the C library strcmp function
compare returns one of three possible values:
1. A positive value if s1 is greater than the string represented by args
2. A negative value if s1 is less than the string represented by args
3. 0 if s1 is equal to the string represented by args

Table 9.21. `string compare` Operations
`s.compare(s2)`	Compare `s` to `s2`.
`s.compare(pos1, n1, s2)`
	Compares `n1` characters starting at `pos1` from `s` to `s2`.
`s.compare(pos1, n1, s2, pos2, n2)`
	Compares `n1` characters starting at `pos1` from `s` to the `n2` characters starting at `pos2` in `s2`.
`s.compare(cp)`	Compares `s` to the null-terminated string pointed to by `cp`.
`s.compare(pos1, n1, cp)`
	Compares `n1` characters starting at `pos1` from `s` to `cp`.
`s.compare(pos1, n1, cp, n2)`
	Compares `n1` characters starting at `pos1` from `s` to `n2` characters starting from the pointer `cp`.

Section 9.7 Container Adaptor

In addition to the sequential containers, the library provides three sequential container adaptors: queue, priority_queue, and stack

An adaptor is a general concept in the library. There are container, iterator, and function adaptors. Essentially, an adaptor is a mechanism for making one thing act like another. A container adaptor takes an existing container type and makes it act like a different abstract type

Table 9.22. Common Adaptor Operations and Types
`size_type`	Type large enough to hold size of largest object of this type.
`value_type`	Element type.
`container_type`	Type of the underlying container on which the adaptor is implemented.
`A a;`	Create a new empty adaptor named `a`.
`A a(c);`	Create a new adaptor named `a` with a copy of the container `c`.
Relational Operators	Each adaptor supports all the relational operators: `==, !=, <, <=, >, >=`.

Initializing an Adapator
1. Each adaptor defines two constructors: the default constructor that creates an empty object and a constructor that takes a container and makes a copy of that container as its underlying value
Overriding the Underlying Container Type
1. By default both stack and queue are implemented in terms of deque, and a priority_queue is implemented on a vector. We can override the default container type by naming a sequential container as a second type argument when creating the adaptor
2. There are constraints on which containers can be used for a given adapator. We can use any of the sequential containers as the underlying container for a stack
Relational Operations on Adaptors
1. Two adaptors of the same type can be compared for equality, inequality, less-than, greater-than, less-than-equal, and greater-than-equal relationships, provided that the underlying element type supports the equality and less-than operators

9.7.1. Stack Adaptor

Table 9.23. Operations Supported by the Stack Container Adaptor
`s.empty()`	Returns `TRue` if the `stack` is empty; false otherwise.
`s.size()`	Returns a count of the number of elements on the `stack`.
`s.pop()`	Removes, but does not return, the top element from the `stack`.
`s.top()`	Returns, but does not remove, the top element on the `stack`.
`s.push(item)`	Places a new top element on the `stack`.

9.7.2. Queue and Priority Queue

The library queue uses a first-in, first-out (FIFO) storage and retrieval policy. Objects entering the queue are placed in the back. The next object retrieved is taken from the front of the queue. There are two kinds of queues: the FIFO queue, which we will speak of simply as a queue, and a priority queue
A priority_queue lets us establish a priority among the elements held in the queue. Rather than place a newly entered item at the back of the queue, the item is placed ahead of all those items with a lower priority. By default, the library uses the < operator on the element type to determine relative priorities

To use either queue or priority_queue, we must include the queue header

Table 9.24. Operations Supported by Queues and Priority Queues
`q.empty()`	Returns `TRue` if the `queue` is empty; false otherwise.
`q.size()`	Returns a count of the number of elements on the `queue`.
`q.pop()`	Removes, but does not return, the front element from the `queue`.
`q.front()`	Returns, but does not remove, the front element on the `queue`. This operation can be applied only to a `queue`.
`q.back()`	Returns, but does not remove, the back element on the `queue`. This operation can be applied only to a `queue`.
`q.top()`	Returns, but does not remove, the highest-priority element. This operation can be applied only to a `priority_queue`.
`q.push(item)`	Places a new element at the end of the `queue` or at its appropriate position based on priority in a `priority_queue`.

Pages

Friday, January 21, 2011

Table 10.1. Associative Container Types

Section 10.1 Preliminaries: the pair Type

Table 10.2. Operations on pairs

Section 10.2 Associative Containers

Section 10.3 The map Type

Table 10.3. Constructors for map

Table 10.4. Types Defined by the map Class

Table 10.5. insert Operations on maps

Section 10.4 The set Type

Section 10.5 The multimap and multiset Types

Table 10.8. Associative Container Operations Returning Iterators

Section 10.6 Using Containers: Text-Query Program

Monday, January 17, 2011

Section 18.1 Optimizing Memory Allocation

Section 18.2 Run-Time Type Identification

Section 18.3 Pointer to Class Member

Section 18.4 Nested Classes

Section 18.5 Union: A Space-Saving Class

Section 18.6 Local Classes

Section 18.7 Inherently Nonportable Features

Section 17.1 Exception Handling

Section 17.2 Namespaces

Section 17.3 Multiple and Virtual Inheritance

Section 15.1 OOP: An Overview

Section 15.2 Defining Base and Derived Classes

Section 15.3 Conversions and Inheritance

Section 15.4 Constructors and Copy Control

Section 15.5 Class Scope under Inheritance

Section 15.6 Pure Virtual Functions

Section 15.7 Containers and Inheritance

Section 15.8 Handle Classes and Inheritance

Section 15.9 Text Queries Revisited

Table 9.1. Sequential Container Types

Section 9.1 Defining a Sequential Container

Table 9.2. Container Constructors

Section 9.2 Iterators and Iterator Ranges

Table 9.3. Common Iterator Operations

Table 9.4. Operations Supported by vector and deque Iterators

Requirements on Iterators Forming an Iterator Range

Section 9.3 Sequence Container Operations

Table 9.5. Container-Defined Typedefs

Table 9.6. Container begin and end Operations

Key Concept: Container Elements Are Copies

Table 9.7. Operations that Add Elements to a Sequential Container

Table 9.8. Sequential Container Size Operations

Table 9.9. Operations to Access Elements in a Sequential Container

Table 9.10. Operations to Remove Elements from a Sequential Container

Table 9.11. Sequential Container Assignment Operations

Section 9.4 How a vector Grows

Section 9.5 Deciding Which Container to Use

Hints on Selecting Which Container to Use

Section 9.6 strings Revisited

Table 9.12. string Operations Introduced in Section 3.2

Table 9.13. Additional Ways to Construct strings

Table 9.14. string Operations in Common with the Containers

Table 9.15. string-Specific Versions

Table 9.17. Operations to Modify strings (args defined in Table 9.18)

Table 9.18. Arguments to append and replace

Table 9.19. string Search Operations (Arguments in Table 9.20)

Table 9.20. Arguments to string find Operations

Table 9.21. string compare Operations

Section 9.7 Container Adaptor

Table 9.22. Common Adaptor Operations and Types

Table 9.23. Operations Supported by the Stack Container Adaptor

Table 9.24. Operations Supported by Queues and Priority Queues

Table 10.2. Operations on `pairs`

Table 10.3. Constructors for `map`

Table 10.4. Types Defined by the `map` Class

Table 10.5. `insert` Operations on maps

Table 9.4. Operations Supported by `vector` and `deque` Iterators

Table 9.6. Container `begin` and `end` Operations

Table 9.12. `string` Operations Introduced in Section 3.2

Table 9.13. Additional Ways to Construct `string`s

Table 9.14. `string` Operations in Common with the Containers

Table 9.15. `string`-Specific Versions

Table 9.17. Operations to Modify `string`s (args defined in Table 9.18)

Table 9.18. Arguments to `append` and `replace`

Table 9.19. `string` Search Operations (Arguments in Table 9.20)

Table 9.20. Arguments to `string find` Operations

Table 9.21. `string compare` Operations