c++ - 一堆独特元素的容器

Question

我想要做的是构建一个包含独特元素的堆栈。

如果一个元素被推送到已经在堆栈中的元素不会被推送但是现有的元素应该被移动到堆栈的顶部，即 ABCD + B > ACDB

我想从你这里得到这个功能的最佳选择。

我决定在列表上使用堆栈适配器，因为

1. list 确实为元素移动提供了恒定的时间
2. list 是堆栈本机支持的容器之一。

我选择的缺点是我必须手动检查重复元素。

PS我的编译器不是最近的所以请不要建议unordered_set。

Answer 1

基本上，您必须在恒定时间移动+长时间搜索或恒定时间搜索+长时间移动之间进行选择。

很难说哪个会更耗时，但考虑一下：

• 每次尝试添加元素时，您都必须搜索该元素是否存在
• 您不必每次都移动元素，因为显然有时您会为容器添加“新”元素。

我建议您将元素及其堆栈位置存储在不同的容器中。以提供快速搜索的方式存储元素，以提供快速移动的方式存储堆栈位置。用指针连接两者（这样你就可以知道哪个元素在哪个位置，哪个位置保存哪个元素<--混乱的短语，我知道！），你会很快地执行一些事情。

Answer 2

根据您的要求，在我看来，您想要的结构可以来自Max Heap。

如果不只存储项目，而是存储一对 (generation, item)，生成来自单调递增的计数器，那么堆的“根”始终是最后看到的元素（其他元素并不重要，是吗？）。

• pop：堆上典型的pop操作（delete-max操作）
• Push：修改操作，以说明结构内“item”的唯一性
  • 寻找“项目”，如果找到更新它的世代（increase-key操作）
  • 如果没有，插入它（insert操作）

考虑到元素的数量（20），在 a 上构建堆vector似乎是一个自然的选择。