надо сделать библиотеку с Си-совместимым интерфейсом

допустим она будет выводить надписи на экран, и у нее будут две функции

typedef void* HTEXT;
extern "C" HTEXT add_text(int x, int y, const char* text);
extern "C" void remove_text(HTEXT hText);

внутри она будет складывать данные переданные в add_text в структуры, и затем перебирать эти структуры и рисовать надписи

struct label_data
{
   int x;
   int y;
   std::string text;
};

возможно когда-то появятся функции change_text(HTEXT hText, const char* newText),

в каком контейнере хранить данные и как выдавать хендлы?

сразу напрашиваются варианты
vector<unique_ptr<label_data>>, хендл — индекс в векторе, часть элементов вектора будет пустой;

boost::intrusive::list<label_data>, хендл — адрес элемента, ненадежно

добавляем в label_data поле handle,
list<label_data>, хендл — уникальное число — каждый новый на 1 больше предыдущего, линейный поиск;

хендл — уникальное число — каждый новый на 1 больше предыдущего,
map<int, label_data> — тот же связанный список (привет соседней теме)