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

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.
    Manipulating containers with iterators is convenient and provides tremendous expressive power when combined with Standard Library algorithms.
  • algorithms
  • Standard Library algorithms are function templates that perform such common data manipulations as searching, sorting and comparing elements or entire containers.
    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.
    Such containers can store sets of values or key–value pairs.
    keys are maintained in sorted order.
    • 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.
    Stacks and queues are typically constrained versions of sequence containers.
    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.
The sequence containers and associative containers are collectively referred to as the first-class containers.

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
These types are considered near containers because they exhibit some, but not all, capabilities of the first-class containers.

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.
The common first-class container defined types inside each container class definition:
  • pointer
  • A pointer for the container’s element type.
  • iterator
  • An iterator that points to an element of the container’s element type.
Before using a Standard Library container, it’s important to ensure that the type of objects being stored in the container supports a minimum set of functionality.

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();
    }
}

15.7.3 priority_queue

15.8 Class bitset

15.9 Wrap-Up 697

留言

熱門文章