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

Question

我已经开始使用C++进行编码,来自Java背景(实际上我在我的大学学过C++,但我们从未进入过STL等)

无论如何,我已经到了我在各种集合中安排数据的地步,我立即告诉自己"好吧,这是一种Set;这是一个List或一个ArrayList;这是地图等" 在Java中,我只想让我正在编写的任何类实现Set或Map或List接口; 但我可能不会继续继承ArrayList或HashSet,或者什么不是,那里的实现有一些参与,我不想搞砸它们.

现在,我在C++中做什么(使用标准库)？似乎没有集合,映射,列表等的抽象基类 - 相当于Java接口; 另一方面,标准容器的实现看起来非常可怕.好吧,也许他们一旦你了解它们就不那么可怕了,但是假设我只是想写一些类似于在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棵树,红黑树和树枝树.

你会怎么做？你会写:

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

当然,你不必写所有这些,特别是如果你只是写一些东西来测试它们的一部分.但是如果你写了所有这些(为了清晰起见,我会将其排除在外),那么你所拥有的将是一个功能齐全的集合类.那个集合类有什么特别之处？

你可以在任何地方使用它.任何与a一起使用的东西std::set都适用于你的套装.它不必专门为它编程.它不需要任何东西.任何适用于任何集合类型的东西都应该适用于它.Boost的任何算法都可以在集合上运行.

你编写的用于集合的任何算法都可以在你的集合和boost集合以及许多其他集合上运行.但不只是集合.如果它们被正确编写,它们将在任何支持特定类型迭代器的容器上工作.如果他们需要随机访问,他们将需要RandomAccessIterators,它std::vector提供但std::list不提供.如果他们需要BidirectionalIterators,然后std::vector和std::list(及其他)将正常工作,但std::forward_list不会.

迭代器/算法/容器的功能非常好.考虑在C++中将文件读入字符串的清洁度:

using namespace std;

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

Answer 2

标准C++库已经实现了列表,映射,集合等.C++中没有必要再次实现这些数据结构.如果您实现类似这些数据结构之一的东西,您将实现相同的概念(即,使用相同的函数名称,参数顺序,嵌套类型的名称等).容器(序列,关联容器等)有各种概念.更重要的是,您将使用适当的迭代器概念公开结构的内容.

注意:C++不是Java.不要尝试用C++编写Java.如果你想编写Java,编程Java:它比在C++中尝试编写它要好得多.如果你想编程C++,编程C++.

Answer 3

您需要尝试放弃 Java 思维方式。你看，STL 的美妙之处就在于它通过迭代器将算法与容器分开。

长话短说：将迭代器传递给您的算法。不继承。

以下是所有容器：http://en.cppreference.com/w/cpp/container

这是所有算法：http://en.cppreference.com/w/cpp/algorithm

您想要继承的原因可能有两个：

• 你想重用实现（坏主意）
• 通过使行为可用来重用现有算法（例如，从 AbstractSet 等基类继承）

简要讨论第一点，如果您需要存储一组事物（例如游戏场景中的对象数组），请准确执行此操作，将这些对象的数组作为 Scene 对象的成员。无需子类化即可充分利用容器。换句话说，更喜欢组合而不是继承。这已经被彻底执行了，并且在 Java 世界中被认为是“正确的事情”。请参阅此处的讨论，它在 GoF 书中！同样的情况也适用于 C++。

例子：

为了解决第二点，让我们考虑一个场景。您正在制作一个 2D 横向卷轴游戏，并且您有一个Scene带有 s 数组的对象GameObject。GameObjects例如，它们具有位置，您希望按位置对它们进行排序，并进行二分搜索以查找最接近的对象。

在 C++ 思维方式中，元素的存储和容器的操作是两个独立的事情。容器类提供了最基本的功能，用于创建/插入/删除。以上任何有趣的事情都属于算法。它们之间的桥梁是迭代器。这个想法是，无论你使用std::vector<GameObject>（我认为相当于Java的ArrayList），还是你自己的实现都是无关紧要的，只要对元素的访问是相同的。这是一个人为的例子：

struct GameObject {
    float x, y;

    // compare just by x position
    operator < (GameObject const& other)
    {
        return x < other.x;
    }
};

void example() {
    std::vector<GameObject> objects = {
        GameObject{8, 2},
        GameObject{4, 3},
        GameObject{6, 1}
    };
    std::sort(std::begin(objects), std::end(objects));
    auto nearestObject = std::lower_bound(std::begin(objects), std::end(objects), GameObject{5, 12});

    // nearestObject should be pointing to GameObject{4,3};
}

这里需要注意的是，我用来存储对象的事实std::vector并不像我可以对其元素执行随机访问的事实那么重要。捕获该返回的迭代器vector。结果我们可以排序并执行二分查找。

向量的本质是元素的随机访问

我们可以将向量替换为任何其他随机访问结构，而无需继承，并且代码仍然可以正常工作：

void example() {
    // using a raw array this time.
    GameObject objects[] = {
        GameObject{8, 2},
        GameObject{4, 3},
        GameObject{6, 1}
    };
    std::sort(std::begin(objects), std::end(objects));
    auto nearestObject = std::lower_bound(std::begin(objects), std::end(objects), GameObject{5, 12});

    // nearestObject should be pointing to GameObject{4,3};
}

作为参考，请参阅我使用过的函数：

• 标准::排序
• std::下界

为什么这是继承的有效替代方案？

这种方法给出了两个正交的可扩展性方向：

• 只需提供迭代器访问即可添加新容器，无需继承。所有现有算法都有效。
• 可以添加新的算法。所有支持这些迭代器的容器都将与这些新算法一起工作，无论过去、现在还是将来。