|
void merge ( list<T,Allocator>& x );
template <class Compare>
void merge ( list<T,Allocator>& x, Compare comp );
Merge sorted lists
Merges x into the list, inserting all the elements of x into the list object at their respective ordered positions. This empties x and increases the list size.
The second version (template function), has the same behavior, but takes a specific function to perform the comparison operation in charge of determining the insertion points. The comparison function has to perform weak strict ordering (which basically means the comparison operation has to be transitive and irreflexive).
The merging is performed using two iterators: one to iterate through x and another one to keep the insertion point in the list object; During the iteration of x, if the current element in x compares less than the element at the current insertion point in the list object, the element is removed from x and inserted into that location, otherwise the insertion point is advanced. This operation is repeated until either end is reached, in which moment the remaining elements of x (if any) are moved to the end of the list object and the function returns (this last operation is performed in constant time).
The entire operation does not involve the construction or destruction of any element object.
If no ordering is required, another option for merging lists is member function list::splice, which is faster.
Parameters
- x
- A list object containing the same type of objects as this container.
- comp
- Comparison function that, taking two values of the same type than those contained in the list object, returns true if the first argument is less than the second, and false otherwise.
Return value
none
Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
// list::merge
#include <iostream>
#include <list>
using namespace std;
// this compares equal two doubles if
// their interger equivalents are equal
bool mycomparison (double first, double second)
{ return ( int(first)<int(second) ); }
int main ()
{
list<double> first, second;
first.push_back (3.1);
first.push_back (2.2);
first.push_back (2.9);
second.push_back (3.7);
second.push_back (7.1);
second.push_back (1.4);
first.sort();
second.sort();
first.merge(second);
second.push_back (2.1);
first.merge(second,mycomparison);
cout << "first contains:";
for (list<double>::iterator it=first.begin(); it!=first.end(); ++it)
cout << " " << *it;
cout << endl;
return 0;
}
|
Output:
first contains: 1.4 2.2 2.9 2.1 3.1 3.7 7.1
|
Complexity
At most, linear in x.size() + this->size() - 1.
See also
| list::splice | Move elements from list to list (public member function) |
| list::remove | Remove elements with specific value (public member function) |
|