std::find 与从向量派生模板

Question

我在编程中经常使用向量，并且通常为了遍历向量来获取现有值，我使用 std::find ，如下所示：

std::vector<int> foo;
std::vector<int>::iterator pos( std::find( foo.begin(), foo.end(), bar );

这是一个真正的无聊。所以我从 std::vector 派生一个模板来提供 find 方法：

template<class T>
class foovector : public std::vector<T>
{
public:
    typename std::vector<T>::iterator find( const T& value )
    {
        return std::find( this->begin(), this->end(), value );
    }
};

所以现在我可以更自然地进行查找：

foovector<int> foo;
foovector<int>::iterator pos( foo.find( bar ) );

我的问题是，这似乎是一个向量的自然且明显的扩展，那么为什么它不是 STL 甚至 boost 的一部分呢？我觉得我在这里缺少一些奥术知识。

Answer 1

如果你做了你想要实现的事情，但仍然不进入从 std::vector 继承的可疑路径，

定义一个独立的函数，

template <typename T>
typename std::vector<T>::const_iterator find( const std::vector<T>& v, const T& value )
 {
     return std::find( v.begin(), v.end(), value );
 }

你可以将其放入命名空间 std（从技术上讲，这是不允许的），或在其他命名空间中（代价是 ADL 无法找到它，因此您需要对其进行限定）。 HTH

P.S.顺便说一句，你可以将其推广到所有容器

template <typename Container, typename T>
typename Container::const_iterator find( const Container& c, const T& value )
{
     return std::find( c.begin(), c.end(), value );
}

Answer 2

1. 从 STL 容器继承不被认为是一个好主意 -它们没有虚拟析构函数，因为它们不是为此设计的。

2. 的优势不在于其可搜索性 - 还有其他专门用于此目的的容器。

3. 我怀疑大多数人只是不觉得您要替换的代码那么麻烦。

Answer 3

STL 设计是提供具有狭窄接口的集合，该接口仅实现在不访问私有成员的情况下无法实现的方法。

然后，他们在迭代器（而不是集合）上添加模板函数。这意味着，即使您创建自己的集合，只要提供标准迭代器，其中许多函数也可以很好地工作。您不需要继承来完成这项工作——因此事情可以保持独立。

Answer 4

可能是因为向量是最简单的容器类型，如果优先考虑搜索，则可以使用更好的（关联）容器。

如果您按索引搜索，Vector 具有 O(1) 性能，但如果您使用搜索算法，您将失去所有这些好处。

Answer 5

因为如果您通常需要进行大量查找，则应该使用集合或映射（或两者的哈希版本）。它不仅更容易编写，而且复杂度为 O(log n)，而未排序的向量为 O(n)。

与地图：

map<stuff> m
m[bar] // returns a reference to the element with key bar.

设置类似。

Answer 6

实际上，我已经将 中定义的大部分自由函数包装为采用容器/范围而不是迭代器的版本。它不仅更安全（我可以添加简单的检查，确保范围有效，等等......）而且也更方便。

对于您的情况，执行此操作的通用方法是：

template <typename Container>
typename Container::iterator find(Container& c,
                                  typename Container::value_type const& v)
{
  return std::find(c.begin(), c.end(), v);
}

template <typename Container>
typename Container::const_iterator find(Container const& c,
                                        typename Container::value_type const& v)
{
  return std::find(c.begin(), c.end(), v);
}

这可以与任何符合 STL 的容器一起使用。

当然，最好是通过 Concept 来调整它，以便使用成员函数 find（如果可用）......