4

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

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

所以起初我认为在我的情况下使用类似地图的结构是无关紧要的，因为在这些结构中，标识符（键）与类本身是分开的。使用映射，我必须返回 name 变量并将其复制到类“外部”（浪费内存和不合逻辑，违反 OOP 规则）。

我的下一个镜头是使用类似集合的结构。在这种情况下，我只有关键字段，我在其中加载整个对象。使用这种方法，我必须重载 <、> 和 == 运算符才能使用对象作为键。如果我使用 unordered_set，我什至可以制作一个用于散列的函子，它工作得很好。这里的问题是我不能像使用地图那样使用容器功能。这是有效mapInstance.find("example")的，这不是setInstance.find("example")。我必须创建一个将成员变量name设置为“example”的对象并将其传递给find()函数。这个解决方案的问题是我的类中的其他成员变量是重复的并且没有使用。std::string我什至尝试为and重载 <、> 和 == 运算符MyClass类，如果我像这样使用它们，效果很好stringInstance < MyClassInstance，但是容器函数无法使用（我什至尝试重载仿函数以使用字符串但没有成功）。

你能建议我一个简单的方法（或方法），如何用std::set或std::map（也许是其他人）解决这个问题？std::map关键不能是参考（据我所知），我不知道如何用std::set.

注意：在 a 的 key 字段中存储指针的问题map是，如果我们改变主意并使用unordered_map而map不是对于一个简单的任务来说似乎非常复杂）。

谢谢你的帮助！

4

2 回答 2

1

您应该问问自己对容器的要求是什么。

需要考虑的事情是：

  • 容器中通常会有多少个对象
  • 什么是内存限制
  • 多久会搜索一次对象以及可接受的复杂性？

std::map 有一些可能与您的班级冲突的要求。例如，一旦将元素添加到地图中，就不允许更改键。但是，您的班级可能每次都更改名称。从这个考虑应该很清楚， std::map 不能将字符串引用作为键。

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

于 2014-08-25T15:28:20.813 回答
1

有时，您必须建立在给出的基础上才能获得所需的结果。我建议您正在寻找适合您用例的专用适配器。

这是一个非常基本的实现，您可以在此基础上进行构建。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类来提供映射的基本复杂性保证，但将满足您通过键查找对象而不构造值类型的要求（就像您需要使用集合一样）。插入提供了更多的复杂性，但查找具有相似的复杂性。如果查找发生得更频繁，那么插入（大多数时候都是这种情况）可以很好地工作。

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您可以以任何您认为合适的方式扩展适配器。添加所需的重载以满足您的要求，模板化参数（分配器、比较、存储类型等）。

于 2014-08-25T15:41:37.827 回答