使用STL容器与包含自己键的类

Question

使用STL容器与包含自己键的类

4

我有一个对象，它可以通过名称进行识别，我想把它放在其中一个STL容器中。

class MyClass {
public:
    //getters and setters, other functions
private:
    std::string name;
    //other member variables
};

一开始我认为在我的情况下使用类似于map的结构是不相关的，因为在这些结构中，标识符（键）与类本身分离。使用map，我必须返回名称变量并将其“复制”到类之外（浪费内存且不合逻辑，违反了OOP规则）。

我接下来尝试使用类似于集合的结构。在这种情况下，我只有键字段，其中我加载整个对象。使用此方法，我必须重载<、>和==运算符，以便将对象用作键。如果我使用unordered_set，甚至可以制作一个用于哈希的函数对象，它可以正常工作。问题在于我不能像使用map那样使用容器函数。这是有效的mapInstance.find("example")，而这不是setInstance.find("example")。我必须创建一个名为“example”的成员变量设置为“name”的对象并将其传递给find()函数。该解决方案的问题在于我类中的其他成员变量会被复制但未被使用。我甚至尝试为

 std :: string 和 MyClass 类重载<、>和==运算符，如果像这样使用它们stringInstance <MyClassInstance，则可以正常工作，但容器函数无法使用（我甚至尝试重载functor以适用于字符串但没有成功）。
你能建议我一个简单的方法（或方法），如何用 std :: set 或 std :: map 解决这个问题吗？在 std :: map 中，键不能是引用（据我所知），我不知道如何用 std :: set 解决它。
注意：将指针存储在map的关键字段中的问题在于，如果我们改变主意并使用unordered_map而不是map，则哈希将基于指针而不是基于字符串计算（哈希函数可以被覆盖，但对于一个简单的任务似乎非常复杂）。
谢谢你的帮助！

- danalizieors

你是否考虑过使用find_if而不是find？ - Oliver Charlesworth

3

至少在 C++14 中，你应该能够在不构造键的情况下使用 find。 - Angew is no longer proud of SO

1

@Angew，我认为要使其工作，您需要确保提供std::less<>或其他具有is_transparent的内容，而不是使用默认的std::less。 - chris

@Angew，我想你刚刚解决了我的问题！你能给我展示一个如何在std::set上使用它的例子吗？ - danalizieors

@MarkRansom C++14已经被“主要编译器”实现了。我不知道这一点，真的很棒！我有最新的GCC编译器（我正在运行Arch），但我认为我的编译器没有正确设置。 - danalizieors

显示剩余7条评论

2个回答

1

您应该考虑您对容器的要求。

需要考虑以下几点：

通常容器中会有多少个对象
内存限制是什么
对象会被搜索多少次，哪种复杂度是可接受的？

std::map 有一些要求，这可能与您的类相冲突。例如，一旦将元素添加到映射中，就不允许更改键。然而，您的类可能每次都会更改名称。从这个考虑可以清楚地看出，std::map 无法使用字符串引用作为键。

在最简单的情况下，您可以考虑使用 std::list 和带有谓词的 std::find_if 来检查特定名称。这将具有 O(n) 的复杂度。

- oxygene

是的，我知道这个名称应该是一个常量。在我的项目中，它被实现为受保护的成员，并且没有setter函数。类的构造函数设置了名称变量。它是受保护的，因为子类可能会更改字符串。 - danalizieors

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Chad · Accepted Answer

有时候，为了达到期望的结果，你需要在现有的基础上进行构建。我建议你寻找一个专门的适配器来满足你的需求。

这是一个非常基本的实现，你可以在此基础上进行构建。在许多情况下，使用 std::vector 可以获得比使用提供类似功能集的标准容器更好的缓存局部性能力。

假设有一个简单的类型和一些辅助运算符：

struct Obj
{
   int key;
   std::string name;
};

bool operator<(const Obj& lhs, const Obj& rhs)
{
   return lhs.key < rhs.key;
}

bool operator==(const Obj& lhs, int rhs)
{
   return lhs.key == rhs;
}

bool operator<(const Obj& lhs, int rhs)
{
   return lhs.key < rhs;
}

我们可以设计一个简单的 flat_map 类，它提供了与 map 相同的基本复杂度保证，但可以通过键查找对象而无需构造值类型（就像使用 set 一样）。插入操作会增加更多的复杂度，但查找操作的复杂度类似。如果查找操作比插入操作频繁得多（这在大多数情况下是成立的），那么这个方法可以很好地工作。

class flat_map
{
public:
   using container_type = std::vector<Obj>;

   // insert object into the set
   // complexity varies based on length of container
   void insert(Obj&& obj)
   {
      container_.emplace_back(std::move(obj));
      std::sort(container_.begin(), container_.end());
   }

   // find with O(log N) complexity    
   container_type::iterator find(int key)
   {
      auto it = std::lower_bound(container_.begin(), container_.end(), key);

      if(it != container_.end() && *it == key)
         return it;

      return container_.end();
   }

private:
   container_type container_;
};

示例用法：

int main()
{
   flat_map obj;

   obj.insert({1, "one"});
   obj.insert({2, "two"});
   obj.insert({3, "three"});

   auto it = obj.find(2);

   std::cout << it->key << ' ' << it->name << '\n';
}

你可以根据需要扩展flat_map适配器。添加必要的重载以满足你的需求，模板化参数（分配器、比较器、存储类型等）。