这个多线程用例的最佳数据结构:入侵列表好吗?

1. 如何表示数据结构
2. 如何使其线程安全,在一个有效的庄园

(1). 首先,假设您的范围是一个数据结构,如下所示

    struct Interval
    {
        Interval(int start, int length)
          : m_start(start),
            m_length(length)
        {}
        int m_start;
        int m_length;
        int value; // Or whatever
    };

由于读取的数量大大超过写入的数量,所以查找需要快速,而修改则不需要。

为数据结构使用列表意味着O(N)个查找和O(1)个修改-这完全是错误的方法。

结构最简单的可能表示形式是向量。如果间隔按排序顺序保持,则查找为O(logN),修改为O(N)。

要实现这一点,只需向Interval添加一个比较器:

bool operator<(const Interval& rhs) const
{
    return m_start < rhs.m_start;
}

std::lower_bound

下一个和上一个间隔是O(1)-递减或递增返回的迭代器。

拆分间隔意味着在当前间隔之后插入一个新元素,并调整当前间隔的长度-O(N)。

连接两个间隔意味着将下一个间隔的长度与当前间隔相加,并删除下一个间隔-O(N)。

reserve() 向量中有足够的空间容纳最大数量的元素,以最小化调整大小的开销。

过早的优化是万恶之源 '.

在保存向量的结构上有一个读/写锁<间隔>这很可能就足够了。唯一可能的问题是(2a)由于读卡器垄断了锁而导致写卡器饥饿,或者(2b)由于写卡器更新时间过长而导致读卡器饥饿。

(2a)如果(且仅当)您面临写入程序饥饿,您可以使锁定更细粒度。它的

使向量通过指针而不是值来保持其间隔。这样,调整大小不会在内存中移动对象。让每个间隔包含一个读/写锁。

内容如下:

如果需要读取其他存储桶,可以按任意顺序读取并锁定它们,直到放弃集合读取锁定,此时写入程序可以添加或删除未锁定的任何间隔。在获取这些锁时,顺序并不重要,因为当您持有集合上的读锁时,写入程序无法更改向量,并且读锁不会争用。

对于写入:

获取集合的写锁,然后获取所需的时间间隔。请注意,对于将添加或删除间隔的所有更新,您必须保持集合写入锁定。如果只更新一个间隔,则可以放弃收集锁。否则,您需要保持写锁,并在您要修改的任何间隔上获取写锁。您可以按任何顺序获取间隔锁,因为没有集合锁,任何读卡器都无法获取新的读取锁。

上述作品通过对作者线程更自私来实现,这应该可以消除饥饿。

内容如下: 获取写锁和共享\u ptr的副本。放弃写锁。读取器现在可以在不使用任何锁(其不可变)的情况下读取集合。

按照读卡器的要求将共享的ptr带到集合中,放弃锁。创建集合的私有副本并对其进行修改(由于集合是私有副本,因此不需要锁)。再次使用写锁,并用新集合替换现有的共享\u ptr。完成旧集合的最后一个线程将销毁它。所有将来的线程都将使用新更新的集合。

并发二叉树可能是一个很好的选择,它允许对不同时间间隔的读写并行进行。