inheritanceJava集合接口（Set，Map，List等）的C ++等价物是什么？ 或者扩展AbstractCollection？

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

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

现在，我在C ++中做什么（使用标准库）？ 似乎没有集合，映射，列表等的抽象基类 – 相当于Java接口; 另一方面，标准容器的实现看起来非常可怕。 好吧，也许他们一旦你了解它们就不那么可怕了，但是假设我只是想写一些类似于在C ++中扩展AbstractSet的非虚拟类？ 我可以传递给任何需要Set的函数吗？ 我应该怎么做呢？

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

Answer 1

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

没有必要争论这个问题，这只是事情的方式。 如果您不喜欢这样，请使用其他语言。

很长的答案是：有一个等价物，但它会让你有点不高兴，因为虽然Java的容器和算法模型主要基于inheritance，但C ++却不是。 C ++的模型主要基于generics迭代器。

让我们说，举个例子，你想要实现一个集合。 忽略了C ++已经有std::set ， std::multiset ， std::unordered_set和std::unordered_multiset这一事实， 并且这些都可以使用不同的比较器和分配器进行自定义，而无序的则具有可自定义的散列函数，当然。

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

你会怎么做？ 你会写：

 template, class Allocator = std::allocator> 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::pointer; using const_pointer = std::allocator_traits::const_pointer; using iterator = /* depends on your implementation */; using const_iterator = /* depends on your implementation */; using reverse_iterator = std::reverse_iterator; using const_reverse_iterator = std::reverse_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 insert(const value_type& value); std::pair insert(value_type&& value); iterator insert(const_iterator hint, const value_type& value); iterator insert(const_iterator hint, value_type&& value); template  void insert(InputIterator first, InputIterator last); void insert(std::initializer_list ilist); template  std::pair 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 equal_range(const Key& key); std::pair 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 void swap(set& lhs, set& rhs); template  bool operator==(const set& lhs, const set& rhs); template  bool operator!=(const set& lhs, const set& rhs); template  bool operator<(const set& lhs, const set& rhs); template  bool operator<=(const set& lhs, const set& rhs); template  bool operator>(const set& lhs, const set& rhs); template  bool operator>=(const set& lhs, const set& rhs); 

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

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

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

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

 using namespace std; ifstream file("file.txt"); string file_contents(istreambuf_iterator(file), istreambuf_iterator{}); 

Answer 2

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

注意：C ++不是Java。 不要尝试用C ++编写Java。 如果你想编写Java程序，编程Java：它比在C ++中尝试编程要好得多。 如果你想编程C ++，编程C ++。

Answer 3

您需要尝试放弃Java思维模式。 你看，STL的优点在于它通过迭代器将算法与容器分开。

简而言之：将迭代器传递给算法。 不要inheritance。

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

以下是所有算法： http ： //en.cppreference.com/w/cpp/algorithm

您可能希望inheritance的原因有两个：

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

要简单地触及第一点，如果需要存储一组事物（比如游戏场景中的一个对象数组），那么就这样做，将这些对象的数组作为Scene对象的成员。 没有必要inheritance子类来充分利用容器。 换句话说， 更喜欢组合而不是inheritance 。 这已经完成了死亡，并且在Java世界中被接受为做“正确的事”。 在这里看到讨论 ，它在GoF书中！ 同样的事情适用于C ++。

例：

为了解决第二点，让我们考虑一个场景。 你正在制作一个2D sidescroller游戏，你有一个Scene对象，带有一个GameObject数组。 这些GameObjects有位置，你想按位置对它们进行排序，并进行二分查找以找到最近的对象，作为一个例子。

在C ++思维模式中，元素的存储和容器的操作是两个不同的东西。 容器类为创建/插入/删除提供了最低限度的function。 上面有趣的东西都归结为算法。 它们之间的桥梁是迭代器 。 我的想法是你是否使用std::vector （相当于我认为的Java的ArrayList），或者你自己的实现是无关紧要的，只要对元素的访问是相同的 。 这是一个人为的例子：

 struct GameObject { float x, y; // compare just by x position operator < (GameObject const& other) { return x < other.x; } }; void example() { std::vector 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捕获返回的迭代器。 因此，我们可以对二进制搜索进行排序和执行。

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

我们可以为任何其他随机访问结构换出向量， 而不需要inheritance ，代码仍可正常工作：

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

供参考，请参阅我使用的function：

• 的std ::排序
• 的std :: LOWER_BOUND

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

这种方法为可扩展性提供了两个正交方向：

• 只需提供迭代器访问权限，就可以添加新容器而无需inheritance。 所有现有算法都有效 。
• 可以添加新算法。 支持这些迭代器的所有容器都将使用这些新算法，包括过去，现在或未来。

Answer 4

C ++标准库（注意：它不称为STL）有许多现有的容器类型： vector ， array ， deque ， forward_list ， list ， set ， map ， multiset ， multimap ， unordered_set ， unordered_map ， unordered_multiset ， unordered_multimap ， stack ， queue ， priority_queue 。 有可能，你只想直接使用其中一个 – 你当然不想从中得到它们。 但是，您可能需要在某些时候实现自己的特殊容器类型，如果它匹配某个接口会很好，对吧？

但不，没有一些容器派生的抽象基类。 但是，C ++标准提供了类型的要求 （有时称为概念 ）。 例如，如果您查看C ++ 11标准（或此处 ）的第23.2节，您将找到Container的要求。 例如，所有容器必须具有默认构造函数，该构造函数在常量时间内创建空容器。 然后对Sequence Containers （如std::vector ）和Associative Containers （如std::map ）有更具体的要求。 您可以对类进行编码以满足这些要求，然后人们可以按照预期安全地使用您的容器。

当然，除了容器之外，还有很多要求。 例如，该标准提供了对不同类型的迭代器，随机数生成器等的要求。

---

ISO C ++委员会（实际上是第8研究组）的许多人正在研究将这些概念作为该语言的一个特征。 该提议允许您指定需要满足的类型的要求，以便将它们用作模板类型参数。 例如，您可以像这样写一个模板函数：

 template  void foo(C container); // This will only accept sequence containers // or even just: void foo(Sequence_container container); 

但是，我认为这目前超出了你对C ++的理解。

Answer 5

在C ++中，集合（也称为容器）和对它们进行操作的通用算法以完全不知道inheritance的方式实现。 相反，连接它们的是迭代器：对于每个容器，指定它为每个算法提供的迭代器类别，说明它使用哪种迭代器类型。 因此在某种程度上，迭代器将另外两个桥接在一起，这就是STL如何将容器和算法的数量保持在最小值（N + M而不是N * M）。 容器进一步定义为序列容器（vector，deque，list（双链表）或forward_list（单链表）和关联容器（map，set，hashmap，hashset等）。序列容器关注性能（即哪个对于不同的情况，一个是更好的选择。关联容器关注事物如何存储在它们中及其结果（二叉树与散列数组）。类似的想法适用于算法。这是通用编程的要点，例如STL事实上，你必须扭曲一个纯粹的OO方法来实现平滑的generics编程。这种范式不能与Java或Smalltalk等语言愉快地搭配