我想讓用戶能夠定義將過濾數據的範圍。所定義的範圍可以是連續的，重疊的或分開的（例如，用戶輸入以下範圍：1-10,5-10,10-12,7-13和15-20）。C++中的數據範圍過濾器
然後我想過濾數據，以便用戶只顯示那些範圍內的內容。
我可能會在不同的圖層上創建代碼，將合適的範圍合併（因此上面的示例將變爲1-13和15-20，但我不希望我的數據服務與此有關，所以它必須能夠處理上面的例子）
我有很多的數據和速度是一個優先事項，所以我不想遍歷每個數據項的範圍列表來檢查它是否應該向用戶顯示或不顯示。
是否有一個數據結構（或某種算法）可用於實現這一目標？
如果您對範圍列表進行排序，則可以使用二進制搜索來最小化迭代。但是，真的，除非你有大量的範圍，迭代將是最快的。
您可以在您的容器中使用迭代器。例如，std :: vector提供了「at」方法。這些迭代器可以是連續的，重疊的或分離的。
讓您的列表脫節（如您所建議的），將重疊的範圍組合在一起。然後對端點數組進行排序，並對每個數據元素執行二進制搜索，並確定它是在一個範圍內還是在它之外。即使元素將始終開始一個範圍，奇怪元素將始終結束一個範圍。
HTH。
您可以使用boost的filter_iterator來實現此目的。
是不是隻是迭代每個元素的範圍過濾器，直到它得到一個是/否的答案呢？ OP表示他出於性能原因想避免這種情況。 – 2010-07-26 14:15:30
解決方案通常取決於範圍界限。
max - min不是那麼巨大（例如，您可以定義[1..1024]範圍），你可以只使用一個陣列，這點每個X到範圍列表。對於你的榜樣，數組應該是：ranges=[0:(1,10), 1:(5,10), 2:(10,12), 3:(7,13), 4:(15-20)] points=[1:[0],2:[0],3:[0],4:[0],5:[0,1],...,7:[0,1,3],...10:[0,1,2,3],...15:[4],...20:[4],21:[]...]
所以，在這種情況下，你可以quicly確定特定X的範圍
一種方法是結合收到範圍，並將它們映射到底層位圖，指示在或不在範圍內。
基於類的設計將允許您爲語法糖重載operator +=，但裸位圖也可以正常工作。例如：
# original bitmap
bits = [ 0,0,0,0,0,0,0,0,0,0 ]
# add 1-5
bits = [ 0,1,1,1,1,1,0,0,0,0 ]
# add 4 - 6
bits = [ 0,1,1,1,1,1,1,0,0,0 ]
# Look for 3
bits[3] == 1 ?
我認爲你想要做的是被稱爲Range Minimum Query。
這並不難，如果您的數據已全部排序。使用的
組合對於每個子範圍[最小值，最大值]你能找到的迭代i_min和最大電流和 使用它們作爲
std::make_pair(i_min, i_max)
使其「範圍」兼容。然後使用boost :: join將所有sub 範圍連接成單個範圍（當然是懶惰），然後在流處理中使用此範圍下行 。
顯然你應該預處理所有的範圍，以確保它們不重疊。
不會使過濾器中的範圍合理嗎？這也將簡化任務。 – pmr 2010-07-26 15:51:35
我更感興趣的是看看是否有一種解決方案不需要將它們組合起來。如果所有合理的解決方案都要求只有分開的範圍，那麼只要用戶在數據服務必須處理之前輸入數據，我就會執行此處理。 – MarkB42 2010-07-26 17:11:58