12月 30, 2021

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)
iterators

pointers

Manipulating containers with iterators

algorithms

algorithms

function templates

15.2 Introduction to Containers

The containers are divided into four major categories:

Sequence containers

array
deque
forward_list

Singly

list

Doubly

vector

Ordered associative containers

Associative

nonlinear

sets of values

key–value pairs

set
multiset
map
multimap

Unordered associative containers

unordered_set
unordered_multiset
unordered_map
unordered_multimap

Container adapters

stack
queue
priority_queue

Stacks

queues

stack

queue

priority_queue

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
valarray

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()
insert()
size()
begin()

iterator

const_iterator

the first element of the container

end()

iterator

const_iterator

after the end of the container

rbegin()

reverse_iterator

const_reverse_iterator

the last element of the container

rend()

reverse_iterator

const_reverse_iterator

before the first element of the container

erase()
clear()

The common first-class container defined types inside each container class definition:

pointer
iterator

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

搜尋此網誌

I'm Jay's father