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

multiset Member Functions

multiset Template Class

• The STL multiset class is used for the storage and retrieval of data from a collection in which the values of the elements contained need not be unique and in which they serve as the key values according to which the data is automatically ordered.

• The key value of an element in a multiset may not be changed directly. Instead, old values must be deleted and elements with new values inserted.  The following code is the multiset template class.

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

Parameters

• The STL multiset class is:

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

• Constructs a multiset that is empty or that is a copy of all or part of some other multiset.

• All constructors store a type of allocator object that manages memory storage for the multiset and that can later be returned by callingget_allocator(). The allocator parameter is often omitted in the class declarations and preprocessing macros used to substitute alternative allocators.

• All constructors initialize their multiset.

• All constructors store a function object of type Compare that is used to establish an order among the keys of the multiset and that can later be returned by calling key_comp().

• The first three constructors specify an empty initial multiset, the second specifying the type of comparison function (_Comp) to be used in establishing the order of the elements and the third explicitly specifying the allocator type (_Al) to be used.

• The fourth constructor specifies a copy of the multiset_Right.

• The last three constructors copy the range [_First, _Last) of a multiset with increasing explicitness in specifying the type of comparison function and allocator.

// 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:

• The return value is an iterator or const_iterator that addresses the first location of an element with a specified key, or the location succeeding the last element in the multiset if no match is found for the key.

• The member function returns an iterator that addresses an element in the multiset whose sort key is equivalent to the argument key under a binary predicate that induces an ordering based on a less than comparability relation.

• If the return value of find() is assigned to aconst_iterator, the multiset object cannot be modified. If the return value of find() is assigned to an iterator, the multiset object can be modified.

// 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:

• Program examples compiled usingg++.

// *****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 inC++ STL Container source code.

2. Check thebest selling C / C++ books at Amazon.com.

3. Acomplete C Standard Library.

4. Acomplete 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