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

EN

这里有两个不同的问题：

1. 如何表示您的数据结构
2. 如何在高效的庄园

中使其线程安全

您的数据结构将对每次写入进行(20-80) x (2-8)读取。

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

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

Since reads massively outnumber writes, lookup needs to be fast, while modifications don't.

Using a list for your data structure means O(N) lookups and O(1) modification - exactly the wrong way around.

The simplest possible representation of your structure is a vector. If the intervals are held in sorted order, lookups are O(logN) and modifications are O(N).

To implement this, just add a comparator to Interval:

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

You can then use std::lower_bound to find the first interval equal or lower to your search interval in O(logN).

Next and previous interval are O(1) - decrement or increment the returned iterator.

Splitting an interval means inserting a new element after the current one and adjusting the length of the current - O(N).

Joining two intervals means adding the length of the next one to the current one and erasing the next one - O(N).

You should reserve() enough space in the vector for the maximum number of elements to minimise resizing overhead.

(2). Following Knuth, 'premature optimisation is the root of all evil'.

A single read/write lock on the structure holding your vector<Interval>很可能就足够了。唯一可能的问题是(2a)，因为读取器垄断了锁，或者(2b)读取器饥饿，因为作者更新需要太长时间。

(2a)如果(并且只有在)你面临作家饥饿的情况下，你可以使锁定变得更细。但极有可能情况并非如此。为此，请执行以下操作：

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

对于读:获取集合的读锁，然后是您想要的间隔。如果不需要读取任何其他时间间隔，则在获得间隔锁后立即放弃收集锁，以允许其他线程继续执行。

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

写出来：

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

以上的工作是通过对作家的线更自私，这应该消除饥饿。

(2b)如果您面临读者饥饿，这是更不可能的，最好的解决方案是将集合写入和读取分开。按共享指针保存集合，并在其上设置一个写锁。

用于读取:获取写入锁和shared_ptr的副本。放弃写锁。读取器现在可以在没有任何锁(其不可变)的情况下读取集合。

用于写入:按照读取器将shared_ptr带到集合中，放弃锁。创建集合的私有副本并对其进行修改(因为它是私有副本，因此不需要锁)。再次使用写锁，用新集合替换现有的shared_ptr。使用旧集合完成的最后一个线程将销毁它。所有未来的线程都将使用新更新的集合。

注意，根据您的问题描述，此算法只适用于一个编写器。

并发二叉树可能是一个很好的适合，允许读取和写入不同的间隔并行进行。