как лучше организовать контейнер для хранения IP адресов  (1-3Mb)
К одним и тем же данным Вам нужно обращаться двумя способами. Один способ — по IP, второй — по времени доступа. При этом необходимо чтобы поиск изменения в данных (смена IP в слоте данных и смена времени доступа) выполнялись быстро и эффективно.

Я бы решал эту задачу отделив сами данные (массив слотов) от индексов, через которые нужно обращаться. Если брать реализацию на С++ то примерно вот так:

// Описатель слота данных
struct CDataItem {
    __int64 accessTime; // Любое представление времени
    DWORD ip;
    BYTE  userData [64];
};

// Индекс по IP
std::map<DWORD, CDataItem *> ipIndex;

// Индекс по времени доступа
std::map<__int64, CDataItem *> accessIndex;

// Память для хранения массива слотов
CDataItem * dataArray = new CDataItem[32000];

При этом, конечно, после каждого изменения (обновления) слота придется обновлять индексы.
а чем собственно не подошел описаный вами же memcached?