[ddustin]

I believe the problem is simple enough to solve assuming I have the requirements correct. Essentially you need these types:

    map<int, map<int, int>> equalityIndices;
    map<int, pair<mutex, condition_variable> pendingWaits;
    mutex writeLock;

When a call to wait occurs you do:

    writeLock.lock();
    
    mutex *m;
    condition_variable *cv;
    
    if(pendingWaits.count(index1)) {
        m = &pendingWaits[index1].first;
        cv = &pendingWaits[index1].second;
    }
    else {
        m = &pendingWaits[index2].first;
        cv = &pendingWaits[index2].second;
    }
    
    equalityIndices[index1][index2]++;
    equalityIndices[index2][index1]++;
    
    writeLock.unlock();
    
    unique_lock lk(*m);
    
    do {
        cv->wait(lk);
    } while(array[index1] != array[index2]);
    
    writeLock.lock();
    
    if(--equalityIndices[index1][index2] == 0) {
        equalityIndices[index1].erase(index2);
        if(equalityIndices[index1].empty()) {
            equalityIndices.erase(index1);
            pendingWaits.erase(index1);
        }
    }
    
    if(--equalityIndices[index2][index1] == 0) {
        equalityIndices[index2].erase(index1);
        if(equalityIndices[index2].empty()) {
            equalityIndices.erase(index2);
            pendingWaits.erase(index2);
        }
    }
    
    writeLock.unlock();

Then in the update value function you do

    array[index] = value;
    
    if(equalityIndices.count(index)) {
        pendingWaits[index].second.notify_all();
        try {
            for(const auto itr : equalityIndices.at(index))
                if(array[index] == array[*itr])
                    pendingWaits[*itr].second.notify_all();
        }
        catch(out_of_range e) {
            (void)e;
        }
    }

This gives you a typical write overhead of O(log k) where k is your number of unique index equality monitors.

The wait until equal method will have a few O(log k) overheads.