从std :: vector获取特定结构对象的快速方法

我有这个简单的struct，调用了Item。从std :: vector获取特定结构对象的快速方法

struct Item { 
    unsigned int id; 
    std::string name; 

    Item() : id(0), name(std::string("")) { 

    }; 
};

然后，我有这个类来容纳所有这些Item s。

class ItemData { 
public: 
    std::vector<Item> m_Items; 
private: 
    void load() { 
     // Parse a JSON string to fill up m_Items vector with 
     // Item objects. 
    } 

    const Item getItem(unsigned int pID) { 
     // Create an "empty" Item object with ID = 0 and name = "" 
     Item temp = Item(); 

     // Loop through the vector 
     for (unsigned int i = 0; i < m_Items.size(); i++) { 
      // Check if the current Item object has the id we are looking for 
      if (m_Items.at(i).id == pID) { 
       // The item is inside the vector, replace temp with the 
       // target vector 
       temp = m_Items.at(i); 

       // Stop looping 
       break; 
      } 
     } 

     // If pID was found, temp will have the values of the object inside the vector 
     // If not, temp will have id = 0 and name = "" 
     return temp; 
    } 
};

我觉得这个方法需要太多的时间，特别是如果ItemData::getItem(unsigned int)在一个循环中调用。

是否有一种更有效的方式获取矢量内的对象，而无需通过矢量循环？我应该使用不同的容器（例如std::list）吗？

来源

2013-08-29 alxcyl

什么是您的ID的一些例子？关于不同的容器，'std :: map'具有O（log n）查找时间。 –

@DarkFalcon ID是简单的无符号整数。 '0'，'1'，'176'，'2000'是一些有效的ID。 – alxcyl

'name（std :: string（“”））'完全是多余的。 –

如果你只是想遍历容器中的所有项目，那么矢量是伟大的。如果在线性搜索并不重要的情况下进行相对较少的查找，那么矢量可能仍然可以。

如果您需要能够通过其编号查找项目并且不关心保留容器中项目的插入顺序，则可以使用map或unordered_map，具体取决于您的分类需求，容器大小，等

如果你需要保持插入顺序和通过ID 做快速查找和你会不会从载体删除项目，那么我建议ID索引的unordered_map，并维持添加新项目时的id-index映射。

来源

2013-08-29 15:55:04

我想保留插入顺序以及快速查找，但删除项目可能不需要。 – alxcyl

@LanceGray：我建议在我的回答中根据您的评论提供解决方案。 –

使用std::map代替：

class ItemData { 
public: 
    std::map<unsigned, Item> m_Items; 
private: 
    void load() { 
     // Parse a JSON string to fill up m_Items vector with 
     // Item objects. 
    } 

    const Item getItem(unsigned id) const { 
     std::map<unsigned, Item>::const_iterator it = m_Items.find(id); 
     if (it != m_Items.end()) 
      return it->second; 
     return Item(); 
    } 
};

你可以考虑std::unordered_map为好。

来源

2013-08-29 15:54:46 trojanfoe

我对''有点困惑。我可以告诉'unsigned'将是每个'Item'对象的关键字，但是不应该'unsigned'是'unsigned int'？或者它们属于同一类型？ – alxcyl

@LanceGray是的，他们是一样的。 – trojanfoe

这是编写'unsigned int'的好理由。好吧，你保存了四个按键：做得好！尽管如此，你因此丧失了清晰度。 –

绝对不是std::list。我相信你正在寻找std::map（它将唯一的ID映射到对象）。或者可能是std::set（它只是存储唯一对象）与自定义比较器，以便Item s将根据其id进行比较。

set将存储对象的缺点为const。我认为map最适合你（一次存储id作为地图密钥的开销，并且一旦进入Item的开销较低）。

来源

2013-08-29 15:56:05 Angew

我不介意我的对象是'const'，因为一旦它们被设置好，我很可能不会改变容器及其对象。 – alxcyl

我想保留插入顺序，以及快速查找，但删除项目可能会被不需要

所以，你想要的是使该向量的索引。即创建项目ID映射到向量中的项位置的哈希表：

class ItemData { 
    vector<Item> m_Items; 
    unordered_map<unsigned int, size_t> m_ItemsIndex; 

    void prepare_index() 
    { 
     for (size_t i = 0; i < m_Items.size(); i++) 
      m_ItemsIndex[m_Items[i].id] = i; 
    } 

    Item& get_item(unsigned int id) 
    { 
     size_t pos = m_ItemsIndex[id]; 
     return m_Items[pos]; 
    } 
}

这增加了查找的从线性速度（O（N）），以恒定的时间（O（1））。

在load的末尾呼叫prepare_index。你也想添加错误检查等，但你明白了。

插入顺序被保留，因为您仍然可以直接迭代矢量。

来源

2013-08-29 17:17:40

从std :: vector获取特定结构对象的快速方法

回答

相关问题