Why is replacing an element of a vector so slow?

I notice that amending (or replacing) an element in a large vector is consuming a lot of time when the vector is getting bigger, even when the element's place in the vector is known.

Is there an explanaition for this?

I use an unsorted set as an index. The code first tries to find the element in the set with set.find(). If the element not present in the set the code insert it at the end of the set and at the same time pushes it at the end of the vector. If the element is found on position "x" of the set the data in the vector is replaced by using:

vector.at(x)=vector[x]+element.

When I skip the vector part and only insert the element in the set the code easily processes 95 million elements in less then 2 minutes. But when I add the vector part to it the code keeps on running for hours.