java - 继承 Java 集合接口(interface)(Set、Map、List 等)的 C++ 等价物是什么？或者扩展 AbstractCollection？

Question

我已经开始使用 C++ 编写代码，来自 Java 背景(实际上我在我的大学学习了 C++，但我们从未接触过 STL 等)

无论如何，我已经到了在各种集合中排列数据的地步，我立即告诉自己“好吧，这是一种集合；这是一个列表，或者一个 ArrayList；这是一张 map 等等。”在 Java 中，我会简单地让我正在编写的任何类实现 Set 或 Map 或 List 接口(interface)；但我可能不会去继承 ArrayList 或 HashSet 或其他什么，那里的实现有点涉及，我不想把它们搞砸。

现在，我要用 C++(使用标准库)做什么？似乎没有 Sets、Maps、Lists 等的抽象基类——相当于 Java 接口(interface)；另一方面，标准容器的实现看起来很糟糕。好吧，一旦你了解了它们，也许它们就没那么可怕了，但假设我只是想用 C++ 编写类似扩展 AbstractSet 的非虚拟类？我可以传递给任何需要 Set 的函数的东西吗？我应该怎么做？

只是为了澄清 - 我不一定想做 Java 中的常见做法。但是，另一方面，如果我有一个对象，从概念上讲，它是一种集合，我想继承一些适当的东西，免费获得默认实现，并在我的 IDE 的指导下实现我应该实现的那些方法。

Answer 1

简短的回答是:没有等价物，因为 C++ 做事的方式不同。

争论没有意义，事情就是这样。如果您不喜欢这样，请使用其他语言。

长答案是:有一个等价物，但它会让您有点不高兴，因为虽然 Java 的容器和算法模型在很大程度上基于继承，但 C++ 不是。 C++ 的模型很大程度上基于通用迭代器。

比方说，以您的示例为例，您想要实现一个集合。忽略 C++ 已经有 std::set、std::multiset、std::unordered_set 和 std::unordered_multiset 这一事实、和这些都可以使用不同的比较器和分配器进行自定义，当然，无序的比较器和分配器具有可自定义的哈希函数。

假设您想重新实现 std::set。也许你是一名计算机科学专业的学生，​​你想比较 AVL 树、2-3 树、红黑树和 splay 树等。

你会怎么做？你会写:

template<class Key, class Compare = std::less<Key>, class Allocator = std::allocator<Key>> 
class set {
    using key_type = Key;
    using value_type = Key;
    using size_type = std::size_t;
    using difference_type = std::ptrdiff_t;
    using key_compare = Compare;
    using value_compare = Compare;
    using allocator_type = Allocator;
    using reference = value_type&;
    using const_reference = const value_type&;
    using pointer = std::allocator_traits<Allocator>::pointer;
    using const_pointer = std::allocator_traits<Allocator>::const_pointer;
    using iterator = /* depends on your implementation */;
    using const_iterator = /* depends on your implementation */;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>

    iterator begin() const;
    iterator end() const;
    const_iterator cbegin() const;
    const_iterator cend() const;
    reverse_iterator rbegin() const;
    reverse_iterator rend() const;
    const_reverse_iterator crbegin() const;
    const_reverse_iterator crend() const;

    bool empty() const;
    size_type size() const;
    size_type max_size() const;

    void clear();

    std::pair<iterator, bool> insert(const value_type& value);
    std::pair<iterator, bool> insert(value_type&& value);
    iterator insert(const_iterator hint, const value_type& value);
    iterator insert(const_iterator hint, value_type&& value);
    template <typename InputIterator>
    void insert(InputIterator first, InputIterator last);
    void insert(std::initializer_list<value_type> ilist);

    template <class ...Args>
    std::pair<iterator, bool> emplace(Args&&... args);

    void erase(iterator pos);
    iterator erase(const_iterator pos);
    void erase(iterator first, iterator last);
    iterator erase(const_iterator first, const_iterator last);
    size_type erase(const key_type& key);

    void swap(set& other);

    size_type count(const Key& key) const;
    iterator find(const Key& key);
    const_iterator find(const Key& key) const;

    std::pair<iterator, iterator> equal_range(const Key& key);
    std::pair<const_iterator, const_iterator> equal_range(const Key& key) const;

    iterator lower_bound(const Key& key);
    const_iterator lower_bound(const Key& key) const;
    iterator upper_bound(const Key& key);
    const_iterator upper_bound(const Key& key) const;

    key_compare key_comp() const;
    value_compare value_comp() const;
}; // offtopic: don't forget the ; if you've come from Java!

template<class Key, class Compare, class Alloc>
void swap(set<Key,Compare,Alloc>& lhs, 
          set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator==(const set<Key,Compare,Alloc>& lhs,
                const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator!=(const set<Key,Compare,Alloc>& lhs,
                const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator<(const set<Key,Compare,Alloc>& lhs,
               const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator<=(const set<Key,Compare,Alloc>& lhs,
                const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator>(const set<Key,Compare,Alloc>& lhs,
               const set<Key,Compare,Alloc>& rhs);

template <class Key, class Compare, class Alloc>
bool operator>=(const set<Key,Compare,Alloc>& lhs,
                const set<Key,Compare,Alloc>& rhs);

当然，您不必编写所有这些，特别是如果您只是编写一些内容来测试其中的一部分。但是如果你写了所有这些(为了清楚起见我排除了更多)，那么你将拥有一个功能齐全的集合类。那个 set 类有什么特别之处？

您可以在任何地方使用它。任何适用于 std::set 的东西都适用于你的集合。它不必专门为它编程。它不需要任何东西。任何适用于任何集合类型的东西都应该适用于它。 Boost 的任何算法都适用于集合。

您编写的用于集合的任何算法都将适用于您的集合、boost 集合和许多其他集合。但不仅仅是在片场。如果它们写得很好，它们将适用于任何支持特定类型迭代器的容器。如果他们需要随机访问，他们将需要 std::vector 提供的 RandomAccessIterators，但 std::list 没有。如果他们需要 BidirectionalIterators，那么 std::vector 和 std::list(和其他)将工作正常，但 std::forward_list 赢了't.

迭代器/算法/容器的东西工作得很好。考虑在 C++ 中将文件读入字符串的清洁度:

using namespace std;

ifstream file("file.txt");
string file_contents(istreambuf_iterator<char>(file),
                     istreambuf_iterator<char>{});