CODEWITHSUNDEEP
c++templatessearchstl
shaffooo
shaffooo

Reputation: 1646

What is the base class for STL containers list, deque, vector etc.?

I want to write a function that can take either of STL generic list, deque or vector and search for a key in it. What would be method signature of this function and how can we implement it?

What I know is that if we are accepting any of the derived classes in function argument we can use base abstract class assuming all relevant derived ones have the functions you need for your question.

EDIT: We cannot pass container's iterators in the function argument. If we can that is easy. It has to be a container.

I was thinking: Assuming 'Container' is an abstract base class from STL containers (which its not, according to first answer below).

template bool Search(std::Container C, T& key);

Thanks

Upvotes: 9

Views: 6857

Answers (3)

Zereges
Zereges

Reputation: 5209

As SergeyA mentioned in his answer, C++'s STL does not have polymorphic containers (opposing to Java or C# interfaces).

Regarding your requested function signature, look into STL <algorithm> header. There are lot of functions operating on some data, using two pointers (iterators) to the beginning and end of data block. For example,

template< class InputIt, class T >
InputIt find( InputIt first, InputIt last, const T& value );

searching for some value in [first, last).

If you really want to pass whole container to the function, you'll similarly write

template<class Container, class T>
bool Search(const Container& container, const T& value)
{
    for (auto iterator = container.begin(); iterator != container.end(); ++iterator)
    {
        if (*iterator == value)
            return true;
    }
    return false;
}

Upvotes: 13

SergeyA
SergeyA

Reputation: 62553

Luckily for us, there is no base class for standard library containers. The only place I know of where polymorphic inheritance is used in standard library is streams, and this is what earned them such a bad fame.

Standard containers are non-polymorphic, thus fast. You will have to make your function template to work with any container.

For example,

template <class CONTAINER> bool exists(const CONTAINER& ctr, const typename CONTAINER::value_type& key);

Upvotes: 5

Nicol Bolas
Nicol Bolas

Reputation: 473232

Containers do not have base classes. They do not define an interface based on dynamic polymorphism. They define an interface based on static polymorphism. That is, they do implement certain methods in common, but they are not inherited from some prototype.

Therefore, you must use the standard C++ mechanism for static polymorphism: templates. The container itself must be a template parameter:

template<typename Container, ...>
bool IsFound(const Container &c, ...);

Of course, this will not prevent any user from passing types which are not vector, deque, or list. They could pass anything that fulfills the implicit static requirements that your IsFound function imposes.

You could pass a set for example, and it would probably work, to some degree. But it wouldn't be nearly as fast as calling set::find with the type.

Upvotes: 4

Related Questions