链接两个对象的明智方法

Question

我有两个对象向量：

std::vector<Foo*> fooVector; //contains some 100 elements
std::vector<Bar*> barVector; //contains some 10,000 elements

想法是 Bar 对象总是比 Foo 对象多得多。但是，每个 Foo 对象都需要与一个 Bar 对象相关联；到目前为止，这就像给每个 Foo 对象一个 Bar 指针和一个 getBar() 函数一样简单。

但是，我也需要能够做相反的事情：给定一个 Bar 对象，我需要一种方法来立即获取其关联的 Foo（如果有）。完成此操作最直接的方法是为每个 Bar 分配一个 Foo 指针。不过，这似乎非常多余，因为我将介绍 10,000 多种出错的方法（更不用说其中只有 100 种是有效的，其余的都是 nullptrs）。另一种方式，我现在有，是这样的：

Foo* getFooPtr(Bar* barObj){      
    for(auto& foo : fooVector){
        if(foo->getBar() == barObj)
            return foo;
    }
}

虽然它有效，但效率低下，因为它每次都必须遍历整个 fooVector。这个函数需要经常运行，所以这是不可接受的。

我考虑过使用 std::map 之类的东西，但最终仍然存在相同的迭代问题。

Answer 1

一个包含 10,000 个元素的向量并不是“10,000 多种出错的方式”。如果你对所有元素都做同样的事情，它只是一个更容易出错的方式 - 填充指针数据的代码。

在没有更好的方法的情况下，我会选择双重链接，只有当我对问题有更广泛的看法时，我才能设计这种方法。从更广泛的角度来看，可能存在更好的选择，可能涉及集合和映射 - 特别是如果您需要对一个 bar 的 foo 和一个 foo 的 bar 进行密集搜索。

将你的指针设置封装在一个函数中，保证这对是一致的，这样你就安全了。

特别是，您应该尝试该选项，看看它是否会给您带来具体问题。 Whosebug 将在这里解决这些问题。

错误可以改，但没写完的代码不能改，怕出错

Answer 2

如果需要减少冗余，再创建一个向量

std::vector<std::pair<Bar *, Foo *> > barFooVector

这将作为 bar 到 Foo 的 100 个案例的反向映射。

为确保您不会在指针中纠结，使用std::shared_ptr而不是裸指针更安全

std::vector<std::shared_ptr<Foo>> fooVector; //contains some 100 elements
std::vector<std::shared_ptr<Bar>> barVector; //contains some 10,000 elements
std::vector<std::pair<std::shared_ptr<Bar>, std::shared_ptr<Foo>> > barFooVector
std::vector<std::pair<std::shared_ptr<Foo>, std::shared_ptr<Bar>> > fooBarVector

此外，在这些向量上创建辅助包装器将具有高度可维护性和可扩展性

Answer 3

[...] so far, this is as simple as giving each Foo object a Bar pointer, and a getBar() function.

在这种情况下，这：

Foo* getFooPtr(Bar* barObj){      
    for(auto& foo : fooVector){
        if(foo->getBar() == barObj)
            return foo;
    }
}

是疯狂。

如果给每个 Foo 对象一个 Bar 指针，为什么不给每个 Bar 一个 Foo 指针？

class Foo
{
protected:
    Bar* _bar;

public:
    void setBar(Bar* bar);
    Bar* getBar() const;
};


class Bar
{
    friend class Foo; //allow Foo to set _foo pointer

protected:
    Foo* _foo;

public:
    Foo* getFoo() const;
};


void Foo::setBar(Bar* bar)
{
    this->_bar = bar;
    bar->_foo = this;
}

Bar* Foo::getBar() const
{
    return this->_bar;
}

Foo* Bar::getFoo() const
{
    return this->_foo;
}

每次你将 Bar 对象与 Foo 对象相关联时，两者都会自动保存此关联 - 你将能够从 Foo 获得 Bar 指针反之亦然：

Foo* f = ...;
f->setBar(...);

现在：

Bar* b = f->getBar();
Foo* bf = b->getFoo();

assert( f == bf ); //This hould always be true

Answer 4

如果您不太关心 space 复杂度并且时间复杂度是您的主要关注点，您可能想要实现一个哈希 table.

查找将为 O(1)，因为您没有存储桶，与存储 10.000 个指针（无论它们是否为空）相比，您可能会使用更少的内存。

链接两个对象的明智方法

A sensible way of linking two objects

c++

pointers

linked-list