STL容器list、deque、vector等的基类是什么？

Question

我想编写一个函数，可以接受STL通用列表、双端队列或向量，并在其中搜索关键字。这个函数的方法签名是什么？我们该如何实现它？

我知道如果我们在函数参数中接受任何派生类，我们可以使用基础抽象类，假设所有相关的派生类都具有您需要的函数。

编辑：我们不能将容器的迭代器传递给函数参数。如果可以的话，那很容易。它必须是一个容器。

我在思考：假设“Container”是STL容器的抽象基类（根据下面的第一个答案，它不是）。

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

谢谢

- shaffooo

---

它们没有基类。查看<algorithm>函数以了解它们的功能。 - chris

谢谢您的评论，但它并没有解答我的问题。大多数预定义的<算法>函数在提供范围时非常有用，但我需要传入一个STL容器。 - shaffooo

谢谢您的评论，但它没有对所提出的问题有所帮助。是的，它表明STL容器没有基类，因此您的问题基于错误的假设。请忘记基类，并考虑用另一种方式来解决这个问题。 - PaulMcKenzie

Answer 1

正如SergeyA在他的回答中提到的，C++的STL没有多态容器（与Java或C#接口相对）。

关于您请求的函数签名，请查看STL <algorithm>头文件。有很多函数操作一些数据，使用两个指针（迭代器）指向数据块的开头和结尾。例如：

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

在[first，last)范围内搜索一些value。

如果您确实想将整个容器传递给函数，则可以类似地编写

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;
}

- Zereges

---

我认为 'return false;' 应该在 for 循环之外。 - shaffooo

如果容器的类型是 T，并且您的函数旨在处理容器中的类型，则在模板定义中不需要两个参数：template<class Container> bool Search(const Container& container, const Container::value_type& value)。 - PaulMcKenzie

@shaffooo，如果你无法使用auto，仍然可以通过typename Container::[const_]iterator约定来实现。 - chris

@PaulMcKenzie，不幸的是，这可能会产生一些不良后果。例如，您有一个std::string容器，并且您想要查找“abc”（除非足够长，否则不适用SSO）。现在，您需要创建一个带有分配和所有内容的新字符串。除非您正在制作用户可能关心的库，否则此类问题通常不是问题。您的方法的一个优点是可以使用大括号作为参数来构造值。 - chris

@chris 然后你可以为函数模板设置默认参数。举个例子：http://ideone.com/ZmMc0H 默认为 value::type，否则使用提供的 T 类型。当然，我甚至不需要指定第一个模板参数 - 这是为了说明如果提供了1个参数，则默认值会生效。 - PaulMcKenzie

Answer 2

幸运的是，标准库容器没有基类。我所知道的唯一使用多态继承的标准库位置是流（streams），这也是它们赢得如此糟糕声誉的原因。

标准容器是非多态的，因此速度很快。您需要使您的函数模板适用于任何容器。

例如：

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

- SergeyA

---

我理解我们需要创建一个模板，但我想知道的是函数签名会是什么样子。我们将传递什么容器？键可以是一些通用类型T，定义为template<typename T>。 - shaffooo

@shaffooo，考虑使用迭代器。 - SergeyA

我认为你的意思是我们在调用函数中有一个STL容器，我们可以获取开始和结束迭代器，并将两个迭代器和键传入该范围进行搜索，或者使用<algorithm>中的'find'函数。我知道这个解决方案。这个问题是在面试中问到的，限制是我必须传入任何STL容器本身。 - shaffooo

那么函数参数会是 std::list<T>、std::deque<T> 还是 std::vector<T>？我只能传入一个容器参数和一个关键字参数，类似于 search(std::container<T> c, T key)。 - shaffooo

Answer 3

容器没有基类，它们不是基于动态多态性定义接口的。它们基于静态多态性定义接口。也就是说，它们确实实现了某些共同的方法，但这些方法并非从某个原型继承而来。

因此，您必须使用标准的C++静态多态机制：模板。容器本身必须成为模板参数:

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

当然，这并不能阻止任何用户传递不是vector、deque或list的类型。他们可以传递任何符合你的IsFound函数所施加的隐式静态要求的东西。

例如，您可以传递一个set，它可能会工作，在某种程度上。但是，与使用该类型的set::find相比，速度不会快得多。

- Nicol Bolas

---

这很有帮助。现在我们如何使该容器接受模板数据类型。我们可以使用template <typename Container<typename T>>来接受不同数据类型的容器，例如int或double等。 - shaffooo

对于 STL 容器，您可以通过使用 Container::value_type 来确定类型。 - PaulMcKenzie