Why not implement the function in C ++ containers?
My original question is, why is the function contains()
missing in C ++ Containers
?
So, I was looking for an explanation, and I found something interesting about why some other features are not implemented in all Containers
(essentially due to performance and usability issues).
I know that you can use a function find
from a library algorithm
or you can just write your own function using Iterator
, but I cannot figure out why in set
, for example, the function is implemented contains
(where it is called find
), whereas in vector
or queue
it is not .
It's also very clear to me why the Container classes don't have a common interface, for example Collections
in Java (thanks to this answer), but in this case I can't find a reason why not to implement the function contains()
in all container classes (or at least some sense how vector
).
thank
source to share
There is a good reason why containers do not have a common (legacy) interface "(like in Java
), and so called generators do it C++
. Why write code for each container when you can only write it once for all containers? This is one of the basic principles on which it was built STL
.
If you are using member functions from the common legacy interface to use containers, you need to write a search function for each container. This is wasteful and bad engineering. Good design says that if you can only write code in one place, you need to because you only need to remove bugs from one place, and fixing a bug in one place fixes a bug everywhere .
So the underlying philosophy STL
is to decouple algorithms from containers so that you only have to write the algorithm once and it works for all containers. After debugging the algorithm, it is debugged for all containers.
The fly in this ointment is that some containers can make better decisions due to their internal structure. A type function has been added for these containers that will take advantage of this efficiency.
But most of the functionality should be separate from containers. It's called decoupling, and it reduces bugs while using code at the same time, often much more than polymorphism that libraries such as containers Java
(common inherited interface) use.
source to share
The reason it std::set
implements its own find
is because "generic" std::find
does a linear search, or std::set
maybe much better than looking up its tree representation in O (log 2 n).
std::vector
and std::list
on the other hand cannot be found faster than in linear time, so they rely on the implementation std::find
.
Note that you are still allowed to use std::find
to std::set
to find it linearly; it's just not as efficient as using your own function find
.
std::set<int> s {1, 2, 3, 4, 5, 6};
auto res = std::find(s.begin(), s.end(), 3);
std::cout << *res << std::endl; // prints 3
source to share
Because it's a bad design pattern. If you repeatedly use find in a linear container, there is a problem with your code. The average and worst time complexity is still O (n), which means you made a bad choice.
For example, std::map
and std::unordered_map
have find
member functions that allow O (logn) and O (1) searches. This is because this container uses these methods to efficiently find items: this is how the container should be used.
If you have weighed all the parameters and decided that the line container is the best model for your data, but you need to find an element in rare cases, std::find()
lets you do just that. You don't have to rely on this. I see this as an anti-pattern in Python and Java, and an advantage in C ++.
As a personal note, 3 years ago when I was a rookie coder I wrote a lot if mydict in list: do_something()
. I thought it was a good idea, because Python makes membership in a list of elements idiomatic. I didn't know better. This led me to write terrible code until I found out why linear searches are so inefficient compared to binary and hashmap searches. A programming language or framework should provide good design patterns and discourage bad ones. Enabling Linear Search is a bad design pattern.
source to share
Other answers focus on the complexity of generic and containerized find
methods for some reason . However, they cannot explain the OP's question. The actual reason for the lack of useful utility methods comes from how classes from different files are used in C ++. If every container, which does not contain any special properties, has a method contains
that performs general search with linear complexity, we would be stuck with either a situation where each container header also includes <algorithm>
, or where each container header implements its own algorithm.find
even worse). And a rather large collection of documents at compile time each translation unit after preprocessor includes (i.e. copying) each included header will grow even more. Compilation will take even longer. And the post with a rather cryptic compilation may take even longer. This old non-member function principle, where a non-member function can do the job (and only include what you intend to use) exists for a reason.
Note that there has recently been a proposal for uniform call syntax
which may permit the use of class-classes as classes. If it works, it will probably be possible to write extension functions like this:
template< typename TContainer, typename TItem > bool
contains(TContainer const & container, TItem const & item)
{
// Some implementation possibly calling container member find
// or ::std::find if container has none...
}
::std::vector< int > registry;
registry.contains(3); // false
source to share