是否可以隐藏具有提升范围的底层容器？

Question

我有一个图结构，其中顶点可以有多种类型的边。

顶点类型是多态的，它们必须能够 "classify" 边，具体取决于它们的类型并相应地存储它们，但我希望能够检索 "base level" 处的所有边，而不知道它们是如何已存储。

我正在尝试使用 boost::adaptors::transformed、boost::range::join 和 boost::any_range 来实现此目的。

这方面的一个例子：

#include <iostream>
#include <sstream>
#include <set>
#include <memory>

#include <boost/range/adaptor/transformed.hpp>
#include <boost/range/join.hpp>
#include <boost/range/any_range.hpp>

// forward declarations
class BaseVertex;
class DerivedVertex1;
class DerivedVertex2;

struct TransformCaster
{
    typedef std::shared_ptr<BaseVertex> result_type;
    std::shared_ptr<BaseVertex> operator()(std::shared_ptr<DerivedVertex1> d1) const { return std::static_pointer_cast<BaseVertex>(d1); }
    std::shared_ptr<BaseVertex> operator()(std::shared_ptr<DerivedVertex2> d2) const { return std::static_pointer_cast<BaseVertex>(d2); }
};

class BaseVertex
{
  public:
    BaseVertex(size_t id): id_(id){}
    virtual ~BaseVertex () {}

    virtual std::stringstream name()
    {std::stringstream ss; ss << "Base " << id_; return ss;}

    virtual boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> getEdges() const = 0;

  protected:
    size_t id_;

};

class DerivedVertex1 : public BaseVertex
{
  public:
    DerivedVertex1(size_t id): BaseVertex(id){}

    virtual std::stringstream name()
    {std::stringstream ss; ss << "Derived1 " << id_; return ss;}

    void addEdge1(const std::shared_ptr<DerivedVertex1>& rel)
      { relations_1_.insert(rel); }
    void addEdge2(const std::shared_ptr<DerivedVertex2>& rel)
      { relations_2_.insert(rel); }

    virtual boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> getEdges() const
    {
      // These are temporary, right?
      auto range1 = relations_1_ | boost::adaptors::transformed(TransformCaster());
      auto range2 =  relations_2_ | boost::adaptors::transformed(TransformCaster());

      auto joined_range = boost::range::join(range1, range2);

      // This is wrapping temporary transformed ranges?
      boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> poly_range(joined_range);

      return poly_range;
    }

  private:
    std::set<std::shared_ptr<DerivedVertex1>> relations_1_;
    std::set<std::shared_ptr<DerivedVertex2>> relations_2_;
};

class DerivedVertex2 : public BaseVertex
{
  public:
    DerivedVertex2(size_t id): BaseVertex(id){}

    virtual std::stringstream name()
    {std::stringstream ss; ss << "Derived2 " << id_; return ss;}

    void addEdge1(const std::shared_ptr<DerivedVertex1>& rel)
      { relations_1_.insert(rel); }
    void addEdge2(const std::shared_ptr<DerivedVertex2>& rel)
      { relations_2_.insert(rel); }

    virtual boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> getEdges() const
    {
      // These are temporary, right?
      auto range1 = relations_1_ | boost::adaptors::transformed(TransformCaster());
      auto range2 =  relations_2_ | boost::adaptors::transformed(TransformCaster());

      auto joined_range = boost::range::join(range1, range2);

      // This is wrapping temporary transformed ranges?
      boost::any_range<std::shared_ptr<BaseVertex>,boost::forward_traversal_tag> poly_range(joined_range);

      return poly_range;
    }

  private:
    std::set<std::shared_ptr<DerivedVertex1>> relations_1_;
    std::set<std::shared_ptr<DerivedVertex2>> relations_2_;
};

int main()
{

  std::shared_ptr<DerivedVertex1> derived1 = std::make_shared<DerivedVertex1>(0);
  std::shared_ptr<DerivedVertex2> derived2 = std::make_shared<DerivedVertex2>(1);

  derived1->addEdge1(derived1); // self pointing edge
  derived1->addEdge2(derived2); // edge towards other

  std::shared_ptr<BaseVertex> base = std::static_pointer_cast<BaseVertex>(derived1);

  // segfault on getEdges()
  for(auto& e : base->getEdges())
    std::cout << e->name().str() << std::endl;

  return 0;
}

这让我在 getEdges() 评估时出现段错误。据我了解，any_range 保留对临时变量 boost::adaptors::tranformed 的引用。我试图将转换适配器范围保留为 class 成员变量，但它不起作用。

是否有使用 any_range 实现此目的的正确方法？ transform_iterator / any_iterator 类型是答案还是我会遇到类似的问题？

Answer 1

错误是由于 (Trac Issue #10493)

解决方法是使 any_range 的引用类型成为常量值：

using BaseVertexRange = boost::any_range<BaseVertexPtr, boost::forward_traversal_tag, BaseVertexPtr const>;

观看演示 Live On Coliru

我可以建议对顶点使用具有变体类型的面向值的图形表示。有一个较旧的答案显示

NOTE This still leaves the design issue of leaked memory due the self-edge.

我可以建议简化单个边集合吗：

Live On Coliru

#include <iostream>
#include <memory>
#include <set>
#include <sstream>

class BaseVertex {
  public:
    BaseVertex(size_t id) : id_(id) {}
    virtual ~BaseVertex() {}

    virtual std::string name() { return "Base " + std::to_string(id_); }

    void addEdge(std::shared_ptr<BaseVertex> rel) { _relations.insert(std::move(rel)); }

    auto getEdges() const {
        return _relations;
    }

  protected:
    int id_;
    std::set<std::shared_ptr<BaseVertex> > _relations;
};

class DerivedVertex1 : public BaseVertex {
  public:
    DerivedVertex1(size_t id) : BaseVertex(id) {}

    virtual std::string name() { return "DerivedVertex1 " + std::to_string(id_); }
};

class DerivedVertex2 : public BaseVertex {
  public:
    DerivedVertex2(size_t id) : BaseVertex(id) {}

    virtual std::string name() { return "DerivedVertex2 " + std::to_string(id_); }
};

int main() {

    auto derived1 = std::make_shared<DerivedVertex1>(0);
    auto derived2 = std::make_shared<DerivedVertex2>(1);

    derived1->addEdge(derived1); // self pointing edge
    derived1->addEdge(derived2); // edge towards other

    for (auto& e : derived1->getEdges())
        std::cout << e->name() << std::endl;
}

NOTE This still leaves the design issue of leaked memory due the self-edge.

概念性思考

如果有单独的边集合的原因仅仅是因为顶点同时是不同图形的一部分，那就这样做吧！

Live On Coliru

版画

==== first graph
DerivedVertex1 0 --> DerivedVertex1 0 
==== second graph
DerivedVertex1 0 --> DerivedVertex2 1 
DerivedVertex2 1 -->

在这种情况下，我建议进一步简化：

Live On Coliru

#include <iostream>
#include <memory>
#include <set>
#include <sstream>

class BaseVertex {
  public:
    BaseVertex(size_t id) : id_(id) {}
    virtual ~BaseVertex() {}

    virtual std::string name() { return "Base " + std::to_string(id_); }
  protected:
    int id_;
};

class DerivedVertex1 : public BaseVertex {
  public:
    DerivedVertex1(size_t id) : BaseVertex(id) {}

    virtual std::string name() { return "DerivedVertex1 " + std::to_string(id_); }
};

class DerivedVertex2 : public BaseVertex {
  public:
    DerivedVertex2(size_t id) : BaseVertex(id) {}

    virtual std::string name() { return "DerivedVertex2 " + std::to_string(id_); }
};

#include <boost/graph/adjacency_list.hpp>
#include <boost/property_map/transform_value_property_map.hpp>

using Graph = boost::adjacency_list<boost::vecS, boost::vecS, boost::directedS, std::shared_ptr<BaseVertex> >;

void DebugPrint(std::string const& caption, Graph const& g);

int main() {

    auto derived1 = std::make_shared<DerivedVertex1>(0);
    auto derived2 = std::make_shared<DerivedVertex2>(1);

    Graph g1, g2;

    {
        auto v1 = add_vertex(derived1, g1);
        add_edge(v1, v1, g1);
    }

    {
        auto v1 = add_vertex(derived1, g2);
        auto v2 = add_vertex(derived2, g2);
        add_edge(v1, v2, g2);
    }

    DebugPrint("first graph", g1);
    DebugPrint("second graph", g2);
}

#include <boost/graph/graph_utility.hpp>
void DebugPrint(std::string const& caption, Graph const& g) {
    auto name_map = boost::make_transform_value_property_map(std::mem_fn(&BaseVertex::name), get(boost::vertex_bundle, g));

    boost::print_graph(g, name_map, std::cout << "==== " << caption << "\n");
}

是否可以隐藏具有提升范围的底层容器？

Is possible to hide underlying containers with boost range?

c++

c++11

boost

boost-range

概念性思考