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.
|
| ||||||||||||||||
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
- Intializing a Container as a Copy of Another Container
- 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
- 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
- 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
- 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
- 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
char *words[] = {"stately", "plump", "buck", "mulligan"};
// calculate how many elements in words
size_t words_size = sizeof(words)/sizeof(char *);
// use entire array to initialize words2
list<string> words2(words, words + words_size);
- Allocating and Initializing a Specified Number of Elements
- The constructors that take a size are valid only for sequential containers; they are not supported for the associative containers
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
- 9.1.2. Constraints on Types that a Container Can Hold
The element type must support assignment.
We must be able to copy objects of the element type.
- 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
- References do not support assignment in its ordinary meaning, so we cannot have containers of references
- 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
- The IO library types do not support copy or assignment. Therefore, we cannot have a container that holds objects of the IO types
- Container Operations May Impose Additional Requirements
- 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
- 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
- Containers of Containers
- Note the spacing used when specifying a container element type as a container
vector< vector<string> > lines; // ok: space required between close >
vector< vector<string>> lines; // error: >> treated as shift operator - 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
- Note the spacing used when specifying a container element type as a container
While most types can be used as the element type of a container, there are two constraints that element types must meet:
// 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
- 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 - nAdding (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 -= iter2Compound-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
- 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
- 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
When first equals last, the range is empty.
When first is not equal to last, there is at least one element in the range, and first refers to the first element in that range. Moreover, we can advance first by incrementing it some number of times until first == last
The library uses left-inclusive ranges because such ranges have two convenient properties. Assuming first and last denote a valid iterator range, then
- The concept of an iterator range is fundamental to the standard library.
- 9.2.2. Some Container Operations Invalidate Iterators
- 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
- 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
- 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
- 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
- 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
|
Section 9.3 Sequence Container Operations
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
- The begin and end operations yield iterators that refer to the first and one past the last element in the container.
- 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
- 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
- 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
- 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
- Avoid Storing the Iterator Returned from end
- 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
- Don't cache the iterator returned from end. Inserting or deleting elements in a deque or vector will invalidate the cached iterator
- 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
- Every sequential container supports push_back, which appends an element to the back of the container
- 9.3.4. Relational Operators
- The containers must be the same kind of container and must hold elements of the same type
- 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
- Relational Operators Use Their Element's Relational Operator
- We can compare two containers only if the same relational operator defined for the element types
- We can compare two containers only if the same relational operator defined for the element types
- The containers must be the same kind of container and must hold elements of the same type
- 9.3.5. Container Size Operations
- 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
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
- 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
- If a container is not empty, then the front and back members return references bound to the first or last elements in the container
- 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.
- a
- 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
- Removing an Element From within the Container
- The more general way to remove an element, or range of elements, is through erase.
- 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
- 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
- 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
- The more general way to remove an element, or range of elements, is through erase.
- Removing All the Elements in a Container
- To delete all the elements in a container, we could either call clear or pass the iterators from begin and end to erase
- 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
- To delete all the elements in a container, we could either call clear or pass the iterators from begin and end to erase
- 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
- 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
- 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.
- Using swap to Avoid the Cost of Deleting Elements
- 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
- 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
- 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
- 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
// 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;
} - 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
Each sequential container defines a set of useful typedefs and supports operations that let us
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
- 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
- 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
- We know that the size of an empty vector is zero, and evidently our library also sets capacity of an empty vector to zero
- 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
- this vector implementation appears to follow a strategy of doubling the current capacity each time it has to allocate new storage
- 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
- 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;
} - 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
Section 9.5 Deciding Which Container to Use
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
- 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
- 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
- How Access to the Elements Affects Choice of Container
- 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
- In general, unless there is a good reason to prefer another container, vector is usually the right one to use
- 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
- Hints on Selecting Which Container to Use
If the program requires random access to elements, use a vector or a deque.
If the program needs to insert or delete elements in the middle of the container, use a list.
If the program needs to insert or delete elements at the front and the back, but not in the middle, of the container, use a deque.
If we need to insert elements in the middle of the container only while reading input and then need random access to the elements, consider reading them into a list and then reordering the list as appropriate for subsequent access and copying the reordered list into a vector
- Deciding which container to use may require profiling the performance of each container type doing the kinds of operations the application requires
- 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
Hints on Selecting Which Container to Use
There are a few rules of thumb that apply to selecting which container to use:
Whether elements are stored contiguously has other significant impacts on:
Section 9.6 strings Revisited
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 strings
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
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 strings (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
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
The find operations return a string::size_type. Use an object of that type to hold the return from find
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:
A positive value if s1 is greater than the string represented by args
A negative value if s1 is less than the string represented by args
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
- 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
- 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
- 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
- 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
- Relational Operations on Adaptors
- 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
- a
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.
- 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
No comments:
Post a Comment