C++ HOW TO PROGRAM: Introducing the New C++14 Standard
C++ HOW TO PROGRAM
Introducing the New C++14 Standard
TENTH EDITION
Paul Deitel
Harvey Deitel
Introducing the New C++14 Standard
TENTH EDITION Paul Deitel
Harvey Deitel
15 Standard Library Containers and Iterators
15.1 Introduction
The Standard Library defines powerful, template-based, reusable components that implement many common data structures and algorithms used to process those data structures.This chapter introduces three key components of the Standard Library:
- containers (templatized data structures) Each container has associated member functions — a subset of these is defined and common in all containers.
- iterators Iterators, which have properties similar to those of pointers, are used to manipulate container elements.
- algorithms Standard Library algorithms are function templates that perform such common data manipulations as searching, sorting and comparing elements or entire containers.
Manipulating containers with iterators is convenient and provides tremendous expressive power when combined with Standard Library algorithms.
Each algorithm has minimum requirements for the kinds of iterators that can be used with it.
Iterators encapsulate the mechanisms used to traverse containers and access their elements. This encapsulation enables many of the algorithms to be applied to various containers independently of the underlying container implementation.
15.2 Introduction to Containers
The containers are divided into four major categories:- Sequence containers The sequence containers represent linear data structures (i.e., all of their elements are conceptually “lined up in a row”)
- array Fixed size. Direct access to any element.
- deque Rapid insertions and deletions at front or back. Direct access to any element.
- forward_list Singly linked list, rapid insertion and deletion anywhere. Added in C++11.
- list Doubly linked list, rapid insertion and deletion anywhere.
- vector Rapid insertions and deletions at back. Direct access to any element.
- Ordered associative containers Associative containers are nonlinear data structures that typically can locate elements stored in the containers quickly.
- set Rapid lookup, no duplicates allowed.
- multiset Rapid lookup, duplicates allowed.
- map One-to-one mapping, no duplicates allowed, rapid key-based lookup.
- multimap One-to-many mapping, duplicates allowed, rapid key-based lookup.
- Unordered associative containers
- unordered_set
- unordered_multiset
- unordered_map
- unordered_multimap
- Container adapters
- stack Last-in, first-out (LIFO).
- queue First-in, first-out (FIFO).
- priority_queue Highest-priority element is always the first element out.
Such containers can store sets of values or key–value pairs.
keys are maintained in sorted order.
For this reason, the Standard Library implements class templates stack , queue and priority_queue as container adapters that enable a program to view a sequence container in a constrained manner.
Class string supports the same functionality as a sequence container, but stores only character data.
There are other container types that are considered "near containers":
- bitset for maintaining sets of flag values and
- valarray for performing high-speed mathematical vector operations
Common Container Functions
Common member functions for most Standard Library containers,- empty() Returns true if there are no elements in the container; otherwise, returns false .
- insert() Inserts an item in the container.
- size() Returns the number of elements currently in the container.
- begin() Overloaded to return either an iterator or a const_iterator that refers to the first element of the container.
- end() Overloaded to return either an iterator or a const_iterator that refers to the next position after the end of the container.
- rbegin() The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the last element of the container.
- rend() The two versions of this function return either a reverse_iterator or a const_reverse_iterator that refers to the position before the first element of the container.
- erase() Removes one or more elements from the container.
- clear() Removes all elements from the container.
- pointer A pointer for the container’s element type.
- iterator An iterator that points to an element of the container’s element type.
15.3 Introduction to Iterators
Iterators have many similarities to pointers and are used to point to first-class container elements and for other purposes.Iterators hold state information sensitive to the particular containers on which they operate; thus, iterators are implemented for each type of container.
If iterator i points to a particular element, then
- ++i points to the “next” element.(Preincrement an iterator)
- *i refers to the element pointed by i
15.4 Introduction to Algorithms
For some or all of the sequence and associative containers, the Standard Library provides scores of algorithms you’ll use frequently to manipulate these containers.The algorithms operate on container elements only indirectly through iterators.
15.5 Sequence Containers
Performance Tip:- Insertion at the back of a vector is efficient.
- frequent insertions and deletions at both ends of a container normally use a deque
- frequent insertions and deletions in the middle and/or at the extremes of a container normally use a list
15.5.1 vector Sequence Container
Using vector s and Iterators
#include <vector> #include <iostream> using namespace std; int main( ) { vector<int> integers; integers.push_back(2); integers.push_back(3); integers.push_back(4); for (vector<int>::iterator ptr=integers.begin(); ptr != integers.end(); ptr++) cout << *ptr << " "; cout << endl; return 0; } $ ./test 2 3 4
vector Element-Manipulation Functions
#include <vector> #include <iostream> using namespace std; int main( ) { vector<int> values{1,2,3,4,5,6}; values[0] = 7; // set the 1st element values.insert(values.cbegin()+1, 22); // set element at teh 2nd position for (vector<int>::iterator ptr=values.begin(); ptr != values.end(); ptr++) cout << *ptr << " "; cout << endl; return 0; } $ ./test 7 22 2 3 4 5 6
15.5.2 list Sequence Container
15.5.3 deque Sequence Container
15.6 Associative Containers
The associative containers provide direct access to store and retrieve elements via keys.The unordered associative containers might offer better performance for cases in which it’s not necessary to maintain keys in sorted order.
The difference between set and map is: set is used to store only keys while map is used to store key value pairs.
15.6.1 multiset Associative Container
15.6.2 set Associative Container
A set must have unique keys. Therefore, if an attempt is made to insert a duplicate key into a set , the duplicate is ignored.
#include <set> #include <iostream> using namespace std; int main() { set<int> s1; s1.insert(2); s1.insert(5); s1.insert(3); s1.insert(6); cout << "Elements in set:"; for (auto it : s1) // wlak through in set cout << it << " "; cout << endl; return 0; } $ ./test Elements in set:2 3 5 6
15.6.3 multimap Associative Container
15.6.4 map Associative Container
With a map you specify the key and get back the associated value quickly. Providing the key in a map ’s subscript operator [] locates the value associated with that key in the map .
#include <map> #include <iostream> using namespace std; int main() { map<int, string> pairs; pairs[1] = "Bruce Lee"; // Insertion by key indexing pairs.insert({2, "Jerry Lee"}); // Direct pair insertion pairs.insert(make_pair(3, "Jay Lee")); // Insertion of pair by make_pair cout << "Elements in map:\n"; for ( map<int,string>::iterator it=pairs.begin(); it!=pairs.end(); ++it) cout << it->first << ":" << it->second << endl; for ( auto it=pairs.begin(); it!=pairs.end(); ++it) // Type Inference cout << it->first << ":" << it->second << endl; for ( auto it : pairs)// Range-based element loop cout << it.first << ":" << it.second << endl; return 0; } $ ./test Elements in map: 1:Bruce Lee 2:Jerry Lee 3:Jay Lee
15.7 Container Adapters
Container adapters are not first-class containers, they- do not provide the actual data-structure implementation
- do not support iterators
- provide member functions push() and pop() to insert and remove an element
15.7.1 stack Adapter
Class stack (from header <stack> ) enables insertions into and deletions from the underlying container at one end called the top.
#include <stack> #include <iostream> using namespace std; int main() { stack<int> values; values.push(1); values.push(3); while ( ! values.empty() ) { cout << values.top() << " "; values.pop(); } } $ ./test 3 1
15.7.2 queue Adapter
- front() is used to get a reference to the first element in the queue
- back() is used to get a reference to the last element in the queue
#include <queue> #include <iostream> using namespace std; int main() { queue<int> values; values.push(1); values.push(3); while ( ! values.empty() ) { cout << values.front() << " "; values.pop(); } }
留言