原子 std::vector::push_back() 和返回索引

Question

我需要创建一个函数，它将一个值附加到一个向量并返回刚刚附加的值的索引。

示例：

int append(std::vector<int>& numbers, int number){
  int retval = numbers.size();
  // what if some other thread calls push_back(number) in between these calls?
  numbers.push_back(number);
  return retval;
}

我想以原子方式执行此操作，以便即使可能有多个线程向向量附加值，返回的索引也始终正确。如果 push_back 返回刚刚添加的项目的索引，那就很容易了。如何保证返回正确的索引？

Answer 1

std::vector 没有内置线程支持。您可以使用 boost::mutex 来扩展它：

int append(std::vector<int>& numbers, int number){
  boost::mutex::scoped_lock slock( my_lock );
  int retval = numbers.size();
  numbers.push_back(number);
  return retval;
}

您需要以这种方式保护任何读/写操作。另一种方法是为 std::vector 创建包装类，以通过线程支持来扩展它。有关详细信息，请查看此问题。

Answer 2

STL 容器不是线程安全的（即使是单独调用 push_back()），您必须自己解决这个问题 - 在 STL 之外使用一些合适的同步原语。

Answer 3

在 Visual Studio 2010 中，您可以使用 concurrent_vector 来实现此目的，它提供同步增长功能。 本主题列出了每个并发容器。

请注意，这些在英特尔的 TBB 中也可用，具有相同的语法 + 语义，因此可以跨平台使用。

Answer 4

您需要使用互斥体来保证返回正确的索引

Answer 5

最有力的保证解决方案是在所有此类操作上锁定整个向量（这意味着从代码中的任何位置控制每个操作，这实际上意味着创建一个同步向量）。

也许像这样简单的事情就可以满足您的目的：

int append(std::vector<int>& numbers, int number){
  int retval = numbers.size();
  // what if some other thread calls push_back(number) in between these calls?
  numbers.push_back(number);
  int newSize = numbers.size();
  //this bit is as a short-cut in common, easy, cases
  if(newSize = retval + 1) //no need for further complication
    return retval;
  while(++retval < newSize)
    if(numbers[retval] == number)
      return retval;
  //If we get this far, numbers have been deleted, not added. More discussion below.
}

关于这一点的一件事是，如果线程推送 3, 3, 3, 3，那么返回的索引将是错误的，尽管它仍然是 3 的索引。这是否可以取决于您的目的。

另一个是，如果向量同时被弹出或以其他方式缩短，那么最好的情况是我们只是在上面的代码中添加注释，最糟糕的是它会出错（因为它们在我们获得 newSize 后再次弹出，然后访问[retval]无效）。您需要考虑这种情况是否会发生（也许您从代码的其余部分知道它永远不会发生）以及如果发生了该怎么办。

如果这种限制对于您的用例来说太大，那么恐怕生成完全同步的向量是我能想到的最好的。

Answer 6

如果您知道所需的最大大小并使用原子计数器来增加当前元素索引，则可以使用自己的容器在没有互斥锁的情况下执行此操作，例如：

template <typename T> class atomicvector
{
public:
    atomicvector(size_t _size) :
        m_data(_size),
        m_counter(0)
    {

    }

    void clear()
    {
        #ifdef _DEBUG
        memset(m_data.data(), 0x0, m_data.size() * sizeof(T));
        #endif
        m_counter = 0;
    }

    size_t size() const
    {
        return m_counter;
    }

    const T & operator[] (size_t _index) const
    {
        return m_data[_index];
    }

    // Only 'push_atomic' is lock-free, 'size' or 'clear' shouldn't be called while the vector is being filled
    size_t push_atomic(const T & _value)
    {
        size_t index = m_counter.fetch_add(1);
        assert(index < size());
        m_data[index] = _value;
        return index;
    }

private:
    std::vector<T>         m_data;
    std::atomic<size_t>    m_counter;
};