Movatterモバイル変換

• Table of Contents
• Previous Chapter
• Next Chapter

Chapter 12: Abstract Containers

The interesting part is that the kind of data that can be stored inside thesecontainers has been left unspecified at the time the containers wereconstructed. That's why they are spoken of asabstract containers.

Abstract containers rely heavily ontemplates, covered in chapter21 and beyond. To use abstract containers, only a minimal grasp ofthe template concept is required. InC++ a template is in fact a recipefor constructing a function or a complete class. The recipe tries to abstractthe functionality of the class or function as much as possible from the dataon which the class or function operates. As the data types on which thetemplates operate were not known when the template was implemented, thedatatypes are either inferred from the context in which a function template isused, or they are mentioned explicitly when a class template is used (the termthat's used here isinstantiated). In situations where the types areexplicitly mentioned, theangle bracket notation is used to indicatewhich data types are required. For example, below (in section12.2) we'llencounter thepair container, which requires theexplicit mentioning of two data types. Here is apair objectcontaining both anint and astring:

    pair<int, string> myPair;

The objectmyPair is defined as an object holding both anint andastring.

The angle bracket notation is used intensively in the upcomingdiscussion of abstract containers. Actually, understanding this part oftemplates is the only real requirement for using abstract containers. Nowthat we've introduced this notation, we can postpone the more thoroughdiscussion of templates to chapter21, and concentrate ontheir use in this chapter.

Most abstract containers aresequential containers: they containdata that can be stored and retrieved in some sequentialway. Examples are thearray, implementing a fixed-sized array; avector, implementing an extendable array; thelist, implementing a data structure that allows for the easy insertion ordeletion of data; thequeue, also called aFIFO (first in, first out) structure, in which the first element that isentered is the first element to be retrieved again; and thestack,which is afirst in, last out (FILO orLIFO) structure.

In addition to sequential containers several special containers areavailable. Thepair is a basic container in which a pair of values (oftypes that are left open for further specification) can be stored, like twostrings, two ints, a string and a double, etc.. Pairs are often used to returndata elements that naturally come in pairs. For example, themap is anabstract container storing keys and their associated values. Elementsof these maps are returned aspairs.

A variant of thepair is thecomplex container, implementingoperations that are defined on complex numbers.

Atuple (cf. section22.6) generalizes thepair container to adata structure accommodating any number of different data types.

All abstract containers described in this chapter as well as thestringand stream datatypes (cf. chapters5 and6) are part ofthe Standard Template Library.

All but the unordered containers support the following basic set of operators:

• Theoverloaded assignment operator, so we can assign twocontainers of the same types to each other. If the container's data typesupports move assignment, then assignment of an anonymous temporary containerto a destination container will use move assignment when assigning new valuesto the destination container's element. Overloaded assignment isalsosupported by the unordered containers;
• Tests for equality:== and!=Theequality operator applied to two containers returnstrue if the twocontainers have the same number of elements, which are pairwise equalaccording to the equality operator of the contained data type. Theinequality operator does the opposite;
• Ordering operators:<,<=,> and>=. The< operator returnstrue if each element in theleft-hand side container is less than each corresponding element in theright-hand side container. Additional elements in either the left-hand sidecontainer or the right-hand side container are ignored.

  container left;container right;left = {0, 2, 4};right = {1, 3};             // left < rightright = {1, 3, 6, 1, 2};    // left < right

• A default value (e.g., adefault constructor)
• Theequality operator (==)
• Theless-than operator (<)

Most containers (exceptions are thestack (section12.3.11),priority_queue (section12.3.5), andqueue (section12.3.4) containers) support members to determine their maximum sizes(through their member functionmax_size).

Virtually all containers support copy construction. If the containersupports copy construction and the container's data type supports moveconstruction, then move construction is automatically used for the container'sdata elements when a container is initialized with an anonymous temporarycontainer.

Closely linked to the standard template library are thegeneric algorithms. These algorithms may be used to performfrequently occurring tasks or more complex tasks than is possible with thecontainers themselves, like counting, filling, merging, filtering etc.. Anoverview of generic algorithms and their applications is given in chapter19. Generic algorithms usually rely on the availability ofiterators, representing begin andend-points for processing data stored inside containers. The abstractcontainers usually support constructors and members expecting iterators, andthey often have members returning iterators (comparable to thestring::begin andstring::end members). In this chapter theiterator concept is not further investigated. Refer to chapter18 forthis.

Containers often collect data during their lifetimes. When a containergoes out of scope, its destructor tries to destroy its data elements. Thisonly succeeds if the data elements themselves are stored inside thecontainer. If the data elements of containersare pointers to dynamically allocated memory then the memory pointed to bythese pointers is not destroyed, resulting in amemory leak. A consequenceof this scheme is that the data stored in a container should often beconsidered the `property' of the container: the container should be able todestroy its data elements when the container's destructor is called. So,normally containers should not contain pointers to data. Also, a containershould not be required to containconst data, asconst dataprevent the use of many of the container's members, like the assignmentoperator.

12.1: Notations used in this chapter

• Containers live in the standard namespace. In code examples this willbe clearly visible, but in the textstd:: is usually omitted.
• Acontainer without angle brackets represents any container ofthat type. Mentally add the required type inangle bracket notation. E.g.,pair may representpair<string,int>.
• The notationType represents thegeneric type.Type couldbeint,string, etc.
• Identifiersobject andcontainer represent objects of thecontainer type under discussion.
• The identifiervalue represents a value of the type that isstored in the container.
• Simple, one-letter identifiers, liken represent unsignedvalues.
• Longer identifiers representiterators. Examplesarepos,from,beyond

• The identifierkey indicates a value of the used key-type
• The identifierkeyvalue indicates a value of the `value_type'used with the particular container.

12.2: The `pair' container

Thepair's data types are specified when thepair object isdefined (or declared) using the template's angle bracket notation (cf. chapter21). Examples:

    pair<string, string> piper("PA28", "PH-ANI");    pair<string, string> cessna("C172", "PH-ANG");

here, the variablespiper andcessna are defined aspairvariables containing twostrings. Both strings can be retrieved using thefirst andsecond fields of thepair type:

    cout << piper.first << '\n' <<      // shows 'PA28'            cessna.second << '\n';      // shows 'PH-ANG'

Thefirst andsecond members can also be used to reassign values:

    cessna.first = "C152";    cessna.second = "PH-ANW";

If apair object must be completely reassigned, ananonymous pair object can be used as theright-hand operand ofthe assignment. An anonymous variable defines a temporary variable (whichreceives no name) solely for the purpose of (re)assigning another variable ofthe same type. Its generic form is

    type(initializer list)

Note that when apair object is used the type specification is notcompleted by just mentioning the containernamepair. It also requires thespecification of the data types which are stored within the pair. For this the(template)angle bracket notation is used again. E.g., the reassignmentof thecessna pair variable could have been accomplished as follows:

    cessna = pair<string, string>("C152", "PH-ANW");

In cases like these, thetype specification can become quiteelaborate, in which caseusing declarations can be used to improvereadability. If manypair<type1, type2> clauses areused in a source, the typing effort may be reduced and readability might beimproved by first defining a name for the clause, and then using the definedname later. E.g.,

    using pairStrStr = pair<string, string>;    cessna = pairStrStr("C152", "PH-ANW");

All abstract containers are class templates, and thetypes for which class templates are initialized are commonly specified betweenpointed brackets following the class template's name. However, the compilermay be able to deduce the container's types fromthe types of arguments that are specified when constructing thecontainer. E.g., when defining

    pair values{ 1, 1.5 };

the compiler deduces thatvalues.first is anint andvalues.second is adouble. Sometimes the class template's types cannotbe deduced. In those cases the intended types must explicitly be specified:

    pair<int, double> values;

Although the compiler will deduce types whenever it can, it might notdeduce the types we had in mind. Had we defined

    pair cessna{ "C172", "PH-BVL" };

then the compilation would succeed, but an expression likecout << cessna.first.length() would not compile, as"C172" isa NTBS, and hencecessna.first is achar *. In this case simplyappending ans to the NTBSs fixes the problem, but such a simple fix mightnot always be available. Section12.3.2 has contains more informationabout deducing template parameter types.

Apart from this (and the basic set of operations (assignment andcomparisons)) thepair offers no furtherfunctionality. It is, however,a basic ingredient of the upcoming abstract containersmap, multimap andhash_map.

C++ also offers ageneralized pair container: thetuple, coveredin section22.6.

12.3: Available Containers

12.3.1: The `array' container

To define astd::array both the data type of its elements and its sizemust be specified: the data type is given after an opening angle bracket,immediately following the `array' container name. The array's size isprovided after the data type specification. Finally, a closing angle bracketcompletes the array's type. Specifications like this are common practice withcontainers. The combination ofarray, type and size defines atype. As a result,array<string, 4> defines another type thanarray<string, 5>, and a function explicitly defining anarray<Type, N>parameter will not accept anarray<Type, M> argument ifN andMare unequal.

The array's size may may be defined as 0 (although such an array probably haslittle use as it cannot store any element). The elements of an array arestored contiguously. Ifarray<Type, N> arr has been defined, then&arr[n] + m == &arr[n + m], assuming than0 <= n < N and0 <= n + m< N.

The following constructors, operators, and member functions are available:

• Constructors:
  • The copy and move constructors are available;
  • Anarray may be constructed with a fixed numberN ofdefault elements:

    array<string, N> object;

  • An initial subset of the elements of an array may be initialized using a brace delimited initializer list:

    array<double, 4> dArr = {1.2, 2.4};

    HeredArr is defined as an array of 4 element, withdArr[0] anddArr[1] initialized to, respectively 1.2 and 2.4, anddArr[2] anddArr[3] initialized to 0. An attractive characteristic of arrays (andother containers) is that containers initializetheir data elements to the data type's default value. The data type'sdefault constructor is used for thisinitialization. With non-classdata types the value 0 is used. So, for anarray<double, 4> array we knowthat all but its explicitly initialized elements are initialized tozero.

• In addition to the standard operators for containers, thearraysupports theindex operator, which can be used to retrieve or reassignindividual elements of the array. Note that the elements which are indexedmust exist. For example, having defined an empty array a statement likeiarr[0] = 18 produces an error, as the array is empty. Note thatoperator[] doesnot respect itsarray bounds. If you want run-time array bound checking, use the array'sat member.
• Thearray class offers the following member functions:
  • Type &at(size_t idx):
    returns a reference to the array's element at index positionidx. Ifidx exceeds the array's size astd::out_of_range exception is thrown.
  • Type &back():
    returns a reference to the last element in the array. It is theresponsibility of the programmer to use the member only if the array is not empty.
  • array::iterator begin():
    returns aniterator pointing to the first element in the array, returningend if the array is empty.
  • array::const_iterator cbegin():
    returns aconst_iterator pointing to the first element in the array, returningcend if the array is empty.
  • array::const_iterator cend():
    returns aconst_iterator pointing just beyond the array's last element.
  • array::const_reverse_iterator crbegin():
    returns aconst_reverse_iterator pointing to the last element in the array, returningcrend if the array is empty.
  • array::const_reverse_iterator crend():
    returns aconst_reverse_iterator pointing just before the array's first element.
  • value_type *data():
    returns a pointer to the array's first data element. With a const array avalue_type const * is returned.
  • bool empty():
    returnstrue if the array contains no elements.
  • array::iterator end():
    returns an iterator pointing beyond the last element in the array.
  • void fill(Type const &item):
    fills all the array's elements with a copy ofitem
  • Type &front():
    returns a reference to the first element in the array. It is the responsibility of the programmer to use the member only if the array is not empty.
  • array::reverse_iterator rbegin():
    this member returns a reverse_iterator pointing to the last element in the array.
  • array::reverse_iterator rend():
    returns a reverse_iterator pointing before the first element in the array.
  • constexpr size_t size():
    returns the number of elements the array contains.
  • void swap(array<Type, N> &other):
    swaps the content of the current and other array. The array other's data type and size must be equal to the data type and size of the object callingswap.

• All its elements are immediately initialized;
• Introspection is possible (e.g.,size can be used);
• Thearray container can be used in the context of templates, there code is developed that operates on data types that become available only after the code itself has been developed;
• Sincearray supports reverse iterators, it can immediately be used with generic algorithms performing `reversed' operations (e.g., to perform a descending rather than ascending sort (cf. section19.1.54))

12.3.2: The `vector' container

The following constructors, operators, and member functions are available:

• Constructors:
  • The copy and move constructors are available;

  • Avector may be constructed empty:

    vector<string> object;

  • A vector may be initialized to a certain number of elements:

    vector<string> object(5, "Hello"s); // initialize to 5 Hello's,vector<string> container(10);       // and to 10 empty stringsvector<string> names = {"george", "frank", "tony", "karel"};

    Note the difference betweenvector<int> first(5) andvector<int>second{ 5 }. The vectorfirst contains five elements, initialized to 0,while the vectorsecond contains one element, initialized to 5. Referringback to section12.2: with the latter definition the compiler is able todeduce the vector's template parametertype (int), so the latter definition could also have been written asvector second{ 5 }.

    An ambiguity might be observed when looking at

    vector object{ vector{ 1 } };

    Did we define avector<int> or avector<vector<int>>? The standardconsiders this avector<int>: it is initialized using the vector's moveconstructor from an abstractvector<int>.

• A vector may be initialized using iterators. Toinitialize a vector with elements 5 until 10 (including the last one) of anexistingvector<string> the following construction may be used:

  extern vector<string> container;vector<string> object(&container[5], &container[11]);

  Note here that the last element pointed to by the second iterator(&container[11]) isnot stored inobject. This is a simpleexample of the use ofiterators, in which the usedrange of values starts at the first value, and includes all elements upto but not including the element to which the second iterator refers. Thestandard notation for this is[begin, end).

• In addition to the standard operators for containers, thevectorsupports the index operator, which can be used to retrieve or reassignindividual elements of the vector. Note that the elements which are indexedmust exist. For example, having defined an empty vector a statement likeivect[0] = 18 produces an error, as the vector is empty. So, the vectorisnot automatically expanded, andoperator[] doesnot respect itsarray bounds. In this case the vector should be resized first, orivect.push_back(18) should be used (see below). If you need run-time arraybound checking, use the vector'sat member.
• Thevector class offers the following member functions:
  • void assign(...):
    assigns new content to the vector:
    • assign(iterator begin, iterator end) assigns the values atthe iterator range[begin, end) to the vector;
    • assign(size_type n, value_type const &val) assignsncopies ofval to the vector;
    • assign(initializer_list<value_type> values) assigns thevalues in the initializer list to the vector.

  • Type &at(size_t idx):
    returns a reference to the vector's element atindex positionidx. Ifidx exceeds the vector's size astd::out_of_range exception is thrown.
  • Type &back():
    returns a reference to the last element in thevector. It is theresponsibility of the programmer to use the member onlyif the vector is not empty.
  • vector::iterator begin():
    returns an iterator pointing to the firstelement in the vector, returningend if the vector is empty.
  • size_t capacity():
    Number of elements for which memory has beenallocated. It returns at least the value returned bysize
  • vector::const_iterator cbegin():
    returns a const_iterator pointing to the firstelement in the vector, returningcend if the vector is empty.
  • vector::const_iterator cend():
    returns a const_iterator pointing just beyond thevector's last element.
  • void clear():
    erases all the vector's elements.
  • vector::const_reverse_iterator crbegin():
    returns a const_reverse_iterator pointing to the lastelement in the vector, returningcrend if the vector is empty.
  • vector::const_reverse_iterator crend():
    returns a const_reverse_iterator pointing just before thevector's first element.
  • value_type *data():
    returns a pointer to the vector's first data element.
  • iterator emplace(const_iterator position, Args &&...args):
    avalue_type object is constructed from the argumentsspecified afterposition, and the newly created element is inserted atposition. Different frominsert, which expects an existing object ofthe container's value type (and inserts the provided argument into the container) using copy or move construction orassignment,emplace uses its arguments toconstruct such an object immediately at the intended location of thecontainer, without requiring copy or move construction or assignment.
  • constexpr &emplace_back(Args &&...args):
    avalue_type object is constructed from the member'sarguments, and the newly created element is inserted beyond the vector's lastelement, returning a reference to the newly added element.
  • bool empty():
    returnstrue if the vector contains noelements.
  • vector::iterator end():
    returns an iterator pointing beyond the lastelement in the vector.
  • vector::iterator erase():
    erases a specific range of elements in the vector:
    • erase(pos) erases the element pointed to by the iteratorpos. The iterator++pos is returned.
    • erase(first, beyond) erases elements indicated by the iteratorrange[first, beyond), returningbeyond.

  • Type &front():
    returns a reference to the first element in thevector. It is the responsibility of the programmer to use the member only ifthe vector is not empty.
  • allocator_type get_allocator() const:
    returns acopy of the allocator object used by thevector object.
  • ... insert():
    elements may be inserted starting at a certain position. Thereturn value depends on the version ofinsert() that is called:
    • vector::iterator insert(pos) inserts a default value of typeType atpos,pos is returned.
    • vector::iterator insert(pos, value) insertsvalue atpos,pos is returned.
    • void insert(pos, first, beyond) inserts the elements in the iterator range[first, beyond).
    • void insert(pos, n, value) insertsn elements having valuevalue at positionpos.

  • size_t max_size():
    returns the maximum number ofelements thisvector may contain.
  • void pop_back():
    removes the last element from the vector. Avoid calling thismember on an empty vector: although nothing is returned its internallymaintained count of number of available elements is reduced, causing thevector'ssize() member to return the (when cast toint) value -1, andthen -2, etc., etc.
  • void push_back(value):
    addsvalue to the end of the vector.
  • vector::reverse_iterator rbegin():
    this member returns a reverse_iterator pointing to the lastelement in the vector.
  • vector::reverse_iterator rend():
    returns an iterator pointing before the first element in thevector.
  • void reserve(size_t request):
    ifrequest is less than or equal tocapacity, thiscall has no effect. Otherwise, it is a request to allocate additionalmemory. If the call is successful, thencapacity returns a value of atleastrequest. Otherwise,capacity is unchanged. In either case,size's return value won't change, until a function likeresize iscalled, actually changing the number of accessible elements.
  • void resize():
    can be used to alter the number of elements thatare currently stored in the vector:
    • resize(n, value) may be used to resize the vector to a sizeofn.Value is optional. If the vector is expanded andvalue isnot provided, the additional elements are initialized to thedefault valueof the used data type, otherwisevalue is used to initialize extraelements.

  • void shrink_to_fit():
    optionally reduces theamount of memory allocated by a vector to its current size. Theimplementor is free to ignore or otherwise optimize this request. In order toguarantee a `shrink to fit' operation the

    vector<Type>(vectorObject).swap(vectorObject)

    idiom can be used.

  • size_t size():
    returns the number of elements in the vector.
  • void swap(vector<Type> &other):
    swaps two vectors using identical data types. Example:

    #include <iostream>#include <vector>using namespace std;int main(){    vector<int> v1(7);    vector<int> v2(10);    v1.swap(v2);    cout << v1.size() << " " << v2.size() << '\n';}/*    Produced output:10 7*/

12.3.3: The `list' container

The organization of alist is shown in figure10.

As a subtlety note that the representation given in figure10 is notnecessarily used in actual implementations of the list. For example, considerthe following little program:

    int main()    {        list<int> l;        cout << "size: " << l.size() << ", first element: " <<                l.front() << '\n';    }

When this program is run it might actually produce the output:

    size: 0, first element: 0

Its front element can even be assigned a value. In this case theimplementor has chosen to provide the list with a hidden element. The listactually is acircular list, where the hidden element serves as terminatingelement, replacing the 0-pointers in figure10. As noted, this is asubtlety, which doesn't affect the conceptual notion of a list as a datastructure ending in 0-pointers. Note also that it is well known that variousimplementations of list-structures are possible (cf.Aho, A.V.,Hopcroft J.E. andUllman, J.D., (1983)Data Structures and Algorithms (Addison-Wesley)).

Both lists and vectors are often appropriate data structures in situationswhere an unknown number of data elements must bestored. However, there are some rules of thumb to followwhen selecting the appropriate data structure.

• When most accesses arerandom, avector is the preferred data structure. Example: in a program counting character frequencies in a textfile, avector<int> frequencies(256) is the datastructure of choice, as the values of the received characters can be used as indices into thefrequencies vector.
• The previous example illustrates a second rule of thumb, also favoring thevector: if the number of elements is known in advance (and does not notably change during the lifetime of the program), the vector is also preferred over the list.
• In cases whereinsertions ordeletions prevail and the data structure is large the list is generally preferred.

Other considerations related to the choice between lists and vectorsshould also be given some thought. Although it is true that the vector is ableto grow dynamically, thedynamic growth requires data-copying.Clearly, copying a million large data structures takes a considerable amountof time, even on fast computers. On the other hand, inserting a large numberof elements in a list doesn't require us tocopy non-involved data. Inserting a new element in a list merelyrequires us to juggle some pointers. In figure11 this is shown: anew element is inserted between the second and third element, creating a newlist of four elements.

Thelist container offers the following constructors, operators, andmember functions:

• Constructors:
  • The copy and move constructors are available;
  • Alist may be constructed empty:

    list<string> object;

    As with thevector, it is an error to refer to an element of anempty list.

  • A list may be initialized to a certain number of elements. By default, if the initialization value is not explicitly mentioned, the default value or default constructor for the actual data type is used. For example:

    list<string> object(5, "Hello"s); // initialize to 5 Hello'slist<string> container(10);       // and to 10 empty strings

  • A list may be initialized using a two iterators. To initialize a list with elements 5 until 10 (including the last one) of avector<string> the following construction may be used:

    extern vector<string> container;list<string> object(&container[5], &container[11]);

• Thelist does not offer specialized operators, apart from the standard operators for containers.
• The followingmember functions are available:
  • void assign(...):

    assigns new content to the list:

    • assign(iterator begin, iterator end) assigns the values at the iterator range[begin, end) to the list;
    • assign(size_type n, value_type const &val) assignsn copies ofval to the list;
  • Type &back():
    returns a reference to the last element in the list. It is theresponsibility of the programmer to use this member only if the list is not empty.
  • list::iterator begin():
    returns an iterator pointing to the first element in the list, returningend if the list is empty.
  • void clear():
    erases all elements from the list.
  • value_type &emplace_back(Args &&...args):
    avalue_type object is constructed from the member's arguments, and the newly created element is inserted beyond the last element of the list, returning a reference to the newly added element.
  • value_type &emplace_front(Args &&...args):
    avalue_type object is constructed from the member's arguments, and the newly created element is inserted before the first element of the list, returning a reference to the newly added element.
  • bool empty():
    returnstrue if the list contains no elements.
  • list::iterator end():
    returns an iterator pointing beyond the last element in the list.
  • list::iterator erase():
    erases a specific range of elements in the list:
    • erase(pos) erases the element pointed to bypos. The iterator++pos is returned.
    • erase(first, beyond) erases elements indicated by the iterator range[first, beyond).Beyond is returned.
  • Type &front():
    returns a reference to the first element in the list. It is the responsibility of the programmer to use this member only if the list is not empty.
  • allocator_type get_allocator() const:
    returns a copy of the allocator object used by thelist object.
  • ... insert():
    inserts elements into the list. The return value depends on the version ofinsert that is called:
    • list::iterator insert(pos) inserts a default value of typeType atpos,pos is returned.
    • list::iterator insert(pos, value) insertsvalue atpos,pos is returned.
    • void insert(pos, first, beyond) inserts the elements in the iterator range[first, beyond).
    • void insert(pos, n, value) insertsn elements having valuevalue at positionpos.
  • size_t max_size():
    returns the maximum number of elements thislist may contain.
  • void merge(list<Type> other):
    this member function assumes that the current and other lists are sorted (see below, the membersort). Based on that assumption, it inserts the elements ofother into the current list in such a way that the modified list remains sorted. If both list are not sorted, the resulting list will be ordered `as much as possible', given the initial ordering of the elements in the two lists.list<Type>::merge usesType::operator< to sort the data in the list, which operator must therefore be available. The next example illustrates the use of themerge member: the list `object' is not sorted, so the resulting list is ordered 'as much as possible'.

        #include <iostream>    #include <string>    #include <list>    using namespace std;    void showlist(list<string> &target)    {        for        (            list<string>::iterator from = target.begin();            from != target.end();            ++from        )            cout << *from << " ";        cout << '\n';    }    int main()    {        list<string> first;        list<string> second;        first.push_back("alpha"s);        first.push_back("bravo"s);        first.push_back("golf"s);        first.push_back("quebec"s);        second.push_back("oscar"s);        second.push_back("mike"s);        second.push_back("november"s);        second.push_back("zulu"s);        first.merge(second);        showlist(first);    }    // shows:    // alpha bravo golf oscar mike november quebec zulu

    A subtlety is thatmerge doesn't alter the list if the list itself is used as argument:object.merge(object) won't change the list `object'.
  • void pop_back():
    removes the last element from the list. The program aborts when called on anempty list.
  • void pop_front():
    removes the first element from the list. The program aborts when called on anempty list.
  • void push_back(value):
    addsvalue to the end of the list.
  • void push_front(value):
    addsvalue before the first element of the list.
  • list::reverse_iterator rbegin():
    returns a reverse_iterator pointing to the last element in the list.
  • void remove(value):
    removes all occurrences ofvalue from the list. In the following example, the two strings `Hello' are removed from the listobject:

        #include <iostream>    #include <string>    #include <list>    using namespace std;    int main()    {        list<string> object;        object.push_back("Hello"s);        object.push_back("World"s);        object.push_back("Hello"s);        object.push_back("World"s);        object.remove("Hello"s);        while (object.size())        {            cout << object.front() << '\n';            object.pop_front();        }    }    /*            Generated output:        World        World    */

  • void remove_if(Predicate pred):
    removes all occurrences from the list for which the predicate function or function objectpred returnstrue. For each of the objects stored in the list the predicate is called aspred(*iter), whereiter represents the iterator used internally byremove_if. If a functionpred is used, its prototype should bebool pred(value_type const &object).
  • list::reverse_iterator rend():
    this member returns a reverse_iterator pointing before the first element in the list.
  • void resize():
    alters the number of elements that are currently stored in the list:
    • resize(n, value) may be used to resize the list to a size ofn.Value is optional. If the list is expanded andvalue is not provided, the extra elements are initialized to thedefault value of the used data type, otherwisevalue is used to initialize extra elements.
  • void reverse():
    reverses the order of the elements in the list. The elementback becomesfront andvice versa.
  • size_t size():
    returns the number of elements in the list.
  • void sort():
    sorts the list. An example of its use is given at the description of theunique member function below.list<Type>::sort usesType::operator< to sort the data in the list, which must therefore be available.
  • void splice(pos, object):
    transfers the content ofobject to the current list, starting the insertion at the iterator positionpos of the object using thesplice member. Followingsplice,object is empty. For example:

    #include <iostream>#include <string>#include <list>using namespace std;int main(){    list<string> object;    object.push_front("Hello"s);    object.push_back("World"s);    list<string> argument(object);    object.splice(++object.begin(), argument);    cout << "Object contains " << object.size() << " elements, " <<            "Argument contains " << argument.size() <<            " elements,\n";    while (object.size())    {        cout << object.front() << '\n';        object.pop_front();    }}

    Alternatively,argument may be followed by an iterator ofargument, indicating the first element ofargument that should be spliced, or by two iteratorsbegin andend defining the iterator-range[begin, end) onargument that should be spliced intoobject.
  • void swap():
    swaps two lists using identical data types.
  • void unique():
    operating on a sorted list, this member function removes all consecutively identical elements from the list.list<Type>::unique usesType::operator== to identify identical data elements, which operator must therefore be available. Here's an example removing all multiply occurring words from the list:

        #include <iostream>    #include <string>    #include <list>    using namespace std;                            // see the merge() example    void showlist(list<string> &target)    {        for        (            list<string>::iterator from = target.begin();            from != target.end();            ++from        )            cout << *from << " ";        cout << '\n';    }    int main()    {        string            array[] =            {                "charlie",                "alpha",                "bravo",                "alpha"            };        list<string>            target            (                array, array + sizeof(array)                / sizeof(string)            );        cout << "Initially we have:\n";        showlist(target);        target.sort();        cout << "After sort() we have:\n";        showlist(target);        target.unique();        cout << "After unique() we have:\n";        showlist(target);    }    /*        Generated output:        Initially we have:        charlie alpha bravo alpha        After sort() we have:        alpha alpha bravo charlie        After unique() we have:        alpha bravo charlie    */

12.3.4: The `queue' container

A queue is depicted in figure13.

The following constructors, operators, and member functions are availablefor thequeue container:

• Constructors:
  • The copy and move constructors are available;
  • Aqueue may be constructed empty:

        queue<string> object;

    As with thevector, it is an error to refer to an element of anempty queue.

• Thequeue container only supports the basic container operators.
• The followingmember functions are available forqueues:
  • Type &back():
    returns areference to the last element in the queue. It is theresponsibility of the programmer to use the member only if the queue isnot empty.

  • value_type &emplace(Args &&...args):
    avalue_type object is constructed from the member's arguments, and the newly created element is inserted beyond the end of the queue, returning a reference to (or copy of) the newly added element.
  • bool empty():
    returnstrue if the queue contains no elements.
  • Type &front():
    returns areference to the first element in the queue. It is the responsibility of theprogrammer to use the member only if the queue is not empty.
  • void pop():
    removes the element at the front ofthe queue. Note that the element isnot returned by this member. Avoid calling this member on an empty queue: although nothing is returned itsinternally maintained count of number of available elements is reduced,causing the queue'ssize() member to return the (when cast toint)value -1, and then -2, etc., etc. One might wonder whypop returnsvoid, instead of a value of typeType(cf.front). One reason is found in the principles of good softwaredesign: functions should perform one task. Combining the removal and return ofthe removed element breaks this principle. Moreover, when this principle isabandonedpop's implementation is always flawed. Consider theprototypical implementation of apop member that is expected to return thequeue's front-value:

            Type queue::pop()        {            Type ret{ front() };            erase_front();            return ret;        }

    Sincequeue has no control overType's behavior the first statement(Type ret{ front() }) might throw. Although this still supports the'commit or roll-back' principle,queue cannot guarantee thatTypeoffers copy-construction. Hence,pop does not return the queue'sfront-value, but simply erases that element:

            Type queue::pop()        {            erase_front();        }

    Note thatpush doesn't require copy construction:push can also beimplemented when move-construction is supported. E.g.,

            void queue::push(Type &&tmp)        {            d_data.push_back(std::move(tmp));   // uses move construction        }

    Because of all this, we must first usefront and thenpop toobtain and remove the queue's front element.
  • void push(value):
    this memberaddsvalue to the back of the queue.
  • size_t size():
    returns thenumber of elements in the queue.

• repeatedly removing its front element;
• assigning an empty queue using the same data type to it;
• having its destructor called.

12.3.5: The `priority_queue' container

A priority queue is identical to aqueue, but allows the entry of dataelements according topriority rules. A real-life priority queue isfound, e.g., at airport check-in terminals. At a terminal the passengersnormally stand in line to wait for their turn to check in, but late passengersare usually allowed to jump the queue: they receive a higher priority thanother passengers.

The priority queue usesoperator< of the data type stored in thepriority queue to decide about the priority of the data elements. Thesmaller the value, thelower the priority. So, the priority queuecould be used to sort values while they arrive. A simple example of sucha priority queue application is the following program: it reads words fromcin and writes a sorted list of words tocout:

#include <iostream>#include <string>#include <queue>using namespace std;int main(){    priority_queue<string> q;    string word;    while (cin >> word)        q.push(word);    while (q.size())    {        cout << q.top() << '\n';        q.pop();    }}

Unfortunately, the words are listed in reversed order: because of theunderlying<-operator the words appearing later in theASCII-sequenceappear first in the priority queue. A solution to that problem is to define awrapper class around thestring datatype, reversingstring'soperator<. Here is the modified program:

#include <iostream>#include <string>#include <queue>class Text{    std::string d_s;    public:        Text(std::string const &str)        :            d_s(str)        {}        operator std::string const &() const        {            return d_s;        }        bool operator<(Text const &right) const        {            return d_s > right.d_s;        }};using namespace std;int main(){    priority_queue<Text> q;    string word;    while (cin >> word)        q.push(word);    while (q.size())    {        word = q.top();        cout << word << '\n';        q.pop();    }}

Other possibilities to achieve the same exist. One would be to store thecontent of the priority queue in, e.g., a vector, from which the elements canbe read in reversed order.

The following constructors, operators, and member functions are availablefor thepriority_queue container:

• Constructors:
  • The copy and move constructors are available;
  • Apriority_queue may be constructed empty:

    priority_queue<string> object;

• Thepriority_queue only supports the basic operators ofcontainers.
• The followingmember functions are available for priority queues:
  • bool empty():
    returnstrue if thepriority queue contains no elements.
  • void pop():
    removes the element at the top of the priorityqueue. Note that the element isnot returned by this member. As with thequeue avoid calling this member on an empty priority queue (cf. section12.3.4.)
  • void push(value):
    insertsvalue at theappropriate position in the priority queue.
  • size_t size():
    returns the number of elementsin the priority queue.
  • Type &top():
    returns a reference to the firstelement of the priority queue. It is the responsibility of the programmer to use the member only if the priorityqueue is not empty.

Note that the priority queue does not support iterators or an indexoperator. The only element that can be accessed is its top element. Apriority queue can be emptied by:

• repeatedly removing its top element;
• assigning an empty queue using the same data type to it;
• having its destructor called.

12.3.6: The `deque' container

Adeque is comparable to a queue, but it allows for reading andwriting at both ends. Actually, thedeque data type supports a lot morefunctionality than thequeue, as illustrated by the following overview ofavailable member functions. Adeque is a combination of avector andtwo queues, operating at both ends of the vector. In situations where randominsertions and the addition and/or removal of elements at one or both sides ofthe vector occurs frequently using adeque should be considered.

The following constructors, operators, and member functions are available fordeques:

• Constructors:
  • The copy and move constructors are available;
  • Adeque may be constructed empty:

    deque<string> object;

    As with thevector, it is an error to refer to an element of anempty deque.

  • A deque may be initialized to a certain number ofelements. By default, if the initialization value is not explicitly mentioned,the default value or default constructor for the actual data type is used. Forexample:

    deque<string> object(5, "Hello"s), // initialize to 5 Hello'sdeque<string> container(10);       // and to 10 empty strings

  • A deque may be initialized using two iterators. Toinitialize a deque with elements 5 until 10 (including the last one) of avector<string> the following construction may be used:

    extern vector<string> container;deque<string> object(&container[5], &container[11]);

• In addition to the standard operators for containers, the dequesupports the index operator, which may be used to retrieve or reassignrandom elements of the deque. Note that the indexed elements must exist.
• The following member functions are available for deques:
  • void assign(...):

    assigns new content to the deque:

    • assign(iterator begin, iterator end) assigns the values atthe iterator range[begin, end) to the deque;
    • assign(size_type n, value_type const &val) assignsncopies ofval to the deque;

  • Type &at(size_t idx):

    returns a reference to the deque's element at index positionidx. Ifidx exceeds the deque's size astd::out_of_range exceptionis thrown.

  • Type &back():
    returns areference to the last element in the deque. It is theresponsibility of the programmer to use the member only if the deque isnot empty.
  • deque::iterator begin():
    returns an iterator pointingto the first element in the deque.
  • deque::const_iterator cbegin():

    returns a const_iterator pointing to the firstelement in the deque, returningcend if the deque is empty.

  • deque::const_iterator cend():

    returns a const_iterator pointing just beyond thedeque's last element.

  • void clear():
    erases allelements in the deque.
  • deque::const_reverse_iterator crbegin():

    returns a const_reverse_iterator pointing to the lastelement in the deque, returningcrend if the deque is empty.

  • deque::const_reverse_iterator crend():

    returns a const_reverse_iterator pointing just before thedeque's first element.

  • iterator emplace(const_iterator position, Args &&...args)

    avalue_type object is constructed from the argumentsspecified afterposition, and the newly created element is inserted atposition.

  • void emplace_back(Args &&...args)

    avalue_type object is constructed from the member'sarguments, and the newly created element is inserted beyond the deque's lastelement.

  • void emplace_front(Args &&...args)

    avalue_type object is constructed from the member'sarguments, and the newly created element is inserted before the deque's firstelement.

  • bool empty():
    returnstrue if the deque contains no elements.
  • deque::iterator end():
    returns an iterator pointing beyondthe last element in the deque.
  • deque::iterator erase():
    the member canbe used to erase a specific range of elements in the deque:
    • erase(pos) erases the element pointed to bypos. Theiterator++pos is returned.
    • erase(first, beyond) erases elements indicated by the iteratorrange[first, beyond).Beyond is returned.
  • Type &front():
    returns areference to the first element in the deque. It is the responsibility of theprogrammer to use the member only if the deque is not empty.
  • allocator_type get_allocator() const:
    returns acopy of the allocator object used by thedeque object.

  • ... insert():
    inserts elements starting at a certainposition. The return value depends on the version ofinsert that iscalled:
    • deque::iterator insert(pos) inserts a default value of typeType atpos,pos is returned.
    • deque::iterator insert(pos, value) insertsvalue atpos,pos is returned.
    • void insert(pos, first, beyond) inserts the elements in the iterator range[first, beyond).
    • void insert(pos, n, value) insertsn elements having valuevalue starting at iterator positionpos.
  • size_t max_size():
    returns the maximum number ofelements thisdeque may contain.
  • void pop_back():
    removes the last element from thedeque. Avoid calling this member on an empty deque: although nothing isreturned its internally maintained count of number of available elements isreduced, causing the deque'ssize() member to return the (when cast toint) value -1, and then -2, etc., etc.
  • void pop_front():
    removes the first element from thedeque. Avoid calling this member on an empty deque: as withpop_back() itsinternally maintained count of number of available elements is reduced
  • void push_back(value):
    addsvalue to the end ofthe deque.
  • void push_front(value):
    addsvalue before thefirst element of the deque.
  • deque::reverse_iterator rbegin():
    returns a reverse_iterator pointing to the last element in thedeque.
  • deque::reverse_iterator rend():
    this member returns areverse_iterator pointing before the first element in the deque.
  • void resize():
    alters the number of elements that arecurrently stored in the deque:
    • resize(n, value) may be used to resize the deque to a size ofn.Value is optional. If the deque is expanded andvalue is notprovided, the additional elements are initialized to the default value of theused data type, otherwisevalue is used to initialize extra elements.
  • void shrink_to_fit():
    optionally reduces theamount of memory allocated by a deque to its current size. The implementor isfree to ignore or otherwise optimize this request. In order to guarantee a`shrink to fit' operationdeque<Type>(dequeObject).swap(dequeObject) idiomcan be used.
  • size_t size():
    returns thenumber of elements in the deque.
  • void swap(argument):
    swaps two deques using identical datatypes.

12.3.7: The `map' container

Amap is filled withkey, value pairs, which may be of anycontainer-accepted type. Since types are associated with both the key and thevalue, we must specifytwo types in the angle bracket notation, comparableto the specification we've seen with thepair container (cf. section12.2). The first type represents the key's type, the second typerepresents the value's type. Thekey is used to access its associatedinformation. Themap sorts the keys using theiroperator<, where thesmallest key values appears as first element in the map. For example, amap in which the key is astring and the value is adouble can bedefined as follows:

    map<string, double> object;

    map<KeyType, ValueType, std::less<KeyType>>

The two fundamental operations on maps are the storage ofkey, valuecombinations, and the retrieval of values, given their keys. The indexoperator using a key as the index, can be used for both. If the index operatoris used aslvalue, the expression'srvalue is inserted into themap. If it is used asrvalue, the key's associated value is retrieved.Each key can be stored only once in amap. If the same key is enteredagain, the new value replaces the formerly stored value, which is lost.

A specifickey, value combination can implicitly or explicitly be insertedinto amap. If explicit insertion is required, thekey, valuecombination must be constructed first. For this, everymap defines avalue_type which may be used to create values that can be stored in themap. For example, a value for amap<string, int> can be constructed asfollows:

    map<string, int>::value_type siValue{ "Hello", 1 };

Thevalue_type is associated with themap<string, int>: thetype of the key isstring, the type of the value isint. Anonymousvalue_type objects are also often used. E.g.,

    map<string, int>::value_type{ "Hello", 1 };

Instead of using the linemap<string, int>::value_type(...) over andover again, a using declaration is frequently used to reduce typing and toimprove readability:

    using StringIntValue = map<string, int>::value_type;

Now values for themap<string, int> may be specified this way:

    StringIntValue{ "Hello", 1 };

Alternatively,pairs may be used to representkey, valuecombinations used by maps:

    pair<string, int>{ "Hello", 1 };

12.3.7.1: The `map' constructors

• The copy and move constructors are available;
• Amap may be constructed empty:

  map<string, int> object;

  Note that the values stored in maps may be containers themselves. Forexample, the following defines amap in which the value is apair: acontainer nested under another container:

      map<string, pair<string, string>> object;

  Note the use of the twoconsecutive closing angle brackets, which does not result in ambiguitiesas their syntactical context differs from their use as binary operators inexpressions.

• A map may be initialized using two iterators. The iterators mayeither point tovalue_type values for the map to be constructed, or toplainpair objects. If pairs are used, theirfirst element representsthe type of the keys, and theirsecond element represents the type of thevalues. Example:

  pair<string, int> pa[] ={    pair<string,int>("one", 1),    pair<string,int>("two", 2),    pair<string,int>("three", 3),};map<string, int> object(&pa[0], &pa[3]);

  In this example,map<string, int>::value_type could have been writteninstead ofpair<string, int> as well.

  Ifbegin represents the first iterator that is used to construct a mapand ifend represents the second iterator,[begin, end) will beused to initialize the map. Maybe contrary to intuition, themapconstructor only entersnew keys. If the last element ofpa wouldhave been"one", 3, onlytwo elements would have entered themap:"one", 1 and"two", 2. The value"one", 3 would silently have beenignored.

  Themap receives its own copies of the data to which the iteratorspoint as illustrated by the following example:

      #include <iostream>    #include <map>    using namespace std;    class MyClass    {        public:            MyClass()            {                cout << "MyClass constructor\n";            }            MyClass(MyClass const &other)            {                cout << "MyClass copy constructor\n";            }            ~MyClass()            {                cout << "MyClass destructor\n";            }    };    int main()    {        pair<string, MyClass> pairs[] =        {            pair<string, MyClass>{ "one", MyClass{} }        };        cout << "pairs constructed\n";        map<string, MyClass> mapsm{ &pairs[0], &pairs[1] };        cout << "mapsm constructed\n";    }    /*        Generated output:    MyClass constructor    MyClass copy constructor    MyClass destructor    pairs constructed    MyClass copy constructor    mapsm constructed    MyClass destructor    MyClass destructor    */

  When tracing the output of this program, we see that, first, theconstructor of aMyClass object is called to initialize the anonymouselement of the arraypairs. This object is then copied into the firstelement of the arraypairs by the copy constructor. Next, the originalelement is not required anymore and is destroyed. At that point the arraypairs has been constructed. Thereupon, themap constructs a temporarypair object, which is used to construct the map element. Havingconstructed the map element, the temporarypair object isdestroyed. Eventually, when the program terminates, thepair elementstored in themap is destroyed too.

12.3.7.2: The `map' operators

The index operator may be used to retrieve or reassign individual elements ofthe map. The argument of the index operator is called akey.

If the provided key is not available in themap, a new data element isautomatically added to themap using the default value or defaultconstructor to initialize the value part of the new element. This defaultvalue is returned if the index operator is used as an rvalue.

When initializing a new or reassigning another element of the map, the type ofthe right-hand side of the assignment operator must be equal to (or promotableto) the type of the map's value part. E.g., to add or change the value ofelement"two" in a map, the following statement can be used:

    mapsm["two"] = MyClass{};

12.3.7.3: The `map' public members

• mapped_type &at(key_type const &key):
  returns a reference to the map'smapped_typeassociated withkey. If the key is not stored in themap anstd::out_of_range exception is thrown.
• map::iterator begin():
  returns an iterator pointing to thefirst element of the map.
• map::const_iterator cbegin():
  returns a const_iterator pointing to the firstelement in the map, returningcend if the map is empty.
• map::const_iterator cend():
  returns a const_iterator pointing just beyond themap's last element.
• void clear():
  erases all elements fromthe map.
• size_t count(key):
  returns 1 ifthe provided key is available in themap, otherwise 0 is returned.
• map::reverse_iterator crbegin() const:
  reverse_iterator returns a reverse_iterator pointing to the lastelement of the map.
• map::reverse_iterator crend():
  returns an iterator pointingbefore the first element of the map.
• pair<iterator, bool> emplace(Args &&...args):
  avalue_type object is constructed fromemplace'sarguments. If themap already contained an object using the samekey_type value, then astd::pair is returned containing an iteratorpointing to the object using the samekey_type value and the valuefalse. If no suchkey_type value was found, the newly constructedobject is inserted into themap, and the returnedstd::paircontains an iterator pointing to the newly insertedvalue_typeas well as the valuetrue.
• iterator emplace_hint(const_iterator position, Args &&...args):
  avalue_type object is constructed from the member'sarguments, and the newly created element is inserted into themap, unless the (atargs) provided key already exists. Theimplementation may or may not useposition as ahint to start lookingfor an insertion point. The returnediterator points to thevalue_typeusing the provided key. It may refer to an already existingvalue_type orto a newly addedvalue_type; an existingvalue_type is notreplaced. If a new valuewas added, then the container's size has beenincremented whenemplace_hint returns.
• bool empty():
  returnstrue ifthe map contains no elements.
• map::iterator end():
  returns an iterator pointing beyond thelast element of the map.
• pair<map::iterator, map::iterator> equal_range(key):
  thismember returns a pair of iterators, being respectively the return values ofthe member functionslower_bound andupper_bound, introduced below.An example illustrating these member functions is given at thediscussion of the member functionupper_bound.
• ... erase():
  erases a specific element or range of elementsfrom the map:
  • bool erase(key) erases the element having thegivenkey from themap.True is returned if the value was removed,false if the map did not contain an element using the givenkey.
  • void erase(pos) erases the element pointed to by the iteratorpos.
  • void erase(first, beyond) erases all elements indicated bythe iterator range[first, beyond).

• map::iterator find(key):
  returnsan iterator to the element having the given key. If the element isn'tavailable,end is returned. The following example illustrates the use ofthefind member function:

      #include <iostream>    #include <map>    using namespace std;    int main()    {        map<string, int> object;        object["one"] = 1;        map<string, int>::iterator it = object.find("one");        cout << "`one' " <<                (it == object.end() ? "not " : "") << "found\n";        it = object.find("three");        cout << "`three' " <<                (it == object.end() ? "not " : "") << "found\n";    }    /*        Generated output:    `one' found    `three' not found    */

• allocator_type get_allocator() const:
  returns acopy of the allocator object used by themap object.
• ... insert():
  inserts elements into the map. Valuesassociated with already existing keys, however, are not replaced by newvalues. Its return value depends on the version ofinsert that is called:
  • pair<map::iterator, bool> insert(keyvalue) insertsa newvalue_type into the map. The return value is apair<map::iterator, bool>. If the returnedbool field istrue,keyvalue was inserted into the map. The valuefalse indicates that thekey that was specified inkeyvalue was already available in the map, andsokeyvalue was not inserted into the map. In both cases themap::iterator field points to the data element having thekey that was specified inkeyvalue. The use of this variant ofinsert is illustrated by the following example:

        #include <iostream>    #include <string>    #include <map>    using namespace std;    int main()    {        pair<string, int> pa[] =        {            pair<string,int>("one", 10),            pair<string,int>("two", 20),            pair<string,int>("three", 30),        };        map<string, int> object(&pa[0], &pa[3]);                // {four, 40} and `true' is returned        pair<map<string, int>::iterator, bool>            ret = object.insert                    (                        map<string, int>::value_type                        ("four", 40)                    );        cout << boolalpha;        cout << ret.first->first << " " <<            ret.first->second << " " <<            ret.second << " " << object["four"] << '\n';                // {four, 40} and `false' is returned        ret = object.insert                    (                        map<string, int>::value_type                        ("four", 0)                    );        cout << ret.first->first << " " <<            ret.first->second << " " <<            ret.second << " " << object["four"] << '\n';    }    /*        Generated output:        four 40 true 40        four 40 false 40    */

    Note the somewhat peculiar constructions like

        cout << ret.first->first << " " << ret.first->second << ...

    Note that `ret' is equal to thepair returned by theinsert member function. Its `first' field is an iterator into themap<string, int>, so it can be considered a pointer to amap<string,int>::value_type. These value types themselves are pairs too, having`first' and `second' fields. Consequently, `ret.first->first' isthekey of the map value (astring), and `ret.first->second' isthevalue (anint).

  • map::iterator insert(pos, keyvalue). This way amap::value_type may also be inserted into the map.pos is ignored, andan iterator to the inserted element is returned.
  • void insert(first, beyond) inserts the (map::value_type)elements pointed to by the iterator range[first, beyond). Values thatwere already present are not replaced.

• key_compare key_comp():
  returns a copy of the object used by themap to compare keys. The typemap<KeyType, ValueType>::key_compare is defined by the map container andkey_compare's parameters have typesKeyType const &. The comparison function returnstrue if the first key argument should be ordered before the second key argument. To compare keysand values, usevalue_comp, listed below.
• map::iterator lower_bound(key):
  returns an iterator pointing to the firstkeyvalue element of which thekey is at least equal to the specifiedkey. If no such element exists, the function returnsend.
• size_t max_size():
  returns the maximum number ofelements thismap may contain.
• map::reverse_iterator rbegin():
  returns a reverse_iterator pointing to the last element of the map.
• map::reverse_iterator rend():
  returns an iterator pointingbefore the first element of the map.
• size_t size():
  returns thenumber of elements in the map.
• void swap(argument):
  swaps two maps using identical key/valuetypes.
• map::iterator upper_bound(key):
  returns an iterator pointing to the firstkeyvalue element having akey exceeding the specifiedkey. If nosuch element exists, the function returnsend. The followingexample illustrates the member functionsequal_range,lower_boundandupper_bound:

      #include <iostream>    #include <map>    using namespace std;    int main()    {        pair<string, int> pa[] =        {            pair<string,int>("one", 10),            pair<string,int>("two", 20),            pair<string,int>("three", 30),        };        map<string, int> object(&pa[0], &pa[3]);        map<string, int>::iterator it;        if ((it = object.lower_bound("tw")) != object.end())            cout << "lower-bound `tw' is available, it is: " <<                    it->first << '\n';        if (object.lower_bound("twoo") == object.end())            cout << "lower-bound `twoo' not available" << '\n';        cout << "lower-bound two: " <<                object.lower_bound("two")->first <<                " is available\n";        if ((it = object.upper_bound("tw")) != object.end())            cout << "upper-bound `tw' is available, it is: " <<                    it->first << '\n';        if (object.upper_bound("twoo") == object.end())            cout << "upper-bound `twoo' not available" << '\n';        if (object.upper_bound("two") == object.end())            cout << "upper-bound `two' not available" << '\n';        pair        <            map<string, int>::iterator,            map<string, int>::iterator        >            p = object.equal_range("two");        cout << "equal range: `first' points to " <<                    p.first->first << ", `second' is " <<            (                p.second == object.end() ?                    "not available"                :                    p.second->first            ) <<            '\n';    }    /*        Generated output:            lower-bound `tw' is available, it is: two            lower-bound `twoo' not available            lower-bound two: two is available            upper-bound `tw' is available, it is: two            upper-bound `twoo' not available            upper-bound `two' not available            equal range: `first' points to two, `second' is not available    */

• value_compare value_comp():
  returns a copy of the object used by themap to compare keys. The typemap<KeyType, ValueType>::value_compare is defined by the map container andvalue_compare's parameters have typesvalue_type const &. The comparison function returnstrue if the first key argument should be ordered before the second key argument. TheValue_Type elements of thevalue_type objects passed to this member are not used by the returned function.

12.3.7.4: The `map': a simple example

The following example illustrates how to make a simple table listing all keysand values found in a map:

    #include <iostream>    #include <iomanip>    #include <map>    using namespace std;    int main()    {        pair<string, int>            pa[] =            {                pair<string,int>("one", 10),                pair<string,int>("two", 20),                pair<string,int>("three", 30),            };        map<string, int>            object(&pa[0], &pa[3]);        for        (            map<string, int>::iterator it = object.begin();                it != object.end();                    ++it        )            cout << setw(5) << it->first.c_str() <<                    setw(5) << it->second << '\n';    }    /*        Generated output:      one   10    three   30      two   20    */

12.3.8: The `multimap' container

The main difference between themap and themultimap is that themultimap supports multiple values associated with the same key, whereas themap contains single-valued keys. Note that the multimap also accepts multipleidentical values associated with identical keys.

Themap and themultimap have the same set of constructors and memberfunctions, with the exception of theindex operator which is not supported with the multimap. This is understandable: ifmultiple entries of the same key are allowed, which of the possible valuesshould be returned forobject[key]?

Refer to section12.3.7 for an overview ofthemultimap member functions. Some member functions, however, deserveadditional attention when used in the context of themultimapcontainer. These members are discussed below.

• size_t map::count(key):
  returns thenumber of entries in the multimap associated with the givenkey.
• ... erase():
  erases elements from the map:
  • size_t erase(key) erases all elements having thegivenkey. The number of erased elements is returned.
  • void erase(pos) erases the single element pointed to bypos. Other elements possibly having the same keys are not erased.
  • void erase(first, beyond) erases all elements indicated bythe iterator range[first, beyond).

• pair<multimap::iterator, multimap::iterator> equal_range(key):
  returns a pair of iterators, being respectively the return values oflower_bound andupper_bound, introduced below. The function providesa simple means to determine all elements in themultimap that have thesamekeys. An example illustrating the use of these member functions isgiven at the end of this section.
• multimap::iterator find(key):
  thismember returns an iterator pointing to the first value whose key iskey. If the element isn't available,end is returned. Theiterator could be incremented to visit all elements having the samekeyuntil it is eitherend, or the iterator'sfirst member isnot equal tokey anymore.
• multimap::iterator insert():
  thismember function normally succeeds, and so amultimap::iterator isreturned, instead of apair<multimap::iterator, bool> as returned with themap container. The returned iterator points to the newly added element.

    #include <iostream>    #include <map>    using namespace std;    int main()    {        pair<string, int> pa[] =        {            pair<string,int>("alpha", 1),            pair<string,int>("bravo", 2),            pair<string,int>("charlie", 3),            pair<string,int>("bravo", 6),   // unordered `bravo' values            pair<string,int>("delta", 5),            pair<string,int>("bravo", 4),        };        multimap<string, int> object(&pa[0], &pa[6]);        using msiIterator = multimap<string, int>::iterator;        msiIterator it = object.lower_bound("brava");        cout << "Lower bound for `brava': " <<                it->first << ", " << it->second << '\n';        it = object.upper_bound("bravu");        cout << "Upper bound for `bravu': " <<                it->first << ", " << it->second << '\n';        pair<msiIterator, msiIterator>            itPair = object.equal_range("bravo");        cout << "Equal range for `bravo':\n";        for (it = itPair.first; it != itPair.second; ++it)            cout << it->first << ", " << it->second << '\n';        cout << "Upper bound: " << it->first << ", " << it->second << '\n';        cout << "Equal range for `brav':\n";        itPair = object.equal_range("brav");        for (it = itPair.first; it != itPair.second; ++it)            cout << it->first << ", " << it->second << '\n';        cout << "Upper bound: " << it->first << ", " << it->second << '\n';    }    /*        Generated output:        Lower bound for `brava': bravo, 2        Upper bound for `bravu': charlie, 3        Equal range for `bravo':        bravo, 2        bravo, 6        bravo, 4        Upper bound: charlie, 3        Equal range for `brav':        Upper bound: bravo, 2    */

• lower_bound andupper_bound produce the same result fornon-existing keys: they both return the first element having a key thatexceeds the provided key.
• Although the keys are ordered in themultimap, the values forequal keys are not ordered: they are retrieved in the order in which they wereentered.

12.3.9: The `set' container

A set contains unique values (of a container-acceptable type). Each valueis stored only once, and theset sorts its values using theiroperator<, where the smallest values appears as first element in the set.

A specific value can be explicitly created: Everyset defines avalue_type which may be used to create values that can be stored in theset. For example, a value for aset<string> can be constructed asfollows:

    set<string>::value_type setValue{ "Hello" };

Like thestd::map container, thestd::set also has an additionalparameter declaring the class that is used for comparing values in the set.For value typeValueType the set's type definition, therefore, looks likethis:

    set<ValueType, std::less<ValueType>>

Thevalue_type is associated with theset<string>. Anonymousvalue_type objects are also often used. E.g.,

    set<string>::value_type{ "Hello" };

Instead of using the lineset<string>::value_type(...) overand over again, a using declaration is often used to reduce typing and toimprove readability:

    using StringSetValue = set<string>::value_type;

Now values for theset<string> may be constructed as follows:

    StringSetValue{ "Hello" };

Alternatively, values of the set's type may be usedimmediately. In that case the value of typeType is implicitlyconverted to aset<Type>::value_type.

The following constructors, operators, and member functions are availablefor theset container:

• Constructors:
  • The copy and move constructors are available;
  • Aset may be constructed empty:

        set<int> object;

  • A set may be initialized using two iterators. For example:

        int intarr[] = {1, 2, 3, 4, 5};    set<int> object{ &intarr[0], &intarr[5] };

  Note that all values in the set must be different: it is not possible tostore the same value repeatedly when the set is constructed. If the same valueoccurs repeatedly, only the first instance of the value is entered into theset; the remaining values are silently ignored.

  Like themap, theset receives its own copy of the data itcontains.

• Theset container only supports the standard set of operatorsthat are available for containers.
• Theset class has the following member functions:
  • set::iterator begin():
    returns an iterator pointing tothe first element of the set. If the set is emptyend is returned.
  • void clear():
    erases all elements from the set.
  • size_t count(value):
    returns 1 ifthe specified value is available in theset, otherwise 0 is returned.
  • pair<iterator, bool> emplace(Args &&...args):
    avalue_type object is constructed from the member's arguments, and the newly created element is inserted into the set. The return value'ssecond member istrue if the element is inserted, andfalse if the element was already available. The pair'sfirst element is an iterator referring to the set's eement.
  • bool empty():
    returnstrue ifthe set contains no elements.
  • set::iterator end():
    returns an iterator pointing beyondthe last element of the set.
  • pair<set::iterator, set::iterator> equal_range(value):
    thismember returns a pair of iterators, being respectively the return values ofthe member functionslower_bound andupper_bound, introducedbelow.
  • ... erase():
    erases a specific element or range ofelements from the set:
    • bool erase(value) erases the element having the givenvalue from theset.True is returned if the value was removed,false if the set did not contain an element `value'.
    • void erase(pos) erases the element pointed to by the iteratorpos.
    • void erase(first, beyond) erases all elementsindicated by the iterator range[first, beyond).

  • set::iterator find(value):
    returnsan iterator to the element having the given value. If the element isn'tavailable,end is returned.
  • allocator_type get_allocator() const:
    returns acopy of the allocator object used by theset object.
  • ... insert():
    inserts elements into theset. If theelement already exists, the existing element is left untouched and the elementto be inserted is ignored. The return value depends on the version ofinsert that is called:
    • pair<set::iterator, bool> insert(value) insertsa newset::value_type into the set. The return value is apair<set::iterator, bool>. If the returnedbool field istrue,value was inserted into the set. The valuefalse indicates that thevalue that was specified was already available in the set, andso the providedvalue was not inserted into the set. In both cases theset::iterator field points to the data element in theset having thespecifiedvalue.
    • set::iterator insert(pos, value). This way aset::value_type may also be inserted into the set.pos is ignored, andan iterator to the inserted element is returned.
    • void insert(first, beyond) inserts the (set::value_type)elements pointed to by the iterator range[first, beyond) into theset. Values that were already present are not replaced.

  • key_compare key_comp():
    returns a copy of the object used by theset to compare keys. The type
    set<ValueType>::key_compare is defined by the set container andkey_compare's parameters have typesValueType const &. The comparison function returnstrue if its first argument should be ordered before its second argument.
  • set::iterator lower_bound(value):
    returns an iterator pointing to the firstvalue element of which thevalue is at least equal to the specifiedvalue. If no such element exists, the function returnsend.
  • size_t max_size():
    returns the maximum number of elements thisset may contain.
  • set::reverse_iterator rbegin():
    returns a reverse_iterator pointing to the last element of the set.
  • set::reverse_iterator rend:
    returns a reverse_iterator pointing before the first element of the set.
  • size_t size():
    returns the number of elements in the set.
  • void swap(argument):
    swaps two sets (argument beingthe second set) that use identical data types.
  • set::iterator upper_bound(value):
    returns an iterator pointing to the firstvalue element having avalue exceeding the specifiedvalue. If nosuch element exists, the function returnsend.
  • value_compare value_comp():
    returns a copy of the object used by theset to compare values. The type
    set<ValueType>::value_compare is defined by the set container andvalue_compare's parameters have typesValueType const &. The comparison function returnstrue if its first argument should be ordered before its second argument. Its operation is identical to that of akey_compare object, returned bykey_comp.

12.3.10: The `multiset' container

The main difference between theset and themultiset is that themultiset supports multiple entries of the same value, whereas thesetcontains unique values.

Theset and themultiset have the same set of constructors and memberfunctions. Refer to section12.3.9 for an overview of the member functionsthat can be used with themultiset. Some member functions, however,behave slightly different than their counterparts of thesetcontainer. Those members are:

• size_t count(value):
  returns the number ofentries in the multiset associated with the givenvalue.
• ... erase():
  erases elements from the set:
  • size_t erase(value) erases all elements having the givenvalue. The number of erased elements is returned.
  • void erase(pos) erases the element pointed to by the iteratorpos. Other elements possibly having the same values are not erased.
  • void erase(first, beyond) erases all elements indicated bythe iterator range[first, beyond).

• pair<multiset::iterator, multiset::iterator> equal_range(value):
  returns a pair of iterators, being respectively the return values oflower_bound andupper_bound, introduced below. The function providesa simple means to determine all elements in themultiset that have thesamevalues.
• multiset::iterator find(value):
  returns aniterator pointing to the first element having the specified value. If theelement isn't available,end is returned. The iterator could beincremented to visit all elements having the givenvalue until it iseitherend, or the iterator doesn't point to `value' anymore.
• ... insert():
  this member function normally succeeds andreturns amultiset::iterator rather than apair<multiset::iterator,bool> as returned with theset container. The returned iterator points tothe newly added element.

Here is an example showing the use of various member functions of amultiset:

    #include <iostream>    #include <set>    using namespace std;    int main()    {        string            sa[] =            {                "alpha",                "echo",                "hotel",                "mike",                "romeo"            };        multiset<string>            object(&sa[0], &sa[5]);        object.insert("echo");        object.insert("echo");        multiset<string>::iterator            it = object.find("echo");        for (; it != object.end(); ++it)            cout << *it << " ";        cout << '\n';        cout << "Multiset::equal_range(\"ech\")\n";        pair        <            multiset<string>::iterator,            multiset<string>::iterator        >            itpair = object.equal_range("ech");        if (itpair.first != object.end())            cout << "lower_bound() points at " << *itpair.first << '\n';        for (; itpair.first != itpair.second; ++itpair.first)            cout << *itpair.first << " ";        cout << '\n' <<                object.count("ech") << " occurrences of 'ech'" << '\n';        cout << "Multiset::equal_range(\"echo\")\n";        itpair = object.equal_range("echo");        for (; itpair.first != itpair.second; ++itpair.first)            cout << *itpair.first << " ";        cout << '\n' <<                object.count("echo") << " occurrences of 'echo'" << '\n';        cout << "Multiset::equal_range(\"echoo\")\n";        itpair = object.equal_range("echoo");        for (; itpair.first != itpair.second; ++itpair.first)            cout << *itpair.first << " ";        cout << '\n' <<                object.count("echoo") << " occurrences of 'echoo'" << '\n';    }    /*        Generated output:        echo echo echo hotel mike romeo        Multiset::equal_range("ech")        lower_bound() points at echo        0 occurrences of 'ech'        Multiset::equal_range("echo")        echo echo echo        3 occurrences of 'echo'        Multiset::equal_range("echoo")        0 occurrences of 'echoo'    */

12.3.11: The `stack' container

A stack is also called afirst in, last out (FILO orLIFO) datastructure as the first item to enter the stack is the last item to leave. Astack is an extremely useful data structure in situations where data musttemporarily remain available. For example, programs maintain a stack to storelocal variables of functions: the lifetime of these variables is determined bythe time these functions are active, contrary to global (or static local)variables, which live for as long as the program itself lives. Another exampleis found in calculators using theReverse Polish Notation (RPN), in which the operands of operators arekept in a stack, whereas operators pop their operands off the stack andpush the results of their work back onto the stack.

As an example of the use of a stack, consider figure14, in whichthe content of the stack is shown while the expression(3 + 4) * 2 isevaluated. In the RPN this expression becomes3 4 + 2 *, and figure14 shows the stack content after eachtoken (i.e., theoperands and the operators) is read from the input. Notice that each operandis indeed pushed on the stack, while each operator changes the content of thestack.

From figure14 we see that a stack has one location (thetop)where items can be pushed onto and popped off the stack. This top element isthe stack's only immediately visible element. It may be accessed and modifieddirectly.

Bearing this model of the stack in mind, let's see what we formally can dowith thestack container. For thestack, the following constructors,operators, and member functions are available:

• Constructors:
  • The copy and move constructors are available;
  • Astack may be constructed empty:

    stack<string> object;

• Only the basic set of container operators are supported by thestack
• The following member functions are available for stacks:
  • value_type &emplace(Args &&...args):
    avalue_type object is constructed from the member's arguments, and the newly created element is pushed on the stack. The return value is a reference to (or copy of) the newly pushed value.
  • bool empty():
    thismember returnstrue if the stack contains no elements.
  • void pop():
    removes the element at the top of thestack. Note that the popped element isnot returned by this member.Refer to section12.3.4 for a discussion about the reason whypop hasreturn typevoid and whypop should not be called on an emptystack.
  • void push(value):
    placesvalue at the top of the stack, hiding the other elements from view.
  • size_t size():
    thismember returns the number of elements in the stack.
  • Type &top():
    this memberreturns a reference to the stack's top (and only visible) element. It is theresponsibility of the programmer to use this member only if the stackis not empty.

The stack does not support iterators or an indexoperator. The only elements that can be accessed is its top element. To empty a stack:

• repeatedly remove its front element;
• assign an empty stack to it;
• have its destructor called (e.g., by ending its lifetime).

12.3.12: The `unordered_map' container (`hash table')

Before usingunordered_map orunordered_multimap containers the headerfile<unordered_map> must be included.

Theunordered_map class implements anassociative array in which theelements are stored according to somehashing scheme. As discussed, themap is a sorted data structure. The keys in maps are sorted using theoperator< of the key's data type. Generally, this is not the fastest wayto either store or retrieve data. The main benefit of sorting is that alisting of sorted keys appeals more to humans than an unsorted list. However,a by far faster way to store and retrieve data is to usehashing.

Hashing uses a function (called thehash function) to compute an(unsigned) number from the key, which number is thereupon used as an index inthe table storing the keys and their values. This number is called thebucket number. Retrieval of a key is as simple as computing thehash value of the provided key, and looking in the table at the computedindex location: if the key is present, it is stored in the table, at thecomputed bucket location and its value can be returned. If it's not present,the key is not currently stored in the container.

Collisions occur when a computed index position is alreadyoccupied by another element. For these situations the abstract containers havesolutions available. A simple solution, used byunordered_maps, consistsof usinglinear chaining, which uses linked list to store colliding tableelements.

The termunordered_map is used rather thanhash to avoid namecollisions with hash tables developed before they were added to the language.

Because of the hashing method, theefficiency of aunordered_map interms of speed should greatly exceed the efficiency of themap. Comparableconclusions may be drawn for theunordered_set, theunordered_multimapand theunordered_multiset.

12.3.12.1: The `unordered_map' constructors

• aKeyType (becomingunordered_map::key_type),
• aValueType (becomingunordered_map::mapped_type),
• the type of an object computing a hash value from a key value (becomingunordered_map::hasher), and
• the type of an object that can compare two keys for equality (becomingunordered_map::key_equal).
• the type of its allocator. This is usually left unspecified, using the allocator provided by default by the implementor.

The generic definition of anunordered_map container looks like this:

    std::unordered_map <KeyType, ValueType, hash type, predicate type,                        allocator type>

WhenKeyType isstd::string or a built-in type then default typesare available for the hash type and the predicate type. In practice theallocator type is not specified, as the default allocator suffices. In thesecases anunordered_map object can be defined by merely specifying the key-and value types, like this:

    std::unordered_map<std::string, ValueType> hash(size_t size = implSize);

Here,implSize is the container's default initial size, which isspecified by the implementor. The map's size is automatically enlarged by theunordered_map when necessary, in which case the containerrehashes allits elements. In practice the defaultsize argument provided by theimplementor is completely satisfactory.

TheKeyType frequently consists of text. So, aunordered_map using astd::string KeyType is frequently used. Be careful not to use a plainchar const * key_type as twochar const * values pointing to equalC-strings stored at different locations are considered to be differentkeys, as their pointer values rather than their textual content arecompared. Here is an example showing how achar const * KeyType can beused. Note that in the example no arguments are specified when constructingmonths, since default values and constructors are available:

    #include <unordered_map>    #include <iostream>    #include <string>    #include <cstring>    using namespace std;    struct EqualCp    {        bool operator()(char const *l, char const *r) const        {            return strcmp(l, r) == 0;        }    };    struct HashCp    {        size_t operator()(char const *str) const        {            return std::hash<std::string>()(str);        }    };    int main()    {        unordered_map<char const *, int, HashCp, EqualCp> months;        // or explicitly:            unordered_map<char const *, int, HashCp, EqualCp>                                      monthsTwo(61, HashCp(), EqualCp());        months["april"] = 30;        months["november"] = 31;        string apr("april");    // different pointers, same string        cout << "april     -> " << months["april"] << '\n' <<                "april     -> " << months[apr.c_str()] << '\n';    }

If otherKeyTypes must be used, then theunordered_map's constructorrequires (constant references to) a hash function object, computing a hashvalue from a key value, and a predicate function object, returningtrue iftwounordered_map::key_type objects are identical. Agenericalgorithm (see chapter19) exists performing tests of equality(i.e.,equal_to). These tests can be used if the key's data type supportsthe equality operator. Alternatively, an overloadedoperator== orspecializedfunction object could be constructed returningtrue if twokeys are equal andfalse otherwise.

Constructors

Theunordered_map supports the following constructors:

• The copy and move constructors are available;
• explicit unordered_map(size_type n = implSize, hasher const &hf = hasher(),
key_equal const &eql = key_equal(),
allocator_type const &alloc = allocator_type()): this constructor can also be used as default constructor;
• unordered_map(const_iterator begin, const_iterator end, size_type n = implSize, hasher const &hf = hasher(), key_equal const &eql = key_equal(), allocator_type const &alloc = allocator_type()): this constructor expects two iterators specifyinga range ofunordered_map::value_type const objects, and
• unordered_map(initializer_list<value_type> initList, size_type n = implSize, hasher const &hf = hasher(), key_equal const &eql = key_equal(), allocator_type const &alloc = allocator_type()): a constructor expecting aninitializer_list ofunordered_map::value_type values.

The following example shows a program using an unordered_map containingthe names of the months of the year and the number of days these months(usually) have. Then, using the subscript operator the days in several monthsare displayed (the predicate used here is the generic algorithmequal_to<string>, which is provided by the compiler as the default fourthargument of theunordered_map constructor):

    #include <unordered_map>    #include <iostream>    #include <string>    using namespace std;    int main()    {        unordered_map<string, int> months;        months["january"] = 31;        months["february"] = 28;        months["march"] = 31;        months["april"] = 30;        months["may"] = 31;        months["june"] = 30;        months["july"] = 31;        months["august"] = 31;        months["september"] = 30;        months["october"] = 31;        months["november"] = 30;        months["december"] = 31;        cout << "september -> " << months["september"] << '\n' <<                "april     -> " << months["april"] << '\n' <<                "june      -> " << months["june"] << '\n' <<                "november  -> " << months["november"] << '\n';    }    /*        Generated output:    september -> 30    april     -> 30    june      -> 30    november  -> 30    */

12.3.12.2: The `unordered_map' public members

Theunordered_map provides the following member functions (key_type,value_type etc. refer to the types defined by theunordered_map):

• mapped_type &at(key_type const &key):
  returns a reference to the unordered_map'smapped_typeassociated withkey. If the key is not stored in theunordered_map astd::out_of_range exception is thrown.
• unordered_map::iterator begin():
  returns aniterator pointing to the firstelement in the unordered_map, returningend if the unordered_map is empty.
• size_t bucket(key_type const &key):
  returns the index location wherekey is stored. Ifkey wasn't stored yetbucket addsvalue_type(key, Value()) beforereturning its index position.
• size_t bucket_count():
  returns the number of slots used by the containers. Each slot maycontain one (or more, in case of collisions)value_type objects.
• size_t bucket_size(size_t index):
  returns the number ofvalue_type objects stored at bucketpositionindex.
• unordered_map::const_iterator cbegin():
  returns aconst_iterator pointing to the firstelement in the unordered_map, returningcend if the unordered_map is empty.
• unordered_map::const_iterator cend():
  returns aconst_iterator pointing just beyond theunordered_map's last element.
• void clear():
  erases all the unordered_map's elements.
• size_t count(key_type const &key):
  returns the number of times avalue_type object usingkey_typekey is stored in theunordered_map (which is either oneor zero).
• pair<iterator, bool> emplace(Args &&...args):
  avalue_type object is constructed fromemplace'sarguments. If theunordered_map already contained an object using the samekey_type value, then astd::pair is returned containing an iteratorpointing to the object using the samekey_type value and the valuefalse. If no suchkey_type value was found, the newly constructedobject is inserted into theunordered_map, and the returnedstd::paircontains an iterator pointing to the newly inserted insertedvalue_typeas well as the valuetrue.
• iterator emplace_hint(const_iterator position, Args &&...args):
  avalue_type object is constructed from the member'sarguments, and the newly created element is inserted into theunordered_map, unless the (atargs) provided key already exists. Theimplementation may or may not useposition as ahint to start lookingfor an insertion point. The returnediterator points to thevalue_typeusing the provided key. It may refer to an already existingvalue_type orto a newly addedvalue_type; an existingvalue_type is notreplaced. If a new valuewas added, then the container's size has beenincremented whenemplace_hint returns.
• bool empty():
  returnstrue if the unordered_map contains no elements.
• unordered_map::iterator end():
  returns an iterator pointing beyond the last element in theunordered_map.
• pair<iterator, iterator> equal_range(key):
  thismember returns a pair of iterators defining the range of elements having akey that is equal tokey. With theunordered_map this range includesat most one element.
• unordered_map::iterator erase():
  erases a specific range of elements in the unordered_map:
  • bool erase(key) erases the element having thegivenkey from themap.True is returned if the value was removed,false if the map did not contain an element using the givenkey.
  • erase(pos) erases the element pointed to by the iteratorpos. The iterator++pos is returned.
  • erase(first, beyond) erases elements indicated by the iteratorrange[first, beyond), returningbeyond.

• iterator find(key):
  returns an iterator to the element having the given key. If theelement isn't available,end is returned.
• allocator_type get_allocator() const:
  returns acopy of the allocator object used by theunordered_map object.
• hasher hash_function() const:
  returns a copy ofthe hash function object used by theunordered_map object.
• ... insert():

  elements may be inserted starting at a certain position. Noinsertion is performed if the provided key is already in use. The return valuedepends on the version ofinsert() that is called. When apair<iterator, bool> is returned, then thepair's first member is aniterator pointing to the element having a key that is equal to the key of theprovidedvalue_type, thepair's second member istrue ifvaluewas actually inserted into the container, andfalse if not.

  • pair<iterator, bool> insert(value_type const &value) attempts to insertvalue.
  • pair<iterator, bool> insert(value_type &&tmp) attempts to insertvalue usingvalue_type's move constructor.
  • pair<iterator, bool> insert(const_iterator hint, value_typeconst &value) attempts to insertvalue, possibly usinghint as astarting point when trying to insertvalue.
  • pair<iterator, bool> insert(const_iterator hint, value_type&&tmp) attempts to insert avalue usingvalue_type's moveconstructor, and possibly usinghint as a starting point when trying toinsertvalue.
  • void insert(first, beyond) tries to insert the elements inthe iterator range[first, beyond).
  • void insert(initializer_list <value_type> iniList) attempts to insert the elements ininiList into thecontainer.

• hasher key_eq() const:
  returns a copy ofthekey_equal function object used by theunordered_map object.
• float load_factor() const:
  returns the container'scurrent load factor, i.e.size / bucket_count.
• size_t max_bucket_count():
  returns the maximumnumber of buckets thisunordered_map may contain.
• float max_load_factor() const:
  identical toload_factor.
• void max_load_factor(float max):
  changes thecurrent maximum load factor tomax. When a load factor ofmax isreached, the container will enlarge itsbucket_count, followed by a rehashof its elements. Note that the container's default maximum load factor equals1.0
• size_t max_size():
  returns the maximum number ofelements thisunordered_map may contain.
• void rehash(size_t size):
  ifsize exceeds the current bucket count, then the bucketcount is increased tosize, followed by a rehash of its elements.
• void reserve(size_t request):
  ifrequest is less than or equal to the current bucket count,this call has no effect. Otherwise, the bucket count is increased to a valueof at leastrequest, followed by a rehash of the container's elements.
• size_t size():
  returns the number of elements in the unordered_map.
• void swap(unordered_map &other):
  swaps the content of the current and the otherunordered_map.

12.3.12.3: The `unordered_multimap' container

Theunordered_multimap does not offeroperator[] and does not offerat members.

Below all members are described whose behavior differs from the behavior ofthe correspondingunordered_map members:

• at

  not supported by theunordered_multimap container

• size_t count(key_type const &key):
  returns the number of times avalue_type object usingkey_typekey is stored in theunordered_map. This member iscommonly used to verify whetherkey is available in theunordered_multimap.
• iterator emplace(Args &&...args):
  avalue_type object is constructed fromemplace'sarguments. The returnediterator points to the newly inserted insertedvalue_type.
• iterator emplace_hint(const_iterator position, Args &&...args):
  avalue_type object is constructed from the member'sarguments, and the newly created element is inserted into theunordered_multimap. Theimplementation may or may not useposition as ahint to start lookingfor an insertion point. The returnediterator points to thevalue_typeusing the provided key.
• pair<iterator, iterator> equal_range(key):
  thismember returns a pair of iterators defining the range of elements having akey that is equal tokey.
• iterator find(key):
  returns an iterator to an element having the given key. If nosuch element is available,end is returned.
• ... insert():

  elements may be inserted starting at a certain position. Thereturn value depends on the version ofinsert() that is called. When aniterator is returned, then it points to the element that was inserted.

  • iterator insert(value_type const &value) insertsvalue.
  • iterator insert(value_type &&tmp) insertsvalue usingvalue_type's move constructor.
  • iterator insert(const_iterator hint, value_type const &value) insertsvalue, possibly usinghint as astarting point when trying to insertvalue.
  • iterator insert(const_iterator hint, value_type &&tmp) insertsvalue usingvalue_type's moveconstructor, and possibly usinghint as a starting point when trying toinsertvalue.
  • void insert(first, beyond) inserts the elements inthe iterator range[first, beyond).
  • void insert(initializer_list <value_type> iniList) inserts the elements ininiList into the container.

12.3.13: The `unordered_set' container

Before using these hash-based set containers the header file<unordered_set> must be included.

Elements stored in theunordered_set are immutable, but they can beinserted and removed from the container. Different from theunordered_map,theunordered_set does not use aValueType. The set merely storeselements, and the stored element itself is its own key.

Theunordered_set has the same constructors as theunordered_map, butthe set'svalue_type is equal to itskey_type.

When defining anunordered_set type four template arguments must bespecified :

• aKeyType (becomingunordered_set::key_type),
• the type of an object computing a hash value from a key value (becomingunordered_set::hasher), and
• the type of an object that can compare two keys for equality (becomingunordered_set::key_equal).
• the type of its allocator. This is usually left unspecified, using the allocator provided by default by the implementor.

The generic definition of anunordered_set container looks like this:

    std::unordered_set <KeyType, hash type, predicate type, allocator type>

WhenKeyType isstd::string or a built-in type then default typesare available for the hash type and the predicate type. In practice theallocator type is not specified, as the default allocator suffices. In thesecases anunordered_set object can be defined by merely specifying the key-and value types, like this:

    std::unordered_set<std::string> rawSet(size_t size = implSize);

Here,implSize is the container's default initial size, which isspecified by the implementor. The set's size is automatically enlarged whennecessary, in which case the containerrehashes all its elements. Inpractice the defaultsize argument provided by the implementor iscompletely satisfactory.

Theunordered_set supports the following constructors:

• The copy and move constructors are available;
• explicit unordered_set(size_type n = implSize, hasher const &hf = hasher(),
key_equal const &eql = key_equal(),
allocator_type const &alloc = allocator_type()): this constructor can also be used as default constructor;
• unordered_set(const_iterator begin, const_iterator end, size_type n = implSize, hasher const &hf = hasher(), key_equal const &eql = key_equal(), allocator_type const &alloc = allocator_type()): this constructor expects two iterators specifyinga range ofunordered_set::value_type const objects, and
• unordered_set(initializer_list<value_type> initList, size_type n = implSize, hasher const &hf = hasher(), key_equal const &eql = key_equal(), allocator_type const &alloc = allocator_type()): a constructor expecting aninitializer_list ofunordered_set::value_type values.

Theunordered_set does not offer an index operator, and it does not offeranat member. Other than those, it offers the same members as theunordered_map. Below the members whose behavior differs from the behaviorof theunordered_map are discussed. For a description of the remainingmembers, please refer to section12.3.12.2.

• iterator emplace(Args &&...args):
  avalue_type object is constructed fromemplace'sarguments. It is added to the set if it is unique, and an iterator to thevalue_type is returned.
• iterator emplace_hint(const_iterator position, Args &&...args):
  avalue_type object is constructed from the member'sarguments, and if the newly created element is unique it is inserted into theunordered_set. Theimplementation may or may not useposition as ahint to start lookingfor an insertion point. The returnediterator points to thevalue_type.
• unordered_set::iterator erase():
  erases a specific range of elements in the unordered_set:
  • erase(key_type const &key) eraseskey from the set. Itreturns 1 if thekey was removed and 0 if thekey wasn't available inthe set.
  • erase(pos) erases the element pointed to by the iteratorpos. The iterator++pos is returned.
  • erase(first, beyond) erases elements indicated by the iteratorrange[first, beyond), returningbeyond.

12.3.13.1: The `unordered_multiset' container

Below all members are described whose behavior differs from the behavior ofthe correspondingunordered_set members:

• size_t count(key_type const &key):
  returns the number of times avalue_type object usingkey_typekey is stored in theunordered_set. This member iscommonly used to verify whetherkey is available in theunordered_multiset.
• iterator emplace(Args &&...args):
  avalue_type object is constructed fromemplace'sarguments. The returnediterator points to the newly inserted insertedvalue_type.
• iterator emplace_hint(const_iterator position, Args &&...args):
  avalue_type object is constructed from the member'sarguments, and the newly created element is inserted into theunordered_multiset. Theimplementation may or may not useposition as ahint to start lookingfor an insertion point. The returnediterator points to thevalue_typeusing the provided key.
• pair<iterator, iterator> equal_range(key):
  thismember returns a pair of iterators defining the range of elements having akey that is equal tokey.
• iterator find(key):
  returns an iterator to an element having the given key. If nosuch element is available,end is returned.
• ... insert():

  elements may be inserted starting at a certain position. Thereturn value depends on the version ofinsert() that is called. When aniterator is returned, then it points to the element that was inserted.

  • iterator insert(value_type const &value) insertsvalue.
  • iterator insert(value_type &&tmp) insertsvalue usingvalue_type's move constructor.
  • iterator insert(const_iterator hint, value_type const &value) insertsvalue, possibly usinghint as astarting point when trying to insertvalue.
  • iterator insert(const_iterator hint, value_type &&tmp) insertsvalue usingvalue_type's moveconstructor, and possibly usinghint as a starting point when trying toinsertvalue.
  • void insert(first, beyond) inserts the elements inthe iterator range[first, beyond).
  • void insert(initializer_list <value_type> iniList) inserts the elements ininiList into the container.

12.3.14: Heterogeneous lookup

Since the C++14 standard arbitrary lookup key types can be used provided acomparison operator is available to compare that type with the container's keytype. Thus, achar const * key (or any other type for which anoperator< overload forstd::string is available) can be used to lookupvalues in amap<std::string, ValueType>. This is calledheterogeneous lookup.

Heterogeneous lookup is allowed when the comparator given to the associativecontainer does allow this. The standard library classesstd::less andstd::greater were augmented to allow heterogeneous lookup.

12.4: The `complex' container

The complex number's real and imaginary types are specified as the container'sdata type. Examples:

    complex<double>    complex<int>    complex<float>

Note that the real and imaginary parts of complex numbers have the samedatatypes.

When initializing (or assigning) a complex object, theimaginary partmay be omitted from the initialization or assignment resulting in its valuebeing 0 (zero). By default, both parts are zero.

Below it is silently assumed that the usedcomplex type iscomplex<double>. Given this assumption, complex numbers may be initializedas follows:

• target: A default initialization: real and imaginary parts are 0.
• target(1): Thereal part is 1, imaginary part is 0
• target(0, 3.5): The real part is 0, imaginary part is 3.5
• target(source):target is initialized with the values ofsource.

    #include <iostream>    #include <complex>    #include <stack>    using namespace std;    int main()    {        stack<complex<double>>            cstack;        cstack.push(complex<double>(3.14, 2.71));        cstack.push(complex<double>(-3.14, -2.71));        while (cstack.size())        {            cout << cstack.top().real() << ", " <<                    cstack.top().imag() << "i" << '\n';            cstack.pop();        }    }    /*        Generated output:    -3.14, -2.71i    3.14, 2.71i    */

The following member functions and operators are defined for complexnumbers (below,value may be either a primitivescalar type or acomplex object):

• Apart from the standard container operators, the followingoperators are supported from thecomplex container.
  • complex operator+(value):
    thismember returns the sum of the currentcomplex container andvalue.
  • complex operator-(value):
    thismember returns the difference between the currentcomplex container andvalue.
  • complex operator*(value):
    thismember returns the product of the currentcomplex container andvalue.
  • complex operator/(value):
    thismember returns the quotient of the currentcomplex container andvalue.
  • complex operator+=(value):
    thismember addsvalue to the currentcomplex container, returning thenew value.
  • complex operator-=(value):
    this member subtractsvalue from the currentcomplex container,returning the new value.
  • complex operator*=(value):
    thismember multiplies the currentcomplex container byvalue, returningthe new value
  • complex operator/=(value):
    thismember divides the currentcomplex container byvalue, returning thenew value.
• Type real():
  returns thereal part of acomplex number.
• Type imag():
  returns theimaginary partof a complex number.
• Severalmathematical functions are available for thecomplex container, such asabs,arg,conj,cos,cosh,exp,log,norm,polar,pow,sin,sinh andsqrt. All these functions are free functions,not member functions, accepting complex numbers as their arguments. Forexample,

  abs(complex<double>(3, -5));pow(target, complex<int>(2, 3));

• Complex numbers may be extracted fromistreamobjects and inserted intoostream objects. The insertionresults in anordered pair(x, y), in whichx represents the realpart andy the imaginary part of the complex number. The same form mayalso be used when extracting a complex number from anistreamobject. However, simpler forms are also allowed. E.g., when extracting1.2345 the imaginary part is set to 0.

• Table of Contents
• Previous Chapter
• Next Chapter