0

我需要一个满足以下条件的数据结构：

  • 存储任意数量的元素，其中每个元素由 10 个数字指标描述
  • 允许log n通过任何指标快速 ( ) 搜索元素
  • 允许快速 ( log n) 插入新元素
  • 允许快速 ( log n) 移除元素

让我们假设这些元素的构建成本很高。

我想出了以下计划

  • 将所有元素存储在一个名为 DATA 的向量中。
  • 使用 10 std::sets，10 个指标中的每一个。每个std:set都是轻量级的，它只包含整数，它们是向量的索引DATA。比较运算符在 DATA 中“查找”适当的元素，然后选择适当的度量
template< int C >
struct Cmp
{
    bool operator() (int const a, int const b)
    {
        return ( DATA[a].coords[C] != DATA[b].coords[C] ) 
           ? ( DATA[a].coords[C] < DATA[b].coords[C] )
           : ( a < b );
    }
};

元素永远不会从向量中修改或删除。一个新元素被推回 DATA，然后它的索引 ( DATA.size()-1) 被插入到集合 ( set<int, Cmp<..> >) 中。为了删除一个元素，我在元素中设置了一个标志，表示它已被删除（实际上并未将其从DATA向量中删除），然后从所有十个 std::set 中删除元素索引。

只要DATA是全局变量，它就可以正常工作。（它还通过使模板化的结构 Cmp 依赖于全局变量而在某种程度上滥用了类型系统。）

但是，我无法将DATA向量和 std::set 的 ( set<int, Cmp<...> >) 包含在一个类中，然后将DATA它们“索引” std::sets。对于初学者，在外部类中定义的比较运算符 Cmp 无法访问外部类的字段（因此它无法评估 DATA）。我也无法将向量传递给 Cmp 构造函数，因为 Cmp 是由 std::set 构造的，而 std::set 需要一个带有没有参数的构造函数的比较运算符。

我有一种感觉，我正在反对 C++ 类型系统，并试图实现类型系统故意阻止我做的事情。（我试图使 std::set 依赖于仅在运行时构造的变量。）虽然我理解类型系统可能不喜欢我所做的事情，但我认为这是一个合法的用例。

有没有办法实现我上面描述的数据结构/类而不提供 std::set/red-black 树的重新实现？我希望可能有一个我还没有想到的技巧。（是的，我知道 boost 有一些东西，但我想坚持使用标准库。）

4

1 回答 1

0

当我读到“foo按值查找bar”之类的内容时，我最初的反应是使用 amap<>或类似的东西。不过，这有一些含义：

  1. an 中的键std::map（或 an 中的值std::set）是唯一的，因此没有两个元素可以共享相同的键，因此没有两个数据对象能够具有相同的度量。如果多个数据对象可以具有相同的指标（这从您的问题中不清楚），但使用std::multimap(or std::multiset) 会起作用。
  2. 如果键是常量并存储在元素本身中，则使用 aset<data*,cmp>是一种常见的方法。然后比较器只是从对象中检索相应的字段并比较它们。然后查找需要创建一个临时对象并使用 find() 。一些实现还具有允许使用不同类型进行搜索的扩展，这将使这更容易，但也使移植需要实际工作。 重要的是，用作键的字段保持不变，因为如果您修改它们，您会隐式更改set<>. 这就是 aset<>的元素实际上是常数的原因，即即使是普通的iterator有一个常量作为值类型。但是，如果您存储指针，则可以轻松解决这个问题，因为常量指针与指向常量的指针不同。不要用那个射自己的脚！
  3. 如果指标不是对象本身的属性（或者您不介意冗余存储它们），那么使用 anstd::map将是一个自然的选择。根据度量标准，将同一对象存储在多个键下可以在单独的容器中完成 ( map<int,data*> c[10];)。pair<metric,value>但是，您可以使用例如 a作为键 ( map<pair<int,int>,data*> c;)在单个映射中执行此操作。
  4. 使用 avector<>来存储实际元素并仅将它们作为映射中的指针或索引引用肯定有效。不过，我会接受指示，因为这是允许使用集合或映射的上述方法起作用的原因。没有它，比较器将不得不存储对容器的引用，此时它只使用全局 DATA 容器。但是，让它与向量一起使用很棘手，因为正如您正确指出的那样，它会在增长时重新分配其元素。我会考虑使用不同的容器类型，例如std::listor std::deque。前者也允许擦除元素，但它具有更高的每个元素开销。后者的每个元素开销相对较低，仅略高于std::vector. 然后，您甚至可以存储迭代器而不是指针，这有助于调试，前提是您为此使用“已检查的 STL”。尽管如此，您仍需要手动记录哪些对象仍然在某处被引用，而哪些对象没有被引用。
  5. 除了使用单独的容器，您还可以动态分配元素，尽管这本身有一些开销。如果每个元素的开销不是问题，则可以使用引用计数智能指针。如果应用程序是一次性进程，您还可以使用原始指针并让操作系统在退出时回收内存。

请注意，我假设存储数据对象的多个副本不是一种选择。如果是这种情况，您也可以拥有一个map<int,data> m[10];，其中每个地图都存储自己的数据对象副本。所有的簿记问题都将得到解决，但代价是 10 倍的开销。

于 2014-06-25T19:44:37.447 回答