我需要创建一个函数,将一个值附加到向量并返回刚刚附加的值的索引。
示例:
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
返回刚刚添加的项目的索引,那就很容易了。如何保证返回正确的索引?
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
创建包装类,以通过线程支持来扩展它。检查这个问题了解详细信息。
STL 容器不是线程安全的(即使单独调用
push_back()
),您必须自己解决这个问题 - 在 STL 之外使用一些合适的同步原语。
在 Visual Studio 2010 中,您可以使用 concurrent_vector 来实现此目的,它提供同步增长功能。 本主题列出了每个并发容器。
请注意,这些在英特尔的 TBB 中也可用,具有相同的语法 + 语义,因此可以跨平台使用。
您需要使用互斥体来保证返回正确的索引
最有力的保证解决方案是在所有此类操作上锁定整个向量(这意味着从代码中的任何位置控制每个操作,这实际上意味着创建一个同步向量)。
也许像这样简单的事情就可以满足您的目的:
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]就无效了)。您需要考虑这种情况是否会发生(也许您从代码的其余部分知道它永远不会发生)以及如果发生了该怎么办。
如果这种限制对于您的用例来说太大,那么生成完全同步的向量恐怕是我能想到的最好的。
如果您知道所需的最大大小并使用原子计数器来增加当前元素索引,则可以使用自己的容器在没有互斥锁的情况下执行此操作,例如:
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;
};