Professional C__ - Marc Gregoire [180]
Regular Expressions
C++11 adds the concept of regular expressions to the standard library and are defined in the The Standard Template Library The standard template library (STL) supports various containers and algorithms. This section briefly introduces those containers and algorithms. Later chapters will provide the coding details for using them in your programs. STL Containers The STL provides implementations of commonly-used data structures such as linked lists and queues. When you use C++, you should not need to write such data structures again. The data structures are implemented using a concept called containers, which store information called elements, in a way that implements the data structure (linked list, queue, etc.) appropriately. Different data structures have different insertion, deletion, and access behavior and performance characteristics. It is important to be familiar with the data structures available so that you can choose the most appropriate one for any given task. All the containers in the STL are templates, so you can use them to store any type, from built-in types such as int and double to your own classes. Each container instance stores only objects of one type, that is, they are homogeneous collections. There is a new type in C++11 called tuples that allows fixed-sized heterogeneous collections of objects; but for ordinary containers, you need to store objects of one type and one type only. If you need non fixed-sized heterogeneous collections, you could create a class which has multiple subclasses, and each subclass could wrap an object of your required type. The C++ STL containers are homogenous: They allow elements of only one type in each container. Note that the C++ standard specifies the interface, but not the implementation, of each container and algorithm. Thus, different vendors are free to provide different implementations. However, the standard also specifies performance requirements as part of the interface, which the implementations must meet. This section provides an overview of the various containers available in the STL. vector A vector stores a sequence of elements and provides random access to these elements. You can think of a vector as an array of elements that grows dynamically as you insert elements and provides some bounds checking. Like an array, the elements of a vector are stored in contiguous memory. A vector in C++ is a synonym for a dynamic array: an array that grows and shrinks automatically in response to the number of elements it stores. vectors provide fast element insertion and deletion (amortized constant time) at the end of the vector. Amortized constant time insertion means that most of the time insertions are done in constant time O(1). However, sometimes the vector needs to grow in size to accommodate new elements which has a complexity of O(N). On average this results in O(1) complexity or amortized constant time. Details are explained in Chapter 12. A vector has slow (linear time) insertion and deletion anywhere else, because the operation must move all the elements “down” or “up” by one to make room for the new element or to fill the space left by the deleted element. Like arrays, vectors provide fast (constant time) access to any of their elements. You should use a vector in your programs when you need fast access to the elements, but do not plan to add or remove elements often. A good rule of thumb is to use a vector whenever you would have used an array. For example, a system-monitoring tool might keep a list of computer systems that it monitors in a vector. Only rarely would new computers be added to the list, or current computers