c++利用stl set_difference对车辆进出区域进行判定

前言停车场、园区、物流仓这类场景会持续产生车辆进出记录一个常见需求是给定一段时间内的入场记录和出场记录算出当前仍在区域内的车辆。如果记录可以按车牌号排序这个问题就是一次集合差运算——入场集合减去出场集合。标准库的std::set_difference正是做这件事的算法。需要先澄清题面的范围这里的区域判定指的是基于进出记录做集合对账不是地理围栏geofencing。判断一辆车当前坐标是否落在多边形区域内属于计算几何问题std::set_difference帮不上忙它只处理两个有序区间上的多重集合差。把这两件事分开才能选对工具。另一个常见误解是认为std::set_difference会自动去重或自动按车牌聚合。它既不排序输入也不检查输入是否有序更不会理解时间先后。它只按等价关系逐元素比较两个已经排好序的区间。输入无序时标准的前置条件被违反结果没有任何保证。本文先讲std::set_difference的精确语义和前置条件再把进出记录建模成有序多重集合给出完整示例最后讨论重复进出、时间窗、异常记录这些边界情况。一、set_difference 的语义与前置条件std::set_difference声明在algorithm中典型调用形式是// 适用于 C17std::set_difference(first1, last1, first2, last2, result);它把出现在第一个区间、但不在第二个区间的元素按顺序写入result返回输出区间的尾后迭代器。标准对它的要求可以归纳为几条硬性前提两个输入区间都必须已经按同一个比较器排好序。默认比较器是operator也可以传入自定义比较器。输出区间不能与任一输入区间重叠。结果本身也是有序的顺序与输入一致。对于等价元素若第一个区间出现 m 次、第二个区间出现 n 次结果中保留max(m - n, 0)个副本。这正是多重集合multiset语义而不是简单的出现过就全删。复杂度与两个区间长度之和成线性关系即 O(N M)但前提是输入已经有序排序成本另算。第 4 条对车辆场景很关键。假如某车牌在入场记录里出现 3 次、出场记录里出现 1 次差集里会保留 2 个副本表示净入场 2 次。这不是2 辆不同的车而是同一个车牌的两条未配对记录。若业务需要车辆数必须再按车牌去重若业务需要判断是否在场只关心差集是否为空或是否包含该车牌。下面的表格对比几个容易混淆的算法算法含义结果元素个数典型用途std::set_difference在 A 中但不在 B 中每个值保留 max(m−n, 0) 个入场减出场std::set_intersection同时在 A 和 B 中每个值保留 min(m, n) 个找出两批记录都出现的车牌std::set_union出现在 A 或 B 中每个值保留 max(m, n) 个合并两段记录std::set_symmetric_difference只出现在其中一个保留两区间计数之差的绝对值个找出记录不一致的车牌这些算法都属于有序区间上的集合运算共享同一套前置条件。它们的名字里带 set但并不要求容器是std::setstd::vector、std::deque、std::multiset的迭代器都可以只要区间有序。二、把进出记录建模成有序多重集合车辆记录至少包含车牌、时间、闸口、方向四个字段。做当前在区域内的判定时最直接的模型是入场集合所有方向为进入、且属于目标区域的记录取车牌字段。出场集合所有方向为离开、且属于目标区域的记录取车牌字段。差集入场集合减去出场集合。之所以用std::multisetstd::string而不是std::setstd::string是因为同一辆车可能多次进出重复记录必须保留计数。std::multiset的迭代器按比较器有序遍历恰好满足set_difference的输入要求。// 适用于 C17#include algorithm#include iostream#include iterator#include set#include string#include vectorenum class Direction { In, Out };struct PassRecord {std::string plate; // 车牌已做过去空格、统一大写等规范化std::string gate; // 闸口/区域标识Direction dir;};// 收集指定闸口的某方向车牌天然按字符串升序排列std::multisetstd::string collect(const std::vectorPassRecord records,const std::string gate,Direction dir) {std::multisetstd::string plates;for (const auto r : records) {if (r.gate gate r.dir dir) {plates.insert(r.plate);}}return plates; // C17 起按值返回可被复制消除/移动开销可控}这里选择std::multiset而不是先std::sort一个std::vector原因是代码更直观、插入即有序。若记录量很大另一种常见做法是把车牌放进std::vector统一std::sort再用set_difference输出到另一个vector。两种做法复杂度同阶具体取舍要看插入与遍历的比例以及是否需要去重标准并不保证哪种更快应该用真实数据测量。三、完整示例计算仍在区域内的车辆下面的程序把入场集合与出场集合做差输出仍在区域内的车牌列表。为了便于阅读记录中的时间字段被省略实际系统应保留时间并用于时间窗过滤。// 适用于 C17#include algorithm#include iostream#include iterator#include set#include string#include vectorenum class Direction { In, Out };struct PassRecord {std::string plate;std::string gate;Direction dir;};std::multisetstd::string collect(const std::vectorPassRecord records,const std::string gate,Direction dir) {std::multisetstd::string plates;for (const auto r : records) {if (r.gate gate r.dir dir) {plates.insert(r.plate);}}return plates;}int main() {const std::string gate A-01;std::vectorPassRecord records{{京A12345, gate, Direction::In},{京B67890, gate, Direction::In},{京C24680, gate, Direction::In},{京A12345, gate, Direction::Out},{京B67890, gate, Direction::Out},{京D13579, gate, Direction::In},{京C24680, gate, Direction::Out},{京D13579, gate, Direction::In}, // 同一辆车再次进入};auto entered collect(records, gate, Direction::In);auto exited collect(records, gate, Direction::Out);std::multisetstd::string inside;std::set_difference(entered.begin(), entered.end(),exited.begin(), exited.end(),std::inserter(inside, inside.end()));for (const auto plate : inside) {std::cout plate \n;}std::cout records left: inside.size() \n;}按多重集合语义推演入场集合中京D13579出现 2 次出场集合中没有它差集保留 2 个副本其余三个车牌各出现 1 次且各出场 1 次差集为 0。因此输出会是两行京D13579以及records left: 2。这个结果表示有两条未配对的入场记录如果业务口径是当前在场车辆数还需要对差集按车牌去重得到 1 辆。如果想直接得到去重后的车辆集合可以再做一次转换// 适用于 C17std::setstd::string unique_inside(inside.begin(), inside.end());std::cout vehicles inside: unique_inside.size() \n;注意std::set的区间构造函数并不要求输入已经有序它会把元素逐个插入这里inside来自多重集合天然有序构造过程不受影响。这与set_difference的前置条件不同不要混淆。四、时间窗与重复进出的处理集合差只回答净数量不回答什么时候在. 真实业务常见的三个问题需要额外处理第一时间窗过滤。若要判断10 点整时区域内有哪些车不能把全天入场记录和全天出场记录直接相减因为 10 点之后的出场会把 10 点时仍在场的车辆错误减掉。正确做法是只取时间戳不晚于查询时刻的记录入场时间 ≤ T 的入场集合减去出场时间 ≤ T 的出场集合。差集中的每个副本代表一次尚未配对的进入。第二进出顺序。多重集合差忽略顺序。如果数据里存在先出场后入场的异常记录或者同一辆车在同一时刻既有进又有出差集只能给出数量上的净差无法识别逻辑矛盾。需要判断顺序时应按车牌分组、按时间排序后做栈式配对每遇到进入压栈遇到离开弹栈最后栈非空即表示仍在场。这种方式还能发现无入场记录的出场。第三车牌规范化。集合运算依赖比较器的等价关系。京A12345与京a12345、带空格与不带空格的车牌在默认operator下是不同元素会导致差集里出现本应配对却未配对的记录。应在入库时统一大小写、去除空白或者提供一个严格弱序的比较器并在所有相关排序和集合运算中使用同一个比较器。// 适用于 C17#include algorithm#include cctype#include stringstruct PlateLess {bool operator()(const std::string a, const std::string b) const {return std::lexicographical_compare(a.begin(), a.end(), b.begin(), b.end(),[](unsigned char x, unsigned char y) {return std::tolower(x) std::tolower(y);});}};一旦使用自定义比较器entry容器、exit容器以及set_difference的调用都必须传入同一个PlateLess实例否则排序顺序与比较顺序不一致算法的前提被破坏。比较器本身必须满足严格弱序对任意 a、bcomp(a, b)与comp(b, a)不能同时为真且等价关系要传递。写成是典型错误。常见坑点❌ 直接把数据库查出的记录塞进set_difference没有先排序✅ 先用std::sort或把数据放进std::set/std::multiset输入无序时标准前置条件不满足结果不可靠。❌ 入场用默认operator出场用大小写不敏感比较器✅ 两个区间必须使用同一个比较器并且该比较器满足严格弱序。❌ 把结果写回输入区间例如set_difference(v.begin(), v.end(), ..., v.begin())✅ 输出区间不能与输入重叠先写入独立的容器再用std::inserter或std::back_inserter。❌ 对空std::vector直接写set_difference(..., result.begin())✅ 输出迭代器必须可写且空间足够用std::back_inserter(result)自动扩容。❌ 认为差集大小就是当前车辆数✅ 差集保留的是未配对记录数同一车牌多次进入会产生多个副本需要再按车牌去重。❌ 用全量入场减全量出场来判断某一时刻的在场情况✅ 先按时间戳过滤只使用查询时刻之前的记录再做差集。❌ 把set_difference当成地理围栏算法传入经纬度判断是否在多边形内✅ 它只做有序区间的集合差坐标落区判断需要点在多边形内等几何算法与 STL 集合运算无关。❌ 忘记包含iterator就使用std::inserter✅std::inserter、std::back_inserter定义在iterator中std::set_difference在algorithm中。总结要点结论算法类别有序区间上的集合差不是去重工具前置条件两区间按同一比较器有序输出不与输入重叠重复元素每个值保留 max(m−n, 0) 个副本车辆场景入场多重集合减出场多重集合得到未配对记录时间语义算法本身不理解时间需先按时间窗过滤异常顺序集合差无法发现先出后进需按车牌分组配对复杂度O(NM)不含输入排序成本std::set_difference适合做两份已排序记录的对账代码短、语义清晰但它的能力边界也很明确不管时间、不做几何、不去重、不校验输入顺序。把车牌规范化、时间窗过滤和重复记录配对这些业务逻辑放在算法之外才能让这条集合运算真正可靠。