[pva]

Если можно использовать стандартную библиотеку C++:

Код:

#include <string>
#include <map>
using namespace std;

// если я правильно понял, должно быть так:
// поиск по дереву ключ=строка(уникальная) ->
//    список из пар <строка, список чисел> ->
//       добавляем, удаляем всякую фигню, но не делаем быстрого поиска

// список чисел
typedef vector<int> number_list_type;
// список пар строка-number_list_type
typedef list<pair<string, number_list_type> > number_w_key_list_type;
// дерево для поиска по ключу
typedef map<string, number_w_key_list_type> key_list_by_str_type;

// эта переменная содержит нужную структуру (по идее задача уже выполнена)
key_list_by_str_type key_list_by_str;

// как ей пользоваться?
// заполняем
static const char s1[] = "s1";
static const int i1[] = {1, 2, 3, 4};
static const char s2[] = "s2";
static const int i2[] = {5, 6};
static const char s3[] = "s3";
static const int i3[] = {7, 8, 9};
static const char s4[] = "s4";
static const int i4[] = {10};

void add_str(number_w_key_list_type& result, char const* str, int const* first, unsigned count)
{
	// добавляем пустой список, потом заполняем его доюавлением массива в конец
	copy(first, first+count, back_inserter<number_list_type>(
		*result.insert(result.end(), make_pair(string(s1), number_list_type())));
}

// это место можно очень хорошо свернуть в один цикл

add_str(key_list_by_str["key1"], s1, i1, sizeof(i1)/sizeof(i1[0]));
add_str(key_list_by_str["key1"], s2, i2, sizeof(i2)/sizeof(i2[0]));
add_str(key_list_by_str["key1"], s3, i3, sizeof(i3)/sizeof(i3[0]));
add_str(key_list_by_str["key2"], s4, i4, sizeof(i4)/sizeof(i4[0]));
key_list_by_str["key4"]; // пустой

теперь вопрос: какая физическая постановка задачи? мне эта структура кажется громоздкой и неудобной. Есть ещё куча замечательных шаблонов, например multimap, который позволяет хранить в сортированном дереве дубли. Поясни смысли задачи, может подскажу более удобную структуру. Если внутри тоже надо поиск по строке, то можно сделать map<string, multimap<string, int> > или map<string, map<string, vector<int> > >. В последнем случае работа с такой структурой напоминает работу с массивом

Код:

map<string, map<string, vector<int> > > my_data;
my_data["outer key"]["inner key"].push_back(10);

единственное неудобство - это operator[] добавляет элемент, если такой не найден. А чтобы не добавлять, нужно делать сложнее:

Код:

map<string, map<string, vector<int> > >::iterator found_outer;
map<string, vector<int> >::iterator found_inner;

if (my_data.end()!=(found_outer=my_data.find("outer key")) &&
	found_outer->second.end()!=(found_inner=found_outer->second.find("inner key")))
{
	// работа с найденным вектором
	// found_inner->second - это LVALUE vector<int>
	cout << "{";

	vector<int>::iterator
		out_first = found_inner->second.begin(),
		out_last  = found_inner->second.end();

	if (out_first!=out_last)
	{
		if (out_first!=--out_last) copy(out_first, out_last, ostream_iterator<char>(cout, ", "));
		cout << out_last;
	}

	cout << "}";

}
else
{
	cout << "- not found -";
}

cout << "\n";