std::list::merge(3)

📦 version 2024.07.05, in nixpkgs unstable, opensuse-leap 16.0

✨ std::list::merge ✨

okay so bestie, welcome to the std::list::merge(3) page from the C++ Standard Library — we're gonna get you fluent in list-merging realness. no cap, this one's lowkey iconic. 💅

🌸 NAME 🌸

std::list::merge — it merges lists. that's the whole gig. main character energy from the jump. 👑

💅 Synopsis 💅

void merge( list& other );                (1)
void merge( list&& other );               (2) (since C++11)
template< class Compare >                 (3)
void merge( list& other, Compare comp );
template< class Compare >                 (4) (since C++11)
void merge( list&& other, Compare comp );

okay so first thing: if other refers to the same object as *this, this function does literally nothing. no-op. ghost mode. 👻

otherwise, it merges other into *this. both lists should be sorted already (that's the vibe check they need to pass). no elements are copied, and the container other becomes empty after the merge. this operation is stable: for equivalent elements in the two lists, the elements from *this always precede the elements from other, and the order of equivalent elements of *this and other does not change. so if two things compare equal, the one from *this goes first, and neither list's internal order of equal elements gets shuffled. stable queen behavior. 👑

no iterators or references become invalidated. the pointers and references to the elements moved from *this, as well as the iterators referring to these elements, will refer to the same elements of *this, instead of other. so your iterators stay valid and they follow the element to its new home in *this, not other. periodt.

  • 1,2) elements are compared using operator<.
  • 3,4) elements are compared using comp.
⚠️ if *this or other is not sorted with respect to the corresponding comparator, or get_allocator() != other.get_allocator(), the behavior is undefined. not "probably fine," not "we'll see" — undefined. so sort your lists and match your allocators, bestie. 🙈

🎀 Parameters 🎀

  • other — another container to merge. that's it. that's the other list. 🫶
  • comp — comparison function object (i.e. an object that satisfies the requirements of Compare) which returns true if the first argument is less than (i.e. is ordered before) the second.

the signature of the comparison function should be equivalent to the following:

bool cmp(const Type1& a, const Type2& b);

while the signature does not need to have const&, the function must not modify the objects passed to it and must be able to accept all values of type (possibly const) Type1 and Type2 regardless of value category (thus, Type1& is not allowed, nor is Type1 unless for Type1 a move is equivalent to a copy (since C++11)). the types Type1 and Type2 must be such that an object of type list<T, Allocator>::const_iterator can be dereferenced and then implicitly converted to both of them. fancy, but basically: make your comparator chill and don't mutate stuff. 🧚

🦋 Type requirements 🦋

  • Compare must meet the requirements of Compare. that's the whole requirement. it's giving self-referential but we move. 💅

🌈 Return value 🌈

(none). nothing. zero. nada. it's a void function, bestie. it does the thing and returns to the void. ✨

💀 Exceptions 💀

if an exception is thrown for any reason, these functions have no effect — that's the strong exception safety guarantee, slay. but there's a catch: except if the exception comes from a comparison. so if your comp throws, that guarantee doesn't apply. keep your comparator well-behaved or suffer the consequences. 💀

🔥 Complexity 🔥

if other refers to the same object as *this, no comparisons are performed. none. zero. we love a no-op shortcut. 🎀

otherwise, given N as std::distance(begin(), end()) and R as std::distance(other.begin(), other.end()):

  • 1,2) at most N+R-1 comparisons using operator<.
  • 3,4) at most N+R-1 applications of the comparison function comp.

so it's linear-ish, not quadratic. your CPU thanks you. 🔥

🍓 Example 🍓

// Run this code

#include <iostream>
#include <list>

std::ostream& operator<<(std::ostream& ostr, const std::list<int>& list)
{
    for (const int i : list)
        ostr << ' ' << i;
    return ostr;
}

int main()
{
    std::list<int> list1 = {5, 9, 1, 3, 3};
    std::list<int> list2 = {8, 7, 2, 3, 4, 4};

    list1.sort();
    list2.sort();
    std::cout << "list1: " << list1 << '\n';
    std::cout << "list2: " << list2 << '\n';

    list1.merge(list2);
    std::cout << "merged:" << list1 << '\n';
}

Output:

list1:  1 3 3 5 9
list2:  2 3 4 4 7 8
merged: 1 2 3 3 3 4 4 5 7 8 9

like, look at that merge. list2 is empty after, list1 is sorted and combined, and the duplicate 3s are all sitting together in their stable little order. chef's kiss. 🤌

👑 Defect reports 👑

the following behavior-changing defect reports were applied retroactively to previously published C++ standards. history, but make it fashion. 💅

  • LWG 300 (C++98) — the effect when *this and other refer to the same object was not specified; now it's specified as a no-op.
  • LWG 1207 (C++98) — it was unclear whether iterators and/or references will be invalidated; now they keep valid.
  • LWG 1215 (C++98) — O(1) node moving could not be guaranteed if get_allocator() != other.get_allocator(); now the behavior is undefined in this case.

🌟 See also 🌟

  • splice — moves elements from another list (public member function)
  • merge — merges two sorted ranges (function template)
  • inplace_merge — merges two ordered ranges in-place (function template)
  • ranges::merge (C++20) — merges two sorted ranges (niebloid)
  • ranges::inplace_merge (C++20) — merges two ordered ranges in-place (niebloid)

mwah 💋 this page was served fresh from http://cppreference.com on 2024.06.10 — std::list::merge(3), signing off. stay sorted, bestie. 💖

📦 where this page comes from