Когсуэлл Джефф
Шрифт:
lstStr2.push_back("McBeal");
lstStr2.push_back("Slick");
lstStr2.push_back("Willie");
lstStr1.sort; // Отсортировать, иначе объединение выдаст мусор!
lstStr2.sort;
lstStr1.merge(lstStr2); // Заметьте, что это работает только для другого
// списка того же типа
printContainer(lstStr1);
}
Вывод примера 7.5 выглядит так.
– ----
a
b
с
d
e
f
– ----
b
d
e
a
c
f
– ----
a
b
с
d
e
f
Allie
Bill
Cheetoh
Frank
McBeal
Rizzo
Slick
Willie
Обсуждение
merge
объединяет две последовательности и помещает результат в третью — опционально используя функтор сравнения, указанный пользователем и определяющий, когда один элемент меньше другого, а по умолчанию используя operator<
. Сложность линейна: число выполняемых merge
сравнений равно сумме длин двух последовательностей минус один. Типы элементов в обеих последовательностях должны быть сравниваемы с помощью operator<
(или указанного вами функтора сравнения) и должны быть преобразуемы к типу элементов выходной последовательности при помощи конструктора копирования или присвоения; или должен быть определен оператор преобразования, определенный так, чтобы тип элементов выходной последовательности имел для обоих типов операторы присвоения и конструкторы копирования. Объявления
merge
выглядят вот так void merge(In1 first1, In1 last1, In2 first2, In2 last2, Out result);
void merge(In1 first1, In1 last1, In2 first2, In2 last2, Out result,
BinPred comp)
Использование
merge
довольно просто. Обе последовательности должны быть отсортированы (иначе вывод будет представлять собой мусор), и ни одна из них при использовании merge
не изменяется. Итератор вывода, в который помещаются результаты, должен иметь достаточно места для помещения в него числа элементов, равного сумме длин входных последовательностей. Этого можно добиться, явно зарезервировав достаточно места либо, как это сделано в примере 7.5, использовав back_inserter
: merge(v1.begin, v1.end, v2.begin, v2.end,
back_inserter(v3));
back_inserter
— это класс, определенный в <iterator>
, который предоставляет удобный способ создания выходного итератора, который каждый раз, когда ему присваивается значение, вызывает для последовательности метод push_back
. Таким образом, вам не требуется явно изменять размер выходной последовательности. Следующий вызов создает back_inserter
для vector<string>
с именем v3
. back_inserter(v3);
Указывать аргументы шаблона не требуется, так как
back_inserter
— это шаблон функции, а не класса, так что тип аргументов, с которыми он вызван, определяется автоматически. Эквивалентный вызов с явным указанием аргументов шаблона выглядит вот так. back_inserter<vector<string> >(v3);
Однако заметьте, что иногда вам потребуется явно указывать размер выходной последовательности, особенно при использовании в качестве такой последовательности
vector
, vector
при добавлении в него элементов с помощью push_back
может потребовать изменений своего размера, а это очень дорогостоящая операция. За подробностями обратитесь к рецепту 6.2. Если в последовательностях есть два одинаковых элемента, то элемент из первой последовательности будет предшествовать элементу из второй. Следовательно, если дважды вызвать
merge
, поменяв для второго вызова последовательности местами, результирующие выходные последовательности будут различаться (предсказуемо и правильно, но различаться). Объединение двух
list
— это хороший пример ситуации, где можно использовать метод последовательности или аналогичный стандартный алгоритм. Следует предпочесть метод стандартному алгоритму, делающему то же самое, но это не всегда работает, и вот пример, который показывает, почему. Рассмотрим список строк из примера 7.5:
lstStr1.sort; // Сортируем, или объединение даст мусор!
lstStr2.sort,
lstStr1.merge(lstStr2); // Это list::merge
Есть две причины, по которым этот код отличается от вызова
std::merge
. Во-первых, оба списка list
должны иметь один и тот же тип элементов. Это требование следует из объявления list::merge
, которое имеет вид: void merge(list<T, Alloc>& lst);