Boost::Multi_Index 运行总数

Question

首先，对于格式不佳，我深表歉意，我是新手，知道我没有把它弄得漂亮。

我正在实施一个系统来跟踪我存储为块的订单，但我还没有获得使用模板的经验来完全理解参考文档。（我已经尽我所能通读了这本书，并且对 Joaquin 赢得了很多尊重。似乎没有带有排名复合键的示例）

struct Block{//Variable types apart from the bool are immutable, values may be modified though
/*  
This is to replace the previous lookup structure consisting of a map of buys and sells, to a map of products, to a map of prices, to a map of priorities, pointing to a struct holding the blockID and quantity

For a modify, if they are changing products or prices, it will create a new order, else they can shrink quantity desired without changing the priorityAtPrice
If they want to increase the quantity they lose their priority, but the order will keep the other values
*/
    const int32_t productID; //One of ~20 different products 
    mutable uint32_t orderQuantity;//Number of products wanted at that price
    const int64_t desiredPrice; //Prices are not unique
    mutable uint64_t priorityAtPrice;//It's a global priority, in case someone alters their order
    const uint64_t blockID;//Unique to every block
    bool buy;//Tag to note if they are a looking to sell or buy

    bool operator<(const Block& lilBlock)const{return blockID<lilBlock.blockID>}

};
struct idHash{
    uint64_t operator()(const Block& lilBlock)const{
        return lilBlock.blockID;
    }
}
struct ObtainElementByBlockID {};
struct ObtainSublistByProductAndPrice {};
struct PlaceInLine {};
struct randomAccess {};

typedef boost::multi_index_container<
Block*,//Data type being stored, in this case, it is a pointer to Block.
//I'd like to store the block objects in an array[size uint64_t] indexed by the BlockIDs, since they are unique and will be accessed often, so keeping as much in cache is desirable
boost::multi_index::indexed_by<
    boost::multi_index::hashed_unique<//Ideally should be fed an ID and retrieve the orderBlock in O(1) time
    //It is never needed to compare IDs beyond checking if that is the ID being queried for
        boost::multi_index::tag<ObtainElementByBlockID>
        ,boost::multi_index::member<Block,uint64_t, blockID>
        ,idHash
    >
    ,boost::multi_index::random_access<
        boost::multi_index::tag<randomAccess>
        ,boost::multi_index::member<Block,uint64_t,blockID>
    >   
    ,boost::multi_index::ordered_non_unique<//Should return a sublist at a product/price pair ordered by priorityAtPrice
        boost::multi_index::tag<ObtainSublistByProductAndPrice>
        ,boost::multi_index::composite_key<
            Block,
            boost::multi_index::member<Block, int32_t, &Block::productID>
            ,boost::multi_index::member<Block, int64_t, &Block::desiredPrice>
            ,boost::multi_index::member<Block, uint64_t, &Block::priorityAtPrice>
        >
        ,boost::multi_index::composite_key_compare<
            std::equal<int32_t>
            ,std::equal<uint64_t>
            ,std::less<uint64_t>
        >
    >
    /*
    I think what I want has to do with rank
    At product/price/buy, the value returned should be the sum of the quantities with a lower priority. 

    Say at   [chairs, 5$, buy=true]   there are orders(priority,quantity)
    such that {(2,5),(6,12),(896, 3)}
    with block IDs {753, 54, 712}
    Querying for the place in line of a block, given the blockID 712
    It should return 17, since there are orders ahead of block 712 with quantities 5+12=17
    (It might actually need to return 18, but that's trivial)
    */
    ,boost::multi_index::ranked_non_unique<
        boost::multi_index::tag<PlaceInLine>
        ,boost::multi_index::composite_key<
            Block,
            boost::multi_index::member<Block, int32_t, &Block::productID>
            ,boost::multi_index::member<Block, int64_t, &Block::desiredPrice>
            ,boost::multi_index::member<Block,priorityAtPrice>
        >
        ,boost::multi_index::composite_key_compare<
            std::equal<int32_t>
            ,std::equal<uint64_t>
            ,std::less<uint64_t>
        >
    >

> BlockDatabase;

我需要帮助确保我的 multi_index 格式正确。

P.S。 - 如果能从给定的 product/price 中快速提取买入或卖出的数量总和，我们将不胜感激。

Answer 1

您的 post 没有提供 MCVE 并且其中的代码确实有一些错误，即使在添加需要额外的代码（headers 和东西）。

所以，我重写了修复过程中发现的错误的东西，你可以在下面找到结果。关于你的主要问题，你不需要排名指数，有序指数就足够了。你想要的是具有相同 productID、desiredPrice 和 buy/sell 标记且比给定块低 priorityAtPrice 的 orderQuantity 个块的总和：你然后需要一个按 (productID、desiredPrice、buy、priorityAtPrice):

对块进行分组的索引

boost::multi_index::ordered_non_unique<
    boost::multi_index::tag<ObtainSublistByProductPriceAndBuy>
    ,boost::multi_index::composite_key<
        Block,
        boost::multi_index::member<Block, const int32_t, &Block::productID>
        ,boost::multi_index::member<Block, const int64_t, &Block::desiredPrice>
        ,boost::multi_index::member<Block, bool, &Block::buy>
        ,boost::multi_index::member<Block, const uint64_t, &Block::priorityAtPrice>
    >
>

以及一个检索适当范围并计算数量总和的函数：

uint32_t placeInLine(const BlockDatabase& bd, const Block& b)
{
    auto& index = bd.get<ObtainSublistByProductPriceAndBuy>();
    auto  first = index.lower_bound(
        std::make_tuple(b.productID, b.desiredPrice, b.buy));
    auto  last  = index.lower_bound(
        std::make_tuple(b.productID, b.desiredPrice, b.buy, b.priorityAtPrice));
    return std::accumulate(
      first, last, uint32_t(0),
      [](uint32_t n, const Block* pb){ return n + pb->orderQuantity; });
}

完整示例如下。

Live On Coliru

#include <array>
#include <boost/multi_index_container.hpp>
#include <boost/multi_index/composite_key.hpp>
#include <boost/multi_index/hashed_index.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#include <boost/multi_index/random_access_index.hpp>
#include <iostream>
#include <numeric>

struct Block{

    const int32_t productID;
    mutable uint32_t orderQuantity;
    const int64_t desiredPrice;
    mutable uint64_t priorityAtPrice;
    const uint64_t blockID;
    bool buy;

    bool operator<(const Block& lilBlock)const{return blockID<lilBlock.blockID;}
};

struct ObtainElementByBlockID {};
struct RandomAccess {};
struct ObtainSublistByProductAndPrice {};
struct ObtainSublistByProductPriceAndBuy {};

typedef boost::multi_index_container<
Block*,
boost::multi_index::indexed_by<
    boost::multi_index::hashed_unique<
        boost::multi_index::tag<ObtainElementByBlockID>
        ,boost::multi_index::member<Block,const uint64_t,&Block::blockID>
    >
    ,boost::multi_index::random_access<
        boost::multi_index::tag<RandomAccess>
    >   
    ,boost::multi_index::ordered_non_unique<
        boost::multi_index::tag<ObtainSublistByProductAndPrice>
        ,boost::multi_index::composite_key<
            Block,
            boost::multi_index::member<Block, const int32_t, &Block::productID>
            ,boost::multi_index::member<Block, const int64_t, &Block::desiredPrice>
            ,boost::multi_index::member<Block, const uint64_t, &Block::priorityAtPrice>
        >
    >
    ,boost::multi_index::ordered_non_unique<
        boost::multi_index::tag<ObtainSublistByProductPriceAndBuy>
        ,boost::multi_index::composite_key<
            Block,
            boost::multi_index::member<Block, const int32_t, &Block::productID>
            ,boost::multi_index::member<Block, const int64_t, &Block::desiredPrice>
            ,boost::multi_index::member<Block, bool, &Block::buy>
            ,boost::multi_index::member<Block, const uint64_t, &Block::priorityAtPrice>
        >
    >
>
> BlockDatabase;

uint32_t placeInLine(const BlockDatabase& bd, const Block& b)
{
    auto& index = bd.get<ObtainSublistByProductPriceAndBuy>();
    auto  first = index.lower_bound(
        std::make_tuple(b.productID, b.desiredPrice, b.buy));
    auto  last  = index.lower_bound(
        std::make_tuple(b.productID, b.desiredPrice, b.buy, b.priorityAtPrice));
    return std::accumulate(
      first, last, uint32_t(0),
      [](uint32_t n, const Block* pb){ return n + pb->orderQuantity; });
}

int main()
{
    const int32_t chairsID = 0;

    auto blocks = std::array{
      Block{chairsID,  5, 5,   2, 753, true},
      Block{chairsID, 12, 5,   6,  54, true},
      Block{chairsID,  3, 5, 896, 712, true}
    };

    BlockDatabase bd;
    for(auto& b: blocks) bd.insert(&b);

    // retrieve block with blockID 712
    auto it = bd.find(712);

    // output sum of quantities for blocks with same productID, desiredPrice
    // and buy tag and lower priorityAtPrice
    std::cout << placeInLine(bd, **it) << "\n";
}

输出

Boost::Multi_Index 运行总数

Boost::Multi_Index running totals

c++

boost

multi-index

latency