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

Question

我有一个简单的结构体叫做Item。

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

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

    };
};

然后我有一个类来保存所有这些Item。

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）？

- alxcyl

---

你的ID有哪些例子？关于另一个容器，std::map 具有 O(log n) 的查找时间。 - Dark Falcon

@DarkFalcon IDs只是无符号整数。0，1，176，2000是一些有效的ID。 - alxcyl

name( std::string( "" ) ) 是完全多余的。 - Lightness Races in Orbit

@LightnessRacesinOrbit 我明白了，我会记住的。 - alxcyl

@JohnDibling：你说的“它替换了它”是什么意思？ - Lightness Races in Orbit

Answer 1

使用 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。

- trojanfoe

---

我对 <unsigned, Item> 有点困惑。我知道 unsigned 将是每个 Item 对象的键，但是 unsigned 不应该是 unsigned int 吗？或者它们是相同类型的吗？ - alxcyl

@LanceGray 是的，它们是相同的。 - trojanfoe

这是写unsigned int的一个很好的理由。好吧，你省了四个按键：干得好！但是，这样做会降低代码的清晰度。 - Lightness Races in Orbit

Answer 2

如果您只想遍历容器中的所有项，则使用vector很好。如果您偶尔需要查找，线性搜索不会影响性能，那么使用vector可能仍然可以接受。

如果您需要能够通过其ID查找项目，并且不关心容器中项目的插入顺序，则根据您的排序需求、容器大小等，使用map或unordered_map。

如果您需要维护插入顺序并快速查找ID，而且不会从向量中删除项，则建议使用id到索引的unordered_map，并在添加新项时维护id-index映射。

- Mark B

---

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

@LanceGray：根据您在我的答案中的评论，我建议一个解决方案。 - Andrew Tomazos

Answer 3

绝对不是使用 std::list，我相信你要找的是 std::map（将唯一的 ID 映射到对象）。或者使用带有自定义比较器的 std::set（仅存储唯一的对象），以便根据它们的 id 来比较 Item。 set 的缺点是将对象存储为 const。我认为 map 最适合您（将 id 作为映射键和 Item 内部的两次存储的开销很低）。

- Angew is no longer proud of SO

---

我不介意我的对象被声明为const，因为一旦它们被设置好，我很可能不会修改容器及其对象。 - alxcyl

Answer 4

我想保留插入顺序以及快速查找，但可能不需要删除项目。因此，您想为向量创建索引。也就是说，创建一个哈希表，将项目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。当然，您还需要添加错误检查等，但您已经有了想法。

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

- Andrew Tomazos