multiset, find() – g++ program example
<
| 28.6 Multiset
multiset Members
multiset Typedefs
|
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 |
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> >
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 isallocator<Key>. |
Table 28.14 |
The STL multiset class is:
An associative container, which is a variable size container that supports the efficient retrieval of element values based on an associated key value.
Reversible, because it provides bidirectional iterators to access its elements.
Sorted, because its elements are ordered by key values within the container in accordance with a specified comparison function.
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.
A simple associative container because its element values are its key values.
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.
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;
}
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-----------------------------------
Source code is available inC++ STL Container source code.
Check thebest selling C / C++ books at Amazon.com.
Acomplete C++ Standard Library documentation that includes STL.