|
C++ Standard Library, The: A Tutorial and Reference
Chap 2 Introduction to C++ and the Standard Library
2.1 history
string classes are designed as a safe and convenient component. Thus, they provide an almost self-explanatory interface and check for many errors in the interface.
The STL was designed to combine different data structures with different algorithms while achieving the best performance. Thus, the STL is not very convenient and it is not required to check for many logical errors. To benefit from the powerful framework and great performance of the STL, you must know the concepts and apply them carefully.
A template is not compiled once to generate code usable for any type; instead, it is compiled for each type or combination of types for which it is used. This leads to an important problem in the handling of templates in practice: You must have the implementation of a template function available when you call it, so that you can compile the function for your specific type. Therefore, the only portable way of using templates at the moment is to implement them in header files by using inline functions.
2.2 New Language Features
2.2.1 Templates
Non-type Template Parameters
In addition to type parameters, it is also possible to use nontype parameters. A nontype parameter is then considered as part of the type.
Default Template Parameters
Templates classes may have default arguments
Keyword Typename
Note that typename is always necessary to qualify an identifier of a template as being a type, even if an interpretation that is not a type would make no sense. Thus, the general rule in C++ is that any identifier of a template is considered to be a value, except it is qualified by typename.
Member Templates
Member functions of classes may be templates. However, member templates may not be virtual, nor may they have default parameters.
This feature is often used to support automatic type conversions for members in template classes. By providing a different template type for the member function, you relax the rule of exact match.
A special form of a member template is a template constructor. Template constructors are usually provided to enable implicit type conversions when objects are copied. Note that a template constructor does not hide the implicit copy constructor. If the type matches exactly, the implicit copy constructor is generated and called.
Nested Template Classes
2.2.2 Explicit Initialization for Fundamental Types
If you use the syntax of an explicit constructor call without arguments, fundamental types are initialized with zero
2.2.3 Exception Handling
2.2.4 Namespace
Unlike classes, namespaces are open for definitions and extensions in different modules. Thus you can use namespaces to define modules, libraries, or components even by using multiple files.
A namespace defines logical modules instead of physical modules.
using directives in header files is really bad design.
2.2.5 Type bool
2.2.6 Keyword explicit
Note that explicit also rules out the initialization with type conversion by using the assignment syntax:
Stack s1(40); // OK
Stack s2 = 40; // ERROR
This is because there is a minor difference between
X x;
Y y(x); // explicit conversion
and
X x;
Y y = x; // implicit conversion
The former creates a new object of type Y by using an explicit conversion from type X, whereas the latter creates a new object of type Y by using an implicit conversion.
2.2.8 Initialization of Constant Static Members
It is now possible to initialize integral constant static members inside the class structure. This is useful when the constant is used in the class structure after the initialization. For example:
class MyClass {
static const int num = 100;
int elems[num];
...
};
Note that you still have to to define space for a constant static member that is initialized within a class definition:
const int MyClass::num; // no initialization here
Chap 3 General Concept
3.3 Error and Exception Handling
These standard exception classes can be divided into three groups:
1. Exceptions for language support:
bad_alloc (new)
bad_cast (dynamic_cast)
bad_typeid (typeid)
bad_exception (unexpected())
2. Exceptions for the C++ standard library:usually derived from class logic_error
invalid_argument
length_error
out_of_range
domain_error
ios_base::failure
3. Exceptions for errors outside the scope of a program:derived from runtime_error
range_error
overflow_error
underflow_error
3.4 Allocators
An allocator represents a special memory model. It is used as abstraction to translate the need to use memory into a raw call for memory.
It serves as a base for technical solutions that use certain memory models, such as shared memory, garbage collection, and object-oriented databases, without changing the interfaces.
default allocator: Only occasionally does it make sense to program customized allocators.
Chapter 4 Utilities
4.1 class pair
the container classes map and multimap use pairs to manage their elements
make_pair()
makes it convenient to pass two values of a pair directly to a function that requires a pair as its argument
4.2 auto_ptr
Note that class auto_ptr<> does not allow you to initialize an object with an ordinary pointer by using the assignment syntax. Thus, you must initialize the auto_ptr directly by using its value :
std::auto_ptr<ClassA> ptr1(new ClassA); //OK
std::auto_ptr<ClassA> ptr2 = new ClassA; //ERROR
The transfer of ownership implies a special use for auto_ptrs----that is, functions can use them to transfer ownership to other functions.
constant auto_ptrs reduce the danger of an unintended transfer of ownership.The const does not mean that you can't change the value of the object the auto_ptr owns (if any). You can't change the ownership of a constant auto_ptr; however, you can change the value of the object to which it refers.
auto_ptrs are not provided for arrays!
auto_ptrs don't meet the requirements for container elements.Fortunately, the design of the language and library prevents this misuse from compiling in a standard-conforming environment.
we needs to find a mechanism to enable an rvalue to be converted to an lvalue.Thus, the auto_ptr_ref class was introduced to provide this convert-to-lvalue mechanism.
4.3 numeric_limits<>
numeric_limits is a typical example of specialization of a general template
The specializations are provided for any fundamental type that can represent numeric values
4.4 Auxiliary Functions:min, max, swap
min() and max() require that both types match.
comparison criterion as an additional argument.
The big advantage of using swap()is that it enables to provide special implementations for more complex types by using template specialization or function overloading.These special implementations might save time by swapping internal members rather than by assigning the objects. This is the case, for example, for all standard containers and strings .
4.5 Supplementary Comparison Operators
Four template functions define the comparison operators !=, >, <=, and >= by calling the operators == and <.
they are defined in a subnamespace of std, i.e, std::rel_ops.
4.6 Header Files <cstddef> and <cstdlib>
In C++,NULL is simply value 0.Note that in C, NULL often is defined as (void*)0. This is incorrect in C++ because there the type of NULL must be an integer type. Otherwise, you could not assign NULL to a pointer. This is because in C++ there is no automatic conversion from void* to any other pointer type.
Chapter 5 STL
The STL's flexibility, however, has a price, chief of which is that it is not self-explanatory.
5.1 STL Components
The concept of the STL is based on a separation of data and operations.The data is managed by container classes, and the operations are defined by configurable algorithms. Iterators are the glue between these two components. They let any algorithm interact with any container.
5.1 Components
In a way, the STL concept contradicts the original idea of object-oriented programming: The STL separates data and algorithms rather than combining them.
5.2 Containers
Sequence containers: element's position depends on the time and place of the insertion, but it is independent of the value of the element.
Associative containers:actual position of an element depends on its value due to a certain sorting criterion.
The key advantage of automatic sorting is better performance when you search elements. In particular, you can always use a binary search, which results in logarithmic complexity rather than linear complexity.
Strictly speaking, the particular implementation of any container is not defined inside the C++ standard library. However, the behavior and complexity specified by the standard do not leave much room for variation. So, in practice, the implementations differ only in minor details.
Usually, the STL containers provide only those special member functions that in general have "good" timing.This prevents a programmer from calling a function that might cause bad performance.
Note that list.pop_front() does not return the element it removed.
By default,
associative containers
compare the elements or the keys with operator <. However, you can supply your own comparison function to define another ordering criterion.
Associative containers are typically implemented as Red-Black trees.
All of these associative container classes have an optional template argument for the sorting criterion. The default sorting criterion is the operator <. The sorting criterion is also used as the test for equality; that is, two elements are equal if neither is less than the other.
Container Adapters: Stack,Queue,Priority Queue.
5.3 Iterators
fundamental operations of an iterator:
Operator *
Operator ++ and --
Operator == and !=
Operator =
In fact, each container class defines its iterator type as a nested class.As a result, iterators share the same interface but have different types.Because the iterator is defined by the container, it surely does the right thing.
begin() and end() define a half-open range.It has 2 advantage:
1.You have a simple end criterion for loops that iterate over the elements: They simply continue as long as end() is not reached.
2. It avoids special handling for empty ranges. For empty ranges, begin() is equal to end().
Every container defines two iterator types:
container:: iterator
container:: const_iterator
You can't use the subscript operator([]) for multimaps.
Random access iterator provide operators for iterator arithmetic(in accordance with "pointer arithmetic" of an ordinary pointer).The iterators of the container classes vector and deque, and iterators of strings are random access iterators.
5.4 Algorithms
Algorithms are not member functions of the container classes. Instead, they are global functions that operate with iterators.Instead of each algorithm being implemented for each container type, all are implemented only once for any container type.
Note that this is not an object-oriented programming paradigm; it is a generic functional programming paradigm.
Ensuring the ranges are valid is not always as easy as it sounds.If this is not the case, the behavior is undefined
Every algorithm processes half-open ranges.
Multiple Ranges：Several algorithms process more than one range. In this case you usually must define both the beginning and the end only for the first range. For all other ranges you need to pass only their beginnings.
5.5 Iterator Adapters
Iterators are pure abstractions: Anything that behaves like an iterator is an iterator.
5.5.1 Insert Iterators
Insert iterators, or inserters,are used to let algorithms operate in insert mode rather than in overwrite mode.In particular, they solve the problem of algorithms that write to a destination that does not have enough room: they let the destination grow accordingly.
As for Inserter Iterator,A call to step forward is a "no-op"
Three predefined insert iterators:
Back inserters:insert the elements at the back of their container (appends them) by calling push_back()
Front inserters: insert the elements at the front of their container by calling push_front()
General inserters:inserts elements directly in front of the position that is passed as the second argument of its initialization. It calls the insert() member function with the new value and the new position as arguments.For associative containers, the position is taken as a hint to start the search for the correct position. If the position is not correct, however, the timing may be worse than if there was no hint
5.5.2 Stream Iterators
Stream iterators are iterators that read from and write to a stream.
5.5.3 Reverse Iterators
The advantage of using reverse iterators is that all algorithms are able to operate in the opposite direction without special code.
5.6 Manipulating Algorithms
5.6.1 "Removing" Elements
The price of the flexibility of the STL:
In general, iterators do not know their containers(knowing its type ,though). Thus, the algorithms, which use the iterators to access the elements of the container, can't call any member function of the container.
5.6.2 Manipulating Algorithms and Associative Containers
Manipulation algorithms can't use associative containers as a destination;it will results in a failure at compile time
5.6.3 Algorithms versus Member Functions
Even if you are able to use an algorithm, it might be a bad idea to do so. A container might have member functions that provide much better performance.
5.8 Functions as Algorithm Arguments
5.8.2 Predicates
Predicates are functions that return a Boolean value.The STL requires that predicates always yield the same result for the same parameters.
5.9 Function Objects
There are rarely things that are not possible in C++!
It is true that functors do complicate code. However, function objects are more than functions, and they have some advantages:
1. Function objects are "smart functions."
2. Each function object has its own type
3. Function objects are usually faster than ordinary functions.
5.9.2 Predefined Function Objects
A typical example is a function object used as a sorting criterion.
What is interesting is that all these function objects are usually declared inline. Thus, you use a function-like notation or abstraction, but you get good performance.
5.10 Container Elements
Elements of containers must meet certain requirements because containers handle them in a special way.
5.10.1 Requirements for Container Elements
1.An element must be copyable by a copy constructor. The generated copy should be equivalent to the source.
2.An element must be assignable by the assignment operator.
3.An element must be destroyable by a destructor
4.For some member functions of sequence containers, the default constructor must be available.
5.For several operations, the test of equality with operator == must be defined.
6.For associative containers the operations of the sorting criterion must be provided by the elements. By default, this is the operator <, which is called by the less<> function object.
5.10.2 Value Semantics or Reference Semantics
The approach of the STL, only to support value semantics, has strengths and weaknesses
5.11 Errors and Exceptions Inside the STL
5.11.1 Error Handling
The design goal of the STL was the best performance rather than the most security.Error checking wastes time, so almost none is done.
The C++ standard library states that any use of the STL that violates preconditions results in undefined behavior
5.11.2 Exception Handling
The STL almost never checks for logical errors. Therefore, almost no exceptions are generated by the STL itself due to a logical problem.In fact, there is only one function call for which the standard requires that it might cause an exception directly: the at() member function for vectors and deques.
The C++ standard library provides the following basic guarantee for exception safety: will not leak resources or violate container invariants in the face of exceptions.
For all node-based containers (lists, sets, multisets, maps and multimaps), any failure to construct a node simply leaves the container as it was.
All array-based containers (vectors and deques) do not fully recover when an element gets inserted.
Chapter 6. STL Containers
6.1 Common Container Abilities and Operations
Container's constructors are member templates
Assignments VS swap()：swap() offers much better efficiency
6.2 Vectors
6.2.1 Abilities of Vectors
vector's iterators are random access iterators, so you can use any algorithm of the STL
The capacity of a vector is important for two reasons:
1. Reallocation invalidates all references, pointers, and iterators for elements of the vector.
2. Reallocation takes time.
std::vector<int> v; // create an empty vector
v.reserve (80); // reserve memory for 80 elements
std::vector<T> v(5); // creates a vector and initializes it with five values
// (calls five times the default constructor of type T)
It is not possible to call reserve() for vectors to shrink the capacity.Calling reserve() with an argument that is less than the current capacity is a no-op.
Only at() performs range checking
6.2.3 Using Vectors as Ordinary Arrays
You can expect that for any valid index i in vector v, the following yields true:
&v[i] == &v[0] + i
It simply means that you can use a vector in all cases in which you could use a dynamic array.
For Boolean elements of a vector, the C++ standard library provides a specialization of vector：vector<bool>.
Better not use vector<bool>!
6.3 Deques
It manages its elements with a dynamic array, provides random access, and has almost the same interface as a vector.
To provide this ability, the deque is implemented typically as a bunch of individual blocks, with the first block growing in one direction and the last block growing in the opposite direction.
6.4 Lists
Lists provide many special member functions for moving elements. These member functions are faster versions of general algorithms that have the same names. They are faster because they only redirect pointers rather than copy and move the values.
List only provide bidirectional iterators.
For sorting the elements, lists provide the special member function sort().
6.5 Sets and Multisets
If a special sorting criterion is not passed, the default criterion less<> is used.The function object less sorts the elements by comparing them with operator <.
The sorting criterion must define "strict weak ordering." Strict weak ordering is defined by the following three properties:
1. It has to be antisymmetric.(非对称)
2. It has to be transitive.(传递性)
3. It has to be irreflexive.(非自反)
Like all standardized associative container classes, sets and multisets are usually implemented as balanced binary trees . The standard does not specify this, but it follows from the complexity of set and multiset operations.In fact, sets and multisets are typically implemented as "red-black trees."
Automatic sorting imposes an important constraint on sets and multisets: You may not change the value of an element directly because this might compromise the correct order.
The interface reflects this behavior:
* Sets and multisets don't provide operations for direct element access.
* Indirect access via iterators has the constraint that, from the iterator's point of view, the element value is constant.
You can define the sorting criterion in two ways:
1.As a template parameter
std::set<int,std::greater<int> > coll;
This is the usual way to specify the sorting criterion.In this case, the sorting criterion is part of the type.
2.As a constructor parameter
In this case, you might have a type with several sorting criteria.
Sets and multisets are optimized for fast searching of elements, so they provide special search functions.
Assignments
For these operations both containers must have the same type. In particular, the type of the comparison criteria must be the same, although the comparison criteria themselves may be different.
Inserting and removing
* Sets provide the following interface:
pair<iterator,bool> insert(const value_type& elem);
iterator insert(iterator pos_hint,const value_type& elem);
* Multisets provide the following interface:
iterator insert(const value_type& elem);
iterator insert(iterator pos_hint, const value_type& elem);
6.6 Maps and Multimaps
The elements of a map or multimap may have any types Key and T that meet the following two requirements:
1. The key/value pair must be assignable and copyable.
2. The key must be comparable with the sorting criterion.
In fact, sets, multisets, maps, and multimaps typically use the same internal data type.
maps can be used as associative arrays.
To check whether a map container is less than another map container is done by a lexicographical comparison.
More important is the constraint that the key of all elements inside a map and a multimap is considered to be constant.So,you can't call any modifying algorithm if the destination is a map or multimap.
6.6.3 Using Maps as Associative Arrays
Associative containers don't typically provide abilities for direct element access. Instead, you must use iterators. For maps, however, there is an exception to this rule.
This behavior of an associative array has both advantages and disadvantages:
The advantage is that you can insert new elements into a map with a more convenient interface.
The disadvantage is that you might insert new elements by accident or mistake.
multimap is the typical container for dictionaries.
6.7 Other STL Containers
There are three different approaches to making containers "STL-able"
invasive approach: provide the interface that ah STL container requires
noninvasive approach: provide special iterators
wrapper approach: combining the two previous approaches
The string classes of the C++ standard library are an example of the invasive approach of writing STL containers
string can be considered containers of characters.
6.8 Implementing Reference Semantics
STL container classes provide value semantics but not reference semantics.if you want reference semantics in STL containers,you should use a smart pointer class that avoids possible errors.
Chapter 7. STL Iterators
7.2 Iterator Categories
sorting algorithms require iterators that can perform random access because otherwise the runtime would be poor
Two input iterators are equal if they occupy the same position. However, as stated previously, this does not mean that they return the same value on element access.
Output iterators are the counterparts of input iterators.You can't check whether an output iterator is valid or whether a "writing" was successful.
Note: input iterators are comparable while ouptut iterator are not
Another typical example of output iterators are inserters. Inserters are iterators that insert values into containers
Forward iterators are combinations of input and output iterators.Unlike input iterators and output iterators, forward iterators can refer to the same element in the same collection and process the same element more than once.
Bidirectional iterators are forward iterators that provide the additional ability to iterate backward over the
elements.
Random access iterators are bidirectional iterators that are bidirectional iterators that support "iterator arithmetic". That is ,hey can add and subtract offsets, process differences, and compare iterators with relational operators such as < and >
7.2.6 The Increment and Decrement Problem of Vector Iterators
In general, you can increment and decrement temporary iterators. However, for vectors and strings, you typically can't.
The reason for this strange problem lies in the fact that vector iterators are typically implemented as ordinary pointers.
7.3 Auxiliary Iterator Functions
Three auxiliary functions for iterators: advance(), distance(), and iter_swap()
void advance (InputIterator& pos, Dist n)
Note that advance() does not check whether it crosses the end() of a sequence (it can't check because iterators in general do not know the containers on which they operate). Thus, calling this function might result in undefined behavior because calling operator ++ for the end of a sequence is not defined.
Dist distance (InputIterator pos1, InputIterator pos2)
Dist's type : iterator_traits<InputIterator>::difference_type
The first iterator must refer to an element that is not after the element of the second iterator. Otherwise, the behavior is undefined.
distance() has bad performance for other than random access iterators.
void iter_swap (ForwardIterator1 pos1, ForwardIterator2 pos2)
The iterators don't need to have the same type. However, the values must be assignable.
7.4 Iterator Adapters
7.4.1 Reverse Iterators
Reverse iterators are adapters that redefine increment and decrement operators so that they behave in reverse
You can convert normal iterators to reverse iterators. Naturally, the iterators must be bidirectional iterators, but note that the logical position of an iterator is moved during the conversion .This is not a bug; it's a feature!
logical position (the value returned ) VS physical position (the element pointed to )
Within a conversion from an iterator to a reverse iterator,physical position stays the same.
You can convert reverse iterators back to normal iterators using the base() member function provided by reverse iterators.
Again, physical position (the element the iterator pointer to) is retained, but the logical position (the value the iterator returns ) is changed.
7.4.2 Insert Iterators
The C++ standard library provides three kinds of insert iterators: back inserters, front inserters, and general inserters.Each uses a different member function, which it calls for the container to which it belongs
7.4.3 Stream Iterators
The implementation of an ostream iterator uses the same concept as the implementation of insert iterators .The only difference is that they transform the assignment of a new value into an output operation by using operator >>.
Istream iterators are the counterparts of ostream iterators.However, istream iterators are a bit more complicated than ostream iterators (as usual, reading is more complicated than writing).
end-of-stream iterator:created with the default constructor for istream iterators.If a read fails, every istream iterator becomes an end-of-stream iterator.
7.5 Iterator Traits
For each iterator category, the C++ standard library provides an iterator tag that can be used as a "label" for iterators
C++ standard library provides a special template structure to define the iterator traits.
template <class T> struct iterator_traits {...}
Chapter 8. STL Function Objects
8.1 The Concept of Function Objects
3 important advantages of functors:
1. A function object might be smarter because it may have a state.
2. Each function object has its own type.
3. A function object is usually faster than a function pointer.
There are 2 ways to get a "result" or "feedback" from using function objects with algorithms:
1. You can pass the function objects by reference.To pass a function object by reference you simply have to explicitly qualify the call of the algorithm so that the function object type is a reference
2. You can use the return value of the for_each() algorithm.for_each() has the unique ability to return its function object (no other algorithm can do this)
8.1.4 Predicates versus Function Objects
Not every function that returns a Boolean value is a valid predicate for the STL.
A predicate must be "pure function".
8.2 Predefined Function Objects
less<> is the default criterion whenever objects are sorted or compared, so it is used often. Default sorting operations always produce an ascending order (element < nextElement).
8.2.1 Function Adapters
bind1st,bind2rd,not1,not2
A function adapter is a function object that enables the combining of function objects with each other, with certain values, or with special functions.
Function adapters are function objects themselves.
By using function adapters you can combine different function objects to form very powerful expressions. This kind of programming is called functional composition.
8.2.2 Function Adapters for Member Functions
mem_fun_ref,mem_fun
The adapter is necessary because you can't pass a member function directly to an algorithm. Doing so would cause a compile-time error
mem_fun adapters are for sequences that contain pointers to elements. Probably mem_fun_ptr would have been a less confusing name .
Both mem_fun_ref and mem_fun can call member functions with zero or one argument. However, you can't call member functions with two or more arguments in this way.
Note that the member functions called by mem_fun_ref and mem_fun must be constant member functions. Unfortunately, the C++ standard library does not provide function adapters for nonconstant member functions
8.2.3 Function Adapters for Ordinary Functions
ptr_fun
8.2.4 User-Defined Function Objects for Function Adapters
You can write your own function objects, but to use them in combination with function adapters they must meet certain requirements: They must provide type members for the type of their arguments and the result. The C++ standard library provides structures to make this more convenient:
unary_function,binary_function
8.3 Supplementary Composing Function Objects
In general it should be possible to define almost every functional behavior as a combination of function objects. However, the C++ standard library does not provide enough adapters to support this.
Chapter 9. STL Algorithms
9.2 Algorithm Overview
Algorithms work in overwrite mode rather than in insert mode. Thus, the caller must ensure that destination ranges have enough elements. You can use special insert iterators (see Section 7.4.2) to switch from overwrite to insert mode.
To increase their flexibility and power, several algorithms allow the user to pass user-defined operations, which they call internally. These operations might be ordinary functions or function objects. If these functions return a Boolean value , they are called predicates
The _if suffix
Generally, if there is a version of an algorithm which takes a predicate, it gets the name of the algorithm with the suffix _if.
The _copy suffix
The _copy suffix is used as an indication that elements are not only manipulated but also copied into a
destination range
Non-modifying Algorithms
One of the most important algorithms is for_each()
Modifying Algorithms
The fundamental modifying algorithms are for_each() and transform()
Nevertheless, to be safe you should call merge() only for sorted ranges.
You can't use associative containers as a destination for modifying algorithms.
Removing Algorithms
As with modifying algorithms, you can't use an associative container as a destination
Note that removing algorithms remove elements logically only by overwriting them with the following elements that were not removed. Thus, they do not change the number of elements in the ranges on which they operate. Instead, they return the position of the new "end" of the range
Mutating Algorithms
Mutating algorithms are algorithms that change the order of elements (and not their values) by assigning and swapping their values.As with modifying algorithms, you can't use an associative container as a destination
Sorting Algorithms
Sorting algorithms are a special kind of mutating algorithm.However, sorting is more complicated and therefore usually takes more time than simple mutating operations
As with modifying algorithms, you can't use an associative container as a destination
In fact, these algorithms usually have worse than linear complexity and require random access iterators (for the destination).
sort() is based historically on quicksort
partial_sort() is based historically on heapsort
stable_sort() is also based historically on heapsort
The standard guarantees complexity, but not how it is implemented
Sorted Range Algorithms
Sorted range algorithms require that the ranges on which they operate are sorted according to their sorting criterion.
9.4 The for_each() Algorithm
9.5 Nonmodifying Algorithms
Chapter 10. Special Containers
Container Adapters:Stack,Queue,Priority queue
10.1 Stack
Stack's low-level default container is deque;however,You can use any sequence container class that provides the member functions back(), push_back(), and pop_back().
The core interface of stack:
push()
pop()
top()
The standard class stack<> prefers speed over convenience and safety
10.2 Queue
queue 's low-level default container is also deque;
however You can use any sequence container class that provides the member functions front(), back(), push_back(), and pop_front().
The core interface of queues:
push()
front()
back()
pop()
10.3 Priority Queues
The class priority_queue<> implements a queue from which elements are read according to their priority.
As usual ,you can provide the sorting criterion as a template parameter. By default, the elements are sorted by using operator < in descending order.
Unlike queue, priority_queue use vector as its default low-level container; however,You can use any sequence container class that provides random access iterators and the member functions front(), push_back(), and pop_back().
Random access is necessary for sorting the elements, which is performed by the heap algorithms of the STL
The core interface of priority queues:
push()
top()
pop()
queue's member function push() and pop() will call STL algorithm push_heap() internally.
Note that, unlike other container adapters, no comparison operators are defined.
10.4 Bitsets
Bitsets model fixed-sized arrays of bits or Boolean values.
You can't change the number of bits in a bitset. The number of bits is the template parameter.
The class bitset is defined as a template class with the number of bits as the template parameter
For bitsets, some special constructors are defined. However, there is no special copy constructor, assignment operator, and destructor defined
some useful member functions provided by bitset
bitset<bits>::bitset( ) : Creates a bitset with all bits initialized with zero.
bitset<bits>::bitset(unsigned long value) Creates a bitset that is initialized according to the bits of the integral value value.
explicit bitset<bits>::bitset (const string& str) Create a bitset that is initialized by the string str which may contain only the characters '0' and '1'.
size_t bitset<bits>::size() const Returns the number of bits
size_t bitset<bits>::count() const Returns the number of set bits
bool bitset<bits>::any() const Returns whether any bit is set.
bool bitset<bits>::none() const Returns whether no bit is set.
bitset<bits>& bitset<bits>::set(size_t idx) Sets the bit at position idx to true.
bitset<bits>& bitset<bits>::reset() Resets all bits to false
bitset<bits>& bitset<bits>::flip() Toggles all bits (sets unset bits and vice versa)
Operator [ ] returns a special temporary object of type bitset<>::reference when it is called for non-constant bitsets.
unsigned long bitset<bits>::to_ulong( ) const Returns the integral value that the bits of the bitset represent
string bitset<bits>::to_string () const Returns a string that contains the value of the bitset as a binary representation written with characters '0' for unset bits and '1' for set bits
Chapter 11. Strings
11.1 Motivation
Modern data processing is mostly string processing
find()
All these find functions return an index of the first matching position.Yes,
the
return
value is an integer and not an iterator.
The return type of all find functions is
string::size_type
.
Unlike C-strings, objects of class string have no special character '/0' at the end of the string.
If the search fails, a special value is needed to return the failure. That value is npos, which is also defined by the string class.
The type and value of npos are a big pitfall for the use of strings.
Be very careful that you always use string::size_type and not int or unsigned for the return type when you want to check the return value of a find function
At all places where an index and a length are used as arguments, strings behave according to the following two rules:
1. index must have a valid value；otherwise it throws out_of _range.
2. number of characters could have any value；In particular, string::npos always works as a synonym for "all remaining characters."
Both size() and length() return the numberof characters. In particular, size() has nothing to do with the memory that the string uses.(length()这个名字体现了典型的C函数strlen的风格，size()这个名字则体现了典型STL成员函数的风格)
The function getline() is a special function to read input from streams into a string. It reads every character up to the next end-of-line, which by default is the newline character.
string::size_type is an unsigned integral type
11.2 Description of the String Classes
In most cases ,character '/0' is not treated as a special character that terminate the string
In general, a string might contain any character. In particular, a string might contain the contents of a binary file
Operations that Are Not Provided
1. Regular expressions
2. Word processing (capitalization, case-insensitive comparisons)
11.2.3 Constructors and Destructors
You can't initialize a string with a single character.This means that there is an automatic type conversion from type const char* but not from type char to type string.
11.2.4 Strings and C-Strings
You can use ordinary C-strings in almost every situation where strings are
combined
with other string-like objects
However, there is no automatic type conversion from a string object to a C-string. This is for safety reasons.
Note that string do not provide a special meaning for the character '/0', which is used as special character in an ordinary C-string to mark the end of the string. The character '/0' may be part of a string just like every other character.
There are three possible ways to convert the contents of the string into a raw array of characters or C-string:
1.data( )
Returns the contents of the string as an array of characters. Note that the return type is not a valid C-string because no '/0' character gets appended
2.c_str( )
Returns the contents of the string as a C-string. Thus, the '/0' character is appended
3.copy( )
Copies the contents of the string into a character array provided by the caller. An '/0' character is not appended.
Note that data() and c_str() return an array that is owned by the string. Thus, the caller must not modify or free the memory. The return value of c_str() and data() is valid only until the next call of a non-constant member function for the same string
11.2.5 Size and Capacity
For strings, three "sizes" exist:
1. size() and length()
Return the actual number of characters of the string. Both functions are
equivalent
2. max_size()
Returns the maximum number of characters that a string may contain.this value usually is the maximum value of the type of the index less one.
3. capacity()
Returns the number of characters that a string could contain without having to reallocate its internal memory
Member function reserve() is provided to avoid reallocations.Unlike vectors, you can call reserve() for strings to shrink the capacity.If the argument is less than the current number of characters, it is a nonbinding shrink-to-fit request.The default value of reserve() for string is 0. So, a call of reserve() without any argument is always a nonbinding shrink-to-fit request
The standard, however, specifies that capacity may shrink only because of a call of reserve().
11.2.7 Comparisons
If strings are compared by <, <=, >, or >=, their characters are compared lexicographically according to the current character traits.
11.2.8 Modifiers
The specialization of swap() for strings guarantees constant complexity.
11.2.11 Searching and Finding
All search functions have the word find inside their name.
If the search fails, they return npos
11.2.12 The Value npos
Be very careful when using the string value npos and its type. When you want to check the return value always use string::size_type and not int or unsigned for the type of the return value; otherwise, the comparison of the return value with string::npos might not work.
This behavior is the result of the design decision that npos is defined as -1
static const size_type npos = -1;
Unfortunately, size_type (which is defined by the allocator of the string) must be an unsigned integral type.Because -1 is converted into an unsigned integral type, npos is the maximum unsigned value of its type
To write portable code, however, you should always use string::size_type for any index of your string type
11.2.13 Iterator Support for Strings
String iterators are random access iterators. This means that tyou can use all algorithms
To support the use of back inserters for string, the push_back() function is defined
11.2.14 Internationalization
The character traits are provided to specify the details of how to deal with aspects depending on the representation of a character type
11.2.15 Performance
The standard does not specify how the string class is to be implemented. It only specifies the interface. There may be important differences in speed and memory usage depending on the concept and priorities of the implementation.
If you prefer better speed, make sure that your string class uses a concept such as reference counting
11.2.16 Strings and Vectors
Primary difference between string and vector is their goal:
The primary goal of vectors is to handle and to manipulate the elements of the container, not the container as a whole.Thus, vectors implementations are optimized to operate on elements inside the container
The primary goal of strings is to handle and to manipulate the container (the string) as a whole.Thus, strings are optimized to reduce the costs of assigning and passing the whole container
Chapter 13. Input/Output Using Stream Classes
IOStream library were made templates during standardization.As a side effect, this renders simple forward declarations of stream classes illegal. A header was introduced to provide the appropriate declarations: <iosfwd>
13.1 Common Background of I/O Streams
class istream and ostream are instantiations of class template basic_istream<> and basic_ostream<>, with char as the template parameter.
13.1.3 Global Stream Objects
cin (of class istream)
cout (of class ostream)
cerr (of class ostream) :No buffer
clog (of class ostream):By default, this stream is connected to the same destination as cerr, with the difference that output to clog is buffered.
13.1.5 Manipulators
Manipulators are special objects that are used to manipulate a stream.
endl Outputs '/n' and flushes the output buffer
ends Outputs '/0'
flush Flushes the output buffer
ws Reads and discards whitespaces
13.2 Fundamental Stream Classes and Objects
13.2.1 Classes and Class Hierarchy
The class templates basic_istream<> and basic_ostream<> derive virtually from basic_ios<>,
class template basic_streambuf<> is the heart of the IOStream library.
The IOStream library is designed with a rigid separation of responsibilities(严格分工).
The classes derived from basic_ios "only" handle formatting of the data. Actually, they don't even do the formatting! The actual formatting is delegated to corresponding facets in the locale library.
The actual reading and writing of characters is performed by the stream buffers maintained by the basic_ios sub-objects.
In addition, an abstraction from the external representation (for example files or strings or socket) is formed by the stream buffers. By using stream buffers it is quite easy to define access to a new "external representation" like a new storage device ——derive and custoimize.
Detailed Class Definitions
Here are two instantiations of the class basic_ios<> for the two character types used most often:
namespace std {
typedef basic_ios<char> ios;
typedef basic_ios<wchar_t> wios;
}
the class templates basic_istream<>, basic_ostream<>, and basic_iostream<> are also parameterized with the character type and a traits class.
13.2.3 Header Files
<iosfwd>
Contains forward declarations for the stream classes. This header file is necessary because it is no longer permissible to use a simple forward declaration such as "class ostream;"
<istream>
Contains the definitions for the classes that support input only (basic_istream<>) and for the classes that support both input and output (basic_iostream<>).
<iostream>
Contains declarations of the global stream objects.
In general, only those headers defining necessary stuff should be included. In particular, header files should only include <iosfwd>, and the corresponding implementation files should then include the header with the complete definition.
13.3 Standard Stream Operators << and >>
Type bool
By default, Boolean values are printed and read numerically: false is converted from and to 0, and true is converted from and to 1.
Types char and wchar_t
When a char or wchar_t is being read with operator >>, leading whitespace is skipped by default.
Type char*
A C-string (that is, a char*) is read word-wise. That is, when a C-string is being read, leading whitespace is skipped by default and the string is read until another whitespace character or end-of-file is encountered
Type void*
Operators << and >> also provide the possibility of printing a pointer and reading it back in again.
13.4 State of Streams
For the general state of streams, several constants of type iostate are defined to be used as flags .The type iostate is a member of the class ios_base
goodbit eofbit failbit badbit
The exact type of the constants is an implementation detail .it is not defined whether iostate is an enumeration, a type definition for an integral type, or an instantiation of the class bitset
eofbit normally happens with failbit because the end-of-file condition is checked and detected when an attempt is made to read beyond end-of-file. After reading the last character, the flag eofbit is not yet set. The next attempt to read a character sets eofbit and failbit, because the read fails.
These constants are not defined globally. Instead, they are defined within the class
13.4.2 Member Functions Accessing the State of Streams
The current state of the flags can be determined by the member functions
Note that you always have to clear error bits explicitly.If failbit is set, each following stream operation is a no-op until failbit is cleared explicitly.
13.4.3 Stream State and Boolean Conditions
operator void*()
operator !()
13.4.4 Stream State and Exceptions
To stay backward compatible, by default, streams throw no exceptions. However, for the standardized streams, it is possible to define, for every state flag, whether setting that flag will trigger an exception. This definition is done by the exceptions() member function
The exceptions thrown are objects of the class std::ios_base::failure,which is derived from class exception
13.5 Standard Input/Output Functions
The member functions in this section read or write "unformatted" data.
These functions use type streamsize to specify counts, which is defined in <ios>:
13.5.1 Member Functions for Input
When C-strings are read it is safer to use the functions from this section than to use operator >>.
It is often better to use the stream buffer directly instead of using istream member functions
13.5.2 Member Functions for Output
Like the input functions, it may also be reasonable to use the stream buffer directly or to use the template class ostreambuf_iterator for unformatted writing.
13.6 Manipulators
13.6.1 How Manipulators Work
Manipulators are nothing more than functions that are passed to the I/O operators as arguments. The functions are then called by the operator.
 ostream& ostream::operator << ( ostream& (*op) (ostream&))
  ...{
 // call the function passed as parameter with this stream as the argument
return (*op) (*this);
 }
The manipulator endl() for ostream is implemented basically like this
std::ostream& std::endl (std::ostream& strm)
...{
// write newline
strm.put(' ');
// flush the output buffer
strm.flush();
// return strm to allow chaining
return strm;
}
13.7 Formatting
Two concepts influence the definition of I/O formats: format flag and locale
13.7.1 Format Flags
You can also use manipulators to set and clear format flags
The manipulators setiosflags() and resetiosflags() provide the possibility of setting or clearing, respectively, one or more flags in a write or read statement with operator << or >> respectively
13.7.3 Field Width, Fill Character, and Adjustment
Two member functions are used to define the field width and the fill character: width() and fill()
For the output ,width() defines a minimum field. This definition applies only to the next formatted field written
fill() defines the fill character that is used to fill the difference between the formatted representation of a value and the minimum field width. The default fill character is a space.
13.7.4 Positive Sign and Uppercase Letters
Two format flags are defined to influence the general appearance of numeric values: showpos and uppercase
13.7.7 General Formatting Definitions
ios::skipws is set by default, meaning that by default leading whitespaces are skipped by certain read operations.
ios::unitbuf controls the buffering of the output. With ios::unitbuf set, output is basically unbuffered.By default, this flag is not set. However, for the streams cerr and wcerr this flag is set initially.
13.8 Internationalization
Each stream uses an associated locale object. The initial default locale object is a copy of the global locale object at the construction time of the stream
imbue (loc) Sets the locale object
getloc() Returns the current locale object
widen (c) Converts the char character c to a character of the stream's character set
narrow (c,def) Converts character c from the stream's character set to a char (if there is no such char, def is returned)
13.9 File Access
For streams that are both read and written , it is not possible to switch arbitrarily between reading and writing .This is a restriction inherited from C.
13.9.1 File Flags
A set of flags is defined in the class ios_base .These flags are of type openmode.
ios_base::in ios_base::out ios_base::binary ios_base::append ios_base::trunc ios_base::ate
ios_base::binary configures the stream to suppress conversion of special characters or character sequences such as end-of-line or end-of-file
Whether a file is opened for reading and/or for writing is independent of the corresponding stream object's class. The class only determines the default open mode if no second argument is used.
The open mode is passed to the corresponding stream buffer class, which opens the file. However, the operations possible for the object are determined by the stream's class
The member function open() does not clear the stream's state flags
13.9.2 Random Access
Not all stream classes support positioning. For example, positioning the streams cin, cout, and cerr is not defined
The position's value is type pos_type .The C++ standard library defines a global template class fpos<> for file positions. Class fpos<> is used to define types streampos for char and wstreampos for wchar_t streams
13.9.3 Using File Descriptors
The C++ standard library unfortunately does not provide this possibility of attaching a stream to an I/O channel using file descriptors. This is because the language is supposed to be independent of any operating system.
13.10 Connecting Input and Output Streams
13.10.1 Loose Coupling Using tie()
You can tie a stream to an output stream. This means the buffers of both streams are synchronized in a way that the buffer of the output stream is flushed before each input or output of the other stream.
For each stream, you can only have one output stream that is tied to this stream.However, you can tie an output stream to different streams.
By default, the standard input is connected to the standard output using this mechanism. This ensures that a message asking for input is flushed before requesting the input.
// predefined connections:
std::cin.tie (&std::cout);
std::wcin.tie (&std::wcout);
You can also tie one output stream to another output stream
13.10.2 Tight Coupling Using Stream Buffers
Using the function rdbuf(), you can couple streams tightly by using a common stream buffer
Note that the destructor of the classes basic_istream<> and basic_ostream<> does not delete the corresponding stream buffer (it was not opened by these classes anyway).
The advantage of this approach is that the format does not need to be restored to its original state after it is modified because the format applies to the stream object, not to the stream buffer.
Also note that the destruction of a stream object does not flush the buffer. To make sure that an output buffer is flushed, it has to be flushed manually
The fact that stream buffer is not destroyed applies only to basic_istream<> and basic_ostream<>. The other stream classes destroy the stream buffers they allocated originally, but they do not destroy stream buffers set with rdbuf()
13.10.3 Redirecting Standard Streams
A stream can be redirected by setting a new stream buffer.
Stream's member function copyfmt() can be used to assign all format information of a given stream to another stream object
File streams allocate their stream buffer objects at construction time and destroy them on destruction.
13.10.4 Streams for Reading and Writing
13.11 Stream Classes for Strings
String streams provide a buffer but don't have an I/O channel
Stream classes have a similar relationship to the stream base classes, as do the file stream classes.
The major function in the interface of the string stream classes is the member function str(). This function is used to manipulate the buffer of the string stream classes.
A typical programming error when dealing with string streams is to forget to extract the string with the function str(), and instead to write to the file stream directly.
13.11.2 char* Stream Classes
The char* stream classes are retained only for backward compatibility.Their interface is error prone and they are rarely used correctly.
13.12 Input/Output Operators for User-Defined Types
13.12.4 User-Defined Operators Using Unformatted Functions
The I/O operators defined in the C++ standard library are defined in a common scheme : First, with some pre-processing the stream is prepared for actual I/O. Then the actual I/O is done, followed by some post-processing.
The classes basic_istream and basic_ostream each define an auxiliary class sentry. The constructor of these classes does the preprocessing, and the destructor does the corresponding pos-tprocessing.
If an I/O operator uses a function for unformatted I/O or operates directly on the stream buffer, the first thing to be done should be the construction of a corresponding sentry object.
Its state can be checked using the conversion of the sentry object to bool
The sentry object takes the stream strm, on which the preprocessing and post-processing should be done, as the constructor argument.
Of course, it is also possible to use this framework even if functions do not use unformatted functions for their implementation but use I/O operators instead. However, using basic_istream or basic_ostream members for reading or writing characters within code guarded by sentry objects is unnecessarily expensive. Whenever possible, the corresponding basic_streambuf should be used instead.
13.13 The Stream Buffer Classes
13.13.1 User's View of Stream Buffers
Output Member Function
sputc(c)
sputn(s, n)
The interface to reading characters from a stream buffer is a little bit more complex. This is because for input it is necessary to have a look at a character without consuming it. Also, it is desirable that characters can be put back into the stream buffer when parsing.
pubimbue() installs a new locale object in the stream buffer ,returning the previously installed locale object.
getloc() returns the currently installed locale object.
13.14 Performance Issues
13.14.1 Synchronization with C's Standard Streams
By default, the C++ standard streams are synchronized with the corresponding files from the C standard library
13.14.2 Buffering in Stream Buffers
The functions for formatted I/O use stream buffer iterators to access the streams, and operating on stream buffer iterators is slower than operating on pointers.
13.14.3 Using Stream Buffers Directly
All member functions of the class basic_istream and basic_ostream that read or write characters operate according to the same schema: First, a corresponding sentry object is constructed, then the actual operation is performed.The construction of the sentry object results in flushing of potentially tied objects, skipping of whitespace (for input only), and implementation-specific operations like locking in multithreaded environments
Note that a stream buffer has no error state of its own. It also has no knowledge of the input or ouput stream that might connect to it.
Chapter 14. Internationalization
For the internationalization of programs, two related aspects are important
1. Different character sets have different properties
2. The user of a program expects to see national or cultural conventions obeyed
The major approach toward internationalization is to use locale objects to represent an extensible collection of aspects to be adapted to specific local conventions
Actually, the C++ locale mechanism can be used to address all kinds of customization, depending on the user's environment or preferences.
Most of the mechanisms of internationalization involve no or only minimal additional work for the programmer
Some internationalized aspects supported by the C++ standard library are not used by the C++ standard library itself, and to use them the programmer has to call those functions manually.
Strings and streams use another concept for internationalization: character traits
14.1 Different Character Encodings
14.1.1 Wide-Character and Multibyte Text
Two different approaches are common to address character sets that have more than 256 characters: multibyte representation and wide-character representation
The multibyte representation is more compact than the wide-character representation.Thus, the multibyte representation is normally used to store data outside of programs.
Conversely, it is much easier to process characters of fixed size, so the wide-character representation is usually used inside programs.
Like ISO C, ISO C++ uses the type wchar_t to represent wide characters. However in C++, wchar_t is a keyword rather than a type definition
During iteration through a multibyte string, each byte is interpreted according to a current "shift state". Depending on the value of the byte and the current shift state, a byte may represent a certain character or a change of the current shift state.
14.1.2 Character Traits
C established the convention to return a character as int instead of as char from functions reading characters.This technique was extended in C++. The character traits define char_type as the type to represent all characters, and int_type as the type to represent all characters plus EOF.
The C++ standard library provides specializations of char_traits<> for types char and wchar_t
The specialization for char is usually implemented by using the global string functions of C that are defined in <cstring> or <string.h>.
14.2 The Concept of Locales
14.2.1 Using Locales
According to X/Open conventions, the environment variable LANG is used to define the locale to be used.
C++ provides more library support than C, because basically everything available for char is also available for wchar_t.
The name "C" is a special name, and actually is the only locale a C++ implementation is required to support.
If the name used to construct a locale object is unknown to the implementation, an exception of type runtime_error is thrown.
Passing an empty string as the name of the locale has a special meaning: The default locale from the user's environment is used (this is often determined by the environment variable LANG).
The static member function global()of the class locale can be used to install a global locale object. This object is used as the default value for functions that take an optional locale object as an argument.
However, setting the global locale does not replace locales already stored in objects. It only modifies the locale object copied when a locale is created with a default constructor.
14.2.2 Locale Facets
The actual dependencies on national conventions are separated into several aspects that are handled by corresponding objects. An object dealing with a specific aspect of internationalization is called a facet.
A locale object is used as a container of different facets
The type of the facet is passed explicitly as a template argument to the template function use_facet(), accessing the desired facet.
It is possible to define your own versions of the facets to create specialized locales.
To use this facet in a locale, you need to create a new locale using a special constructor. This constructor takes a locale object as its first argument and a pointer to a facet as its second argument. The created locale is identical to the first argument except for the facet that is passed as the second argument.
14.3 Locales in Detail
A C++ locale is an immutable container for facets.
The strange thing about locales is how the objects stored in the container are accessed. A facet in a locale is accessed using the type of the facet as the index.
Using the facet's type as an index has the additional advantage of having a type-safe interface.
Merely copying a locale is considered to be a cheap operation. Creating a modified locale is more expensive
The standard basically requires that two locales consisting of the same set of named facets be considered identical
14.4 Facets in Detail
Every class F that conforms to the following two requirements can be used as a facet:
1. F derives publically from class locale::facet. It declares the copy constructor and the assignment operator to be private, thereby making it infeasible to copy or to assign facets
2. F has a publically accessible static member named id of type locale::id.
Some special implementation guidelines
1. All member functions are declared to be const
2. All public functions are nonvirtual and delegate each request to a protected virtual function.
Chapter 15. Allocators
15.1 Using Allocators as an Application Programmer
Beware that you don't mix elements with different allocators; otherwise, the behavior is undefined.
You can check whether two allocators use the same memory model by using operator ==.
To access the allocator, all types that are parameterized by an allocator provide the member function get_allocator().
15.2 Using Allocators as a Library Programmer
Allocators provide an interface to allocate, create, destroy, and deallocate objects
For the initialization of uninitialized memory the C++ standard library provides some convenience functions:
uninitialized_fill(beg,end,val)
uninitialized_fill_n(beg,num,val)
uninitialized_copy(beg,end,mem)
Raw Storage Iterators
class raw_storage_iterator is provided to iterate over uninitialized memory to initialize it.
Temporary Buffers
get_temporary_buffer() and return_temporary_buffer().
They are provided to handle uninitialized memory that is provided for short, temporary use inside a function
However, it is rather complicated to write exception-safe code with get_temporary_buffer() and return_temporary_buffer(), so they are usually no longer used in library implementations
15.3 The Default Allocator
The default allocator uses the global operators new and delete to allocate and deallocate memory
There is a strange definition of a template structure inside the allocator, called rebind. This template structure provides the ability that any allocator may allocate storage of another type indirectly.
rebind<> is useful if you implement a container and you have to allocate memory for a type that differs from the element's type
15.4 A User-Defined Allocator
Writing your own allocator is not very hard. The most important issue is how you allocate or deallocate the storage. The rest is more or less obvious.
Typically, the only things that differ from typical implementation are max_size(),allocate(), and deallocate().
15.6 Utilities for Uninitialized Memory in Detail
void uninitialized_fill (ForwardIterator beg, ForwardIterator end, const T& value)
void uninitialized_fill_n (ForwardIterator beg, Size num, const T& value)
ForwardIterator uninitialized_copy (InputIterator sourceBeg, InputIterator sourceEnd, ForwardIterator destBeg)
These function either succeeds or has no effect( strong exceptional safe!)
|
转播
