|< C++ STL Container 6 | Main | C++ STL Container 8 - map, multimap, hash >| Site Index | Download |


 

 

 

 

 

MODULE 28

THE C++ STL CONTAINER PART 7

list, set, multiset

 

 

 

 

My Training Period: xx hours

 

What do we have in this session?

  1. Multiset

  2. multiset Members – typedef & member function

  3. multiset Template Class

  4. multiset Constructor

  5. multiset constructor program example

  6. multiset, find() program example

  7. list, sort() – g++ program example

  8. set, count() – g++ program example

  9. multiset, find() – g++ program example

 

 

 

 

 

 

 

 

 

 

 

 

 

 

28.6  Multiset

  • A multiset is the same as a set except that duplicates are allowed. Thus, a multiset may contain multiple elements that have the same value.  It can be depicted as follows:

C++ STL Associative container multiset illustration

  • The elements of a multiset may be multiple and serve as their own sort keys, so keys are not unique. If the definitions were not unique, then a multimap would be the container of choice.

  • The multiset orders the sequence it controls by calling a stored function object of type Compare. This stored object is a comparison function that may be accessed by calling the member function key_comp().

  • The iterator provided by the multiset class is a bidirectional iterator.

multiset Members

 

multiset Typedefs

 

Typedef

Description

allocator_type

A type that represents the allocator class for the multiset object.

const_iterator

A type that provides a bidirectional iterator that can read a const element in the multiset.

const_pointer

A type that provides a pointer to a const element in a multiset.

const_reference

A type that provides a reference to a const element stored in a multiset for reading and performing const operations.

const_reverse_iterator

A type that provides a bidirectional iterator that can read any const element in the multiset.

difference_type

A signed integer type that can be used to represent the number of elements of a multiset in a range between elements pointed to by iterators.

iterator

A type that provides a bidirectional iterator that can read or modify any element in a multiset.

key_compare

A type that provides a function object that can compare two keys to determine the relative order of two elements in the multiset.

key_type

A type that provides a function object that can compare two sort keys to determine the relative order of two elements in the multiset.

pointer

A type that provides a pointer to an element in a multiset.

reference

A type that provides a reference to an element stored in a multiset.

reverse_iterator

A type that provides a bidirectional iterator that can read or modify an element in a reversed multiset.

size_type

An unsigned integer type that can represent the number of elements in a multiset.

value_compare

The type that provides a function object that can compare two elements as sort keys to determine their relative order in the multiset.

value_type

A type that describes an object stored as an element as a multiset in its capacity as a value.

 

Table 28.12

 

multiset Member Functions

 

Member function

Description

begin()

Returns an iterator addressing the first element in the multiset.

clear()

Erases all the elements of a multiset.

count()

Returns the number of elements in a multiset whose key matches a parameter-specified key.

empty()

Tests if a multiset is empty.

end()

Returns an iterator that addresses the location succeeding the last element in a multiset.

equal_range()

Returns a pair of iterators respectively to the first element in a multiset with a key that is greater than a specified key and to the first element in the multiset with a key that is equal to or greater than the key.

erase()

Removes an element or a range of elements in a multiset from specified positions or removes elements that match a specified key.

find()

Returns an iterator addressing the first location of an element in a multiset that has a key equivalent to a specified key.

get_allocator()

Returns a copy of the allocator object used to construct the multiset.

insert()

Inserts an element or a range of elements into a multiset.

key_comp()

A type that provides a function object that can compare two sort keys to determine the relative order of two elements in the multiset.

lower_bound()

Returns an iterator to the first element in a multiset with a key that is equal to or greater than a specified key.

max_size()

Returns the maximum length of the multiset.

multiset()

multiset constructor, constructs a multiset that is empty or that is a copy of all or part of some other multiset.

rbegin()

Returns an iterator addressing the first element in a reversed multiset.

rend()

Returns an iterator that addresses the location succeeding the last element in a reversed multiset.

size()

A type that counts the number of elements in a multiset.

swap()

Exchanges the elements of two multisets.

upper_bound()

Returns an iterator to the first element in a multiset that with a key that is equal to or greater than a specified key.

value_comp()

Retrieves a copy of the comparison object used to order element values in a multiset.

 

Table 28.13

 

multiset Template Class

template < class Key, class Compare = less<Key>, class Allocator = allocator<Key> > 

 

Parameters

 

Parameter

Description

Key

The element data type to be stored in the multiset.

Compare

The type that provides a function object that can compare two element values as sort keys to determine their relative order in the multiset. The binary predicate less<Key> is the default value.

Allocator

The type that represents the stored allocator object that encapsulates details about the multiset's allocation and de-allocation of memory. The default value is allocator<Key>.

 

Table 28.14

  1. An associative container, which is a variable size container that supports the efficient retrieval of element values based on an associated key value.

  2. Reversible, because it provides bidirectional iterators to access its elements.

  3. Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.

  4. Multiple in the sense that its elements do not need to have unique keys, so that one key value can have many element values associated with it.

  5. A simple associative container because its element values are its key values.

  6. A template class, because the functionality it provides is generic and so independent of the specific type of data contained as elements. The data type to be used is, instead, specified as a parameter in the class template along with the comparison function and allocator.

multiset Constructor

// a multiset constructor

#include <set>

#include <iostream>

using namespace std;

 

int main()

{

   multiset <int>::iterator mst0_Iter, mst1_Iter, mst2_Iter, mst3_Iter;

   multiset <int>::iterator mst4_Iter, mst5_Iter, mst6_Iter;

   // create an empty multiset mst0 of key type integer

   multiset <int> mst0;

   // create an empty multiset mst1 with the key comparison function of less than, then insert 6 elements

   multiset <int, less<int> > mst1;

   mst1.insert(41);

   mst1.insert(15);

   mst1.insert(30);

   mst1.insert(10);

   mst1.insert(15);

   mst1.insert(35);

   // create an empty multiset mst2 with the key comparison function of greater than, then insert 4 elements

   multiset <int, greater<int> > mst2;

   mst2.insert(10);

   mst2.insert(21);

   mst2.insert(8);

   mst2.insert(21);

   // create a multiset mst3 with the allocator of multiset mst1

   multiset <int>::allocator_type mst1_Alloc;

   mst1_Alloc = mst1.get_allocator();

   multiset <int> mst3(less<int>(), mst1_Alloc);

   mst3.insert(7);

   mst3.insert(12);

   mst3.insert(9);

   // multiset mst4, a copy of multiset mst1

   multiset <int> mst4(mst1);

   // create a multiset mst5 by copying the range mst1[_First, _Last)

   multiset <int>::const_iterator mst1_PIter, mst1_QIter;

   mst1_PIter = mst1.begin();

   mst1_QIter = mst1.begin();

   mst1_QIter++;

   mst1_QIter++;

   multiset <int> mst5(mst1_PIter, mst1_QIter);

   // create a multiset mst6 by copying the range mst4[_First, _Last) and with the allocator of multiset mst2

   multiset <int>::allocator_type mst2_Alloc;

   mst2_Alloc = mst2.get_allocator();

   multiset <int> mst6(mst4.begin(), ++mst4.begin(), less<int>(), mst2_Alloc);

   // -----------------------------------------------------

   cout<<"Operation: multiset <int> mst0\n";

   cout<<"mst0 data: ";

   for(mst0_Iter = mst0.begin(); mst0_Iter != mst0.end(); mst0_Iter++)

      cout<<" " <<*mst0_Iter;

   cout<<endl;

   cout<<"\nOperation: multiset <int, less<int> > mst1\n";

   cout<<"Operation: mst1.insert(41)...\n";

   cout<<"mst1 data: ";

   for(mst1_Iter = mst1.begin(); mst1_Iter != mst1.end(); mst1_Iter++)

      cout<<" "<<*mst1_Iter;

   cout<<endl;

   cout<<"\nOperation: multiset <int, greater<int> > mst2\n";

   cout<<"Operation: mst2.insert(10)...\n";

   cout<<"mst2 data: "<<*mst2.begin()<<" "<<*++mst2.begin()<<endl;

   cout<<"\nOperation: multiset <int> mst3(less<int>(), mst1_Alloc)\n";

   cout<<"Operation: mst3.insert(7)...\n";

   cout<<"mst3 data: ";

   for(mst3_Iter = mst3.begin(); mst3_Iter != mst3.end(); mst3_Iter++)

      cout<<" "<<*mst3_Iter;

   cout<<endl;

   cout<<"\nOperation: multiset <int> mst4(mst1)\n";

   cout<<"mst4 data: ";

   for(mst4_Iter = mst4.begin(); mst4_Iter != mst4.end(); mst4_Iter++)

      cout<<" "<<*mst4_Iter;

   cout<<endl;

   cout<<"\nOperation: multiset <int> mst5(mst1_PIter, mst1_QIter)\n";

   cout<<"mst5 data: ";

   for(mst5_Iter = mst5.begin(); mst5_Iter != mst5.end(); mst5_Iter++)

      cout<<" "<<*mst5_Iter;

   cout<<endl;

   cout<<"\nOperation: multiset <int> mst6(mst4.begin(), \n++mst4.begin(), less<int>(), mst2_Alloc);\n";

   cout<<"mst6 data: ";

   for(mst6_Iter = mst6.begin(); mst6_Iter != mst6.end(); mst6_Iter++)

      cout<<" "<<*mst6_Iter;

   cout<<endl;

   return 0;

}

 

Output:

C++ STL Associative container multiset constructor  

// multiset, find()

#include <set>

#include <iostream>

using namespace std;  

 

int main()

{

    multiset <int> mst1;

    multiset <int>::const_iterator mst1_QIter, mst1_PIter, mst1_RIter;

    mst1.insert(6);

    mst1.insert(2);

    mst1.insert(14);

    mst1.insert(6);

    mst1.insert(10);

    cout<<"mst1 data: ";

    for(mst1_RIter = mst1.begin(); mst1_RIter != mst1.end(); mst1_RIter++)

        cout<<" "<<*mst1_RIter;

    cout<<endl;

    mst1_PIter = mst1.find(10);

    cout<<"The first element of multiset mst1 with a key of 10 is: "<<*mst1_PIter<<endl;

    mst1_PIter = mst1.find(21);

    // if no match is found for the key, end() is returned

    if(mst1_PIter == mst1.end())

        cout<<"\nThe multiset mst1 doesn't have an element with a key of 21"<<endl;

    else

        cout<<"\nThe element of multiset mst1 with a key of 21 is: "<<*mst1_PIter<<endl;

    // the element at a specific location in the multiset can be

    // found using a dereferenced iterator addressing the location

    mst1_QIter = mst1.end();

    mst1_QIter--;

    mst1_PIter = mst1.find(*mst1_QIter);

    cout<<"\nThe first element of mst1 with a\nkey matching that of the last element is: "<<*mst1_PIter<<endl;    

    // note that the first element with a key equal to the key of the last element is not the last element

    if(mst1_PIter == --mst1.end())

        cout<<"\nThis is the last element of multiset mst1."<<endl;

    else

        cout<<"\nThis is not the last element of multiset mst1."<<endl;

    return 0;

}

 

Output:

 

C++ STL Associative container multiset rfind()

// *****listsort.cpp******

// list, sort()

#include <list>

#include <iostream>

using namespace std;

 

int main()

{

    list <int> ls1;

    list <int>::iterator ls1Iter;

    ls1.push_back(31);

    ls1.push_back(12);

    ls1.push_back(40);

    ls1.push_back(15);

    ls1.push_back(9);

    ls1.push_back(44);

    cout<<"Before sorting, ls1 data: ";

    for(ls1Iter = ls1.begin(); ls1Iter != ls1.end(); ls1Iter++)

        cout<<" "<<*ls1Iter;

    cout<<endl;

    cout<<"\nOperation: ls1.sort()\n";

    ls1.sort();

    cout<<"After sorting, ls1 data: ";

    for(ls1Iter = ls1.begin(); ls1Iter != ls1.end(); ls1Iter++)

        cout<<" "<<*ls1Iter;

    cout<<endl;

    cout<<"\nOperation: ls1.sort(greater<int>())\n";

    ls1.sort(greater<int>());

    cout<<"Re sort with 'greater than' operation,\nls1 =";

    for(ls1Iter = ls1.begin(); ls1Iter != ls1.end(); ls1Iter++)

        cout<<" "<<*ls1Iter;

    cout<<endl;

    return 0;

}

 

[bodo@bakawali ~]$ g++ listsort.cpp -o listsort

[bodo@bakawali ~]$ ./listsort

 

Before sorting, ls1 data:  31 12 40 15 9 44

 

Operation: ls1.sort()

After sorting, ls1 data:  9 12 15 31 40 44

 

Operation: ls1.sort(greater<int>())

Re sort with 'greater than' operation,

ls1 = 44 40 31 15 12 9

 

// ******setcount.cpp*******

// set, count(), expect some warning during the compilation

#include <set>

#include <iostream>

using namespace std;

 

int main()

{

    set <int> st1;

    int i;

    st1.insert(1);

    st1.insert(2);

    st1.insert(1);

    // keys must be unique in set, duplicates are ignored

    i = st1.count(1);

    cout<<"The number of elements in st1 with a sort key of 1 is: "<<i<<endl;

    i = st1.count(2);

    cout<<"The number of elements in st1 with a sort key of 2 is: "<<i<<endl;

    i = st1.count(3);

    cout<<"The number of elements in st1 with a sort key of 3 is: "<<i<<endl;

    return 0;

}

 

[bodo@bakawali ~]$ g++ setcount.cpp -o setcount

[bodo@bakawali ~]$ ./setcount

 

The number of elements in st1 with a sort key of 1 is: 1

The number of elements in st1 with a sort key of 2 is: 1

The number of elements in st1 with a sort key of 3 is: 0

 

// ******multisetfind.cpp******

// multiset, find()

#include <set>

#include <iostream>

using namespace std;  

 

int main()

{

    multiset <int> mst1;

    multiset <int>::const_iterator mst1_QIter, mst1_PIter, mst1_RIter;

    mst1.insert(6);

    mst1.insert(2);

    mst1.insert(14);

    mst1.insert(6);

    mst1.insert(10);

    cout<<"mst1 data: ";

    for(mst1_RIter = mst1.begin(); mst1_RIter != mst1.end(); mst1_RIter++)

    cout<<" "<<*mst1_RIter;

    cout<<endl;

    mst1_PIter = mst1.find(10);

    cout<<"The first element of multiset mst1 with a key of 10 is: "<<*mst1_PIter<<endl;

    mst1_PIter = mst1.find(21);

    // if no match is found for the key, end() is returned

    if(mst1_PIter == mst1.end())

        cout<<"\nThe multiset mst1 doesn't have an element with a key of 21"<<endl;

    else

        cout<<"\nThe element of multiset mst1 with a key of 21 is: "<<*mst1_PIter<<endl;

    // the element at a specific location in the multiset can be

    // found using a dereferenced iterator addressing the location

    mst1_QIter = mst1.end();

    mst1_QIter--;

    mst1_PIter = mst1.find(*mst1_QIter);

    cout<<"\nThe first element of mst1 with a\nkey matching that of the last element is: "<<*mst1_PIter<<endl;

    // note that the first element with a key equal to the key of the last element is not the last element

    if(mst1_PIter == --mst1.end())

        cout<<"\nThis is the last element of multiset mst1."<<endl;

    else

        cout<<"\nThis is not the last element of multiset mst1."<<endl;

    return 0;

}

 

[bodo@bakawali ~]$ g++ multisetfind.cpp -o multisetfind

[bodo@bakawali ~]$ ./multisetfind

 

mst1 data:  2 6 6 10 14

The first element of multiset mst1 with a key of 10 is: 10

 

The multiset mst1 doesn't have an element with a key of 21

 

The first element of mst1 with a

key matching that of the last element is: 14

 

This is the last element of multiset mst1.

 

 

----------------------------------------End of multiset-----------------------------------

tenouk C++ STL tutorial

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Further C++ container related reading:

 

  1. Source code is available in C++ STL Container source code.

  2. Check the best selling C / C++ books at Amazon.com.

  3. A complete C & C++ Standard Library documentation that includes STL.

 

 

 

 

 

 

 

|< C++ STL Container 6 | Main | C++ STL Container 8 - map, multimap, hash >| Site Index | Download |


C++ STL Container Classes:  Part 1 | Part 2 | Part 3 | Part 4 | Part 5 | Part 6 | Part 7 | Part 8 | Part 9 | Part 10 | Part 11