In the C++ standard the complexity of algorithms is a requirement for a compliant implementation. Many text books skip it, but better documentation references it. Taking the "delete element from list" example from this thread https://en.cppreference.com/w/cpp/container/list/remove states that there is a linear search.