3

我有这个简单的struct叫Item.

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

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

    };
};

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

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例如）吗？

4

4 回答 4

4

使用 astd::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-29T15:54:46.883 回答
4

如果您只想遍历容器中的所有项目，那么 vector 很棒。如果您在线性搜索与性能无关紧要的情况下相对不频繁地进行查找，那么向量可能仍然可以。

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

如果您需要维护插入顺序并通过 id 进行快速查找并且您不会从向量中删除项目，那么我建议您使用unordered_mapid 来索引，并在添加新项目时维护 id-index 映射。

于 2013-08-29T15:55:04.137 回答
2

绝对不是std::list。我相信您正在寻找std::map（将唯一 ID 映射到对象）。或者也许std::set（仅存储唯一对象）与自定义比较器，以便Items 将根据它们的id.

set将对象存储为const. 我相信map最适合您（将id一次存储为映射键并且一次存储在其中的开销Item很低）。

于 2013-08-29T15:56:05.370 回答
0

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

所以你想要的是为向量创建一个索引。那就是创建一个哈希表，将项目 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))。

prepare_index结束时调用load。您还需要添加错误检查等，但您明白了。

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

于 2013-08-29T17:17:40.657 回答