基于图环境的备选路径筛选与排序方案优化问询

咱们先回顾下常规场景中，对包装对象的std::vector进行筛选与排序的实现：

class Foo {
    Bar* bar;
    int CalcDistance(); // 基于bar操作
    std::vector<int> GetObjects(); // 基于bar操作
};
std::vector<Foo*> process() {
    std::vector<Foo*> foos = GetFoosFromSomewhere();
    std::vector<Foo*> potentialFoos;
    auto the_filter = [&](auto foo){ return foo->CalcDistance() < MAGIC_NUMBER && !foo->GetObjects().empty(); };
    std::copy_if(foos.begin(), foos.end(), potentialFoos.begin(), the_filter);
    auto the_sorter = [&](auto lhs, auto rhs){ return lhs->CalcDistance() > rhs->CalcDistance(); };
    std::sort(potentialFoos.begin(), potentialFoos.end(), the_sorter);
    return potentialFoos;
}

但现在的需求发生了变化：我们处于图环境中，针对目标顶点（Vertex）的查询会返回多条路径结果——每个目标对应多个距离值与多组对象集合。此时Foo类的接口也做了调整：

class Foo {
    Bar* bar;
    std::vector<int> CalcDistance(Vertex target); // 基于图与bar操作
    std::vector<std::vector<int>> GetObjects(Vertex target); // 基于图与bar操作
};

我们期望实现一种简洁、易表达的方式，对同一目标的备选路径进行筛选与排序，设想的伪代码如下：

// pseudo-code
Foo foo = GetFooFromSomewhere();
std::vector<Vertex> targets = GetTargetsFromSomewhere();
auto the_filter = [](Distance d, Objects o){ return d < MAGIC_NUMBER && !o.empty(); };
auto the_sorter = [](Distances d){ return d.lhs < d.rhs; };
auto alternatives = SortAndFilter(foo, targets, filter<Distance, Objects>(the_filter), sorter<Distance>(the_sorter));

目前已经尝试用可变模板与折叠表达式实现了部分功能，但存在功能未完成、表达性不足、重复造轮子的问题。最终目标是：

• 隐藏bar对象底层调用的复杂度
• 支持通过模板特化扩展查询逻辑

下面分享几个更优的实现思路：

方案一：基于Boost Graph的封装与适配 #

Boost Graph Library(BGL)本身就提供了丰富的路径查询、筛选与排序工具，我们可以基于它做一层适配，避免重复造轮子：

1. 封装路径数据结构：
   先定义一个PathResult结构体，把每个路径对应的距离、对象集合打包，同时关联到对应的Vertex目标：

   struct PathResult {
       Vertex target;
       int distance;
       std::vector<int> objects;
       // 可以根据需求添加更多路径属性
   };
   

2. 适配BGL的路径查询：
   在Foo内部封装BGL的路径查询逻辑，把CalcDistance和GetObjects的结果映射到PathResult集合中。比如：

   class Foo {
   private:
       Bar* bar;
       // 内部持有BGL的图对象或从bar中获取图
       using Graph = boost::adjacency_list<...>; // 根据实际场景选择图类型
       Graph& get_graph() { return bar->graph; }
   public:
       std::vector<PathResult> GetPathResults(Vertex target) {
           std::vector<PathResult> results;
           // 使用BGL的最短路径/多路径查询算法，比如bellman_ford或自定义多路径查询
           // 将查询到的每条路径的距离、对象集合打包成PathResult加入results
           return results;
       }
   };
   

3. 通用的筛选排序接口：
   实现一个通用的SortAndFilter函数，接收Foo、目标列表、筛选器和排序器，内部先获取所有路径结果，再统一处理：

   template<typename FilterFunc, typename SortFunc>
   std::vector<std::vector<PathResult>> SortAndFilter(Foo& foo, const std::vector<Vertex>& targets, FilterFunc filter, SortFunc sort) {
       std::vector<std::vector<PathResult>> all_results;
       for (auto target : targets) {
           auto paths = foo.GetPathResults(target);
           // 筛选
           std::erase_if(paths, [&](const PathResult& pr) { return !filter(pr.distance, pr.objects); });
           // 排序
           std::sort(paths.begin(), paths.end(), [&](const PathResult& lhs, const PathResult& rhs) { return sort(lhs.distance, rhs.distance); });
           all_results.push_back(std::move(paths));
       }
       return all_results;
   }
   

   这样调用的时候就非常简洁，和你设想的伪代码风格一致：

   Foo foo = GetFooFromSomewhere();
   std::vector<Vertex> targets = GetTargetsFromSomewhere();
   auto filter = [](int d, const std::vector<int>& o) { return d < MAGIC_NUMBER && !o.empty(); };
   auto sorter = [](int lhs, int rhs) { return lhs < rhs; };
   auto alternatives = SortAndFilter(foo, targets, filter, sorter);
   

方案二：基于模板特化的扩展机制 #

如果不想依赖Boost Graph，也可以通过模板特化来实现可扩展的查询逻辑，同时隐藏底层细节：

1. 定义查询策略基类：
   先定义一个模板基类，规定查询的接口，后续可以通过特化来扩展不同的查询类型（比如距离查询、对象集合查询，甚至自定义属性查询）：

   template<typename QueryType>
   struct QueryStrategy;
   
   // 特化距离查询策略
   template<>
   struct QueryStrategy<int> {
       static int GetValue(const Foo& foo, Vertex target, size_t path_idx) {
           return foo.CalcDistance(target)[path_idx];
       }
   };
   
   // 特化对象集合查询策略
   template<>
   struct QueryStrategy<std::vector<int>> {
       static std::vector<int> GetValue(const Foo& foo, Vertex target, size_t path_idx) {
           return foo.GetObjects(target)[path_idx];
       }
   };
   

2. 统一的路径元数据获取：
   封装一个函数，根据目标获取所有路径的元数据（比如同时获取距离和对象集合），返回一个包含所有路径属性的元组集合：

   template<typename... Props>
   auto GetPathProperties(Foo& foo, Vertex target) {
       auto dists = foo.CalcDistance(target);
       auto objs = foo.GetObjects(target);
       // 假设每个路径的距离和对象集合数量一致
       std::vector<std::tuple<Props...>> props;
       for (size_t i = 0; i < dists.size(); ++i) {
           props.emplace_back(QueryStrategy<Props>::GetValue(foo, target, i)...);
       }
       return props;
   }
   

3. 简化的SortAndFilter接口：
   基于上面的路径元数据获取，实现通用的筛选排序，同时支持模板特化扩展新的查询属性：

   template<typename FilterFunc, typename SortFunc, typename... Props>
   auto SortAndFilter(Foo& foo, const std::vector<Vertex>& targets, FilterFunc filter, SortFunc sort) {
       std::vector<std::vector<std::tuple<Props...>>> results;
       for (auto target : targets) {
           auto path_props = GetPathProperties<Props...>(foo, target);
           // 筛选
           std::erase_if(path_props, [&](const auto& props) { return !std::apply(filter, props); });
           // 排序
           std::sort(path_props.begin(), path_props.end(), [&](const auto& lhs, const auto& rhs) {
               return sort(std::get<0>(lhs), std::get<0>(rhs)); // 假设排序依据第一个属性，可灵活调整
           });
           results.push_back(std::move(path_props));
       }
       return results;
   }
   

   调用时只需要指定需要的属性类型，就能自动适配：

   auto alternatives = SortAndFilter<int, std::vector<int>>(foo, targets, filter, sorter);
   

这两种方案都能很好地满足你的需求：第一种借助Boost Graph的成熟工具避免重复造轮子，第二种通过模板特化实现高度可扩展的查询逻辑。你可以根据项目是否依赖Boost以及扩展需求来选择合适的方案。

内容的提问来源于stack exchange，提问作者ohmmega