(c++) Is there any techniques using memory rearrange to increase cache hit rate?

I want to have better performance by increasing cache hit rate. I know that loop from 0 to n in something like vector is the best way of reducing cache miss, but in my application, the accessing order of the element is changing everytime, I can't use a fixed order. However, it is not totally random, I can assume that for any two continuous round of access (each round will check every element eventually), only a small part is different. I think I can use that features to reduce cache miss but I don't know if there are similar techniques or it is just worthless.

Situation Example:

struct Data{
...
}
std::vector<Data> dataList;
void Assignment(std::vector<int> dispatch_order)
{
for(int idx:dispatch_order){ do something with dataList[idx]...}
}

Call of Assignment will be like: (executing hillclimb or simulated annealing）

Assignment({0,1,2,3,4});//move 4 to [1]
Assignment({0,4,1,2,3});//move {2,3} to [0]
Assignment({2,3,0,4,1});//move 0 to last
Assignment({2,3,4,1,0});

(so I can say that most of parts are similar for any two continuous Assignment). No modification on dataList during entire computation. Elements of dataList is no more than 10000 (2000 in average?), but repetation of Assignment is over 1,000,000.

If I can rearrange the data location in dataList s.t. for(int idx:dispatch_order) will access the element Data in almost increasing order in memory space, that would be a better performance. But 'rearrange' costs, is it really a good idea? Or I can make duplication of dataList in different order, but it needs extra memory which might drop down the hit rate and I still need to change the order.