Atomically std::vector::push_back() and return index

Question

I need to create a function which appends a value to a vector and returns the index of the value that was just appended.

Example:

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;
}

I would like to do this atomically so that the returned index is always correct even when there may be multiple threads appending values to the vector. It would have been easy if push_back returned the index of the item just added. How can I guarantee that the correct index is returned?

Gottwald

Actually, it would not be easy if push_back() returned an index, as push_back() itself is not thread safe – Tungus

You need to protect your container against all concurrent writes. Concurrent plain push_back() already needs vector-external synchronization – Bander

Bear in mind that for many real-world applications, making small thread-safe operations is not the right solution: you should consider protecting larger chunks of code. Thread-safe collections are good if you are using them as a communication mechanism. That said, this may well be such a case. – Transcendentalistic

Answer 1

std::vector has no built in thread support. You could use boost::mutex to extend it:

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;
}

You need to protect any read/write operation in such way. Another way is to create wrapper class for std::vector that will extend it with thread support. Check this question for details.

Ixtle

How does this work when another thread does something with the vector other than call this function? Another thread calling numbers.clear() isn't going to honour the scoped_lock here. – Suzan

This will work, but it will only secure this single operation. Anyone can do a push_back() somewhere else on the same object and get it broken. – Darryl

One need to protect any read/write operation. May be OP should create wrapper class for std::vector that will extend it with thread support. Check this question for details. – Ixtle

Answer 2

STL containers are not thread-safe (even the call to push_back() alone), you'll have to solve this problem on your own - use some suitable synchronization primitives outside STL.

Darryl

Answer 3

In Visual Studio 2010, you can use a concurrent_vector for this in , it offers synchronized grow functionality . This topic lists each of the concurrent containers.

Note that these are also available in Intel's TBB with identical syntax + semantics and as such are available cross platform.

Calcify

Answer 4

You need to use a mutex to guarantee that the correct index is returned

Kellby

This is really a comment, not an answer to the question. Please use "add comment" to leave feedback for the author. – Highroad

Disagree. I believe this is an answer. The accepted answer also gives the same advice but with an example. – Kellby

Answer 5

The strongest-guarantee solution is to lock the entire vector on all such operations (which means controlling every operation from everywhere in the code, which really means creating a synchronised vector).

It may be that something as simple as this will do for your purposes:

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.
}

One thing about this is that if threads push 3, 3, 3, 3 then the index returned will be wrong, though it will still be an index to a 3. Whether that's okay or not depends on your purposes.

Another is that if the vector is popped or otherwise shortened in the meantime, then at best we get to the point where I just put a comment in the code above, at worse it errors (as they pop again after we obtain newSize, and then accessing [retval] becomes invalid). You need to consider if this case can happen (maybe you know from the rest of the code that it never will) and what to do if it does.

If the limitations of this are too great for your use case, then producing a fully synchronised vector is the best I can think of I'm afraid.

Suzan

Answer 6

You can do this without Mutex with your own container if you can know the maximum required size and use an atomic counter to increment the current element index, e.g. :

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;
};

Amperage