Что мне приходит в голову, так это то, что если у вас есть один и тот же объект для диапазона индексов 0-99 - может быть какая-то функция хеширования, а затем ассоциативный контейнер. Например,
int readdress(int index)
{
if(index < 100) return 0;
...
}
а затем карту, чтобы перечислить 0 указатель в фактический объект.
Однако - я подозреваю, что функция readress не может быть определена как функция (диапазон адресов все время меняется)
То, что я мог бы предложить - это один пользовательский класс, который я сделал когда-то для управления диапазоны индексов - однако - этот класс имеет некоторые ограничения - мне нужно только указать, является ли данный индекс «свободным» или «назначенным» типом, но может быть типом, который может быть заменен каким-то индексом, и они сопоставлены самому объекту (так что замените char с вашим собственным указателем типа).
Я подозреваю, что мой класс может быть не лучшей альтернативой, поэтому, пожалуйста, не будьте грубыми по завершении, это может быть полезно кому-то тогда.
FreeSpace.h:
#pragma once
#include <vector>
using std::vector;
typedef __int64 int64;
typedef struct Slice_
{
Slice_(char t, int64 p, int64 s) : type(t), pos(p), size(s) { }
int64 size;
int64 pos;
char type; //'f' - for free, 'a' - for allocated.
}Slice;
class FreeSpace
{
public:
FreeSpace();
void specifySlice(char type, int64 pos, int64 size);
void _specifySlice(char type, int64& pos, int64& size, int& i);
int64 getTotalSlicesSize(char type);
void printMap(void);
void Clear(void);
void RunTest(const char* name, Slice* ptests, int nTests);
void CheckMap(const char* name, Slice* ptests, int nTests, int* testCounters);
bool RunSelfTest(void);
vector<Slice> slices;
int64 fileSize;
int64 lastAllocEndPos;
bool bDoDebug;
}; //class FreeSpace
FreeSpace.cpp:
#include <afx.h>
#include <afxstr.h> //CString
#include <Windows.h>
#include "FreeSpace.h"
#include <assert.h>
FreeSpace::FreeSpace() :
bDoDebug (false)
{
}
void FreeSpace::specifySlice(char type, int64 ipos, int64 isize)
{
Slice* nextSlice;
Slice* prevSlice;
int i;
if(bDoDebug)
printf("- %s storage from pos %lld, by size %lld\n", (type == 'f') ? "Freeing" : "Allocating", ipos, isize);
_specifySlice(type, ipos, isize, i);
ipos = slices[i].pos;
isize = slices[i].size;
assert(type == slices[i].type);
// Checks if slices can be recombined.
if(i + 1 != slices.size()) nextSlice = &slices[i+1];
else nextSlice = 0;
if(i != 0) prevSlice = &slices[i-1];
else prevSlice = 0;
// Can we recombine with previous allocation
if(prevSlice != 0 && prevSlice->pos + prevSlice->size == ipos && prevSlice->type == type)
{
// Can combine with previous allocation.
slices.erase(slices.begin() + i);
prevSlice->size += isize;
i--;
}
// ---[# 1 #][# 2 #]-------
// Can we recombine with next allocation
if(nextSlice != 0 && nextSlice->pos == ipos + isize && nextSlice->type == type)
{
// Can combine with next allocation.
slices[i].size += nextSlice->size;
slices.erase(slices.begin() + i + 1);
}
}
void FreeSpace::_specifySlice(char type, int64& ipos, int64& isize, int& i)
{
int64 last = ipos + isize;
Slice* nextSlice;
Slice* prevSlice;
for(i = 0; i < slices.size(); i++)
{
Slice& slice = slices[i];
if(i + 1 != slices.size()) nextSlice = &slices[i+1];
else nextSlice = 0;
if(i != 0) prevSlice = &slices[i-1];
else prevSlice = 0;
// ---[######]----------------
// ^------^
// Our allocation starts from same place as current allocation
if(ipos == slice.pos)
{
// Our allocation is the same size.
if(isize == slice.size)
{
if(type == slice.type) // Nothing changed test1
return;
// Type changed.
slice.type = type; // test1
return;
}
// ---[######]----------------
// ^----------^
if(last > slice.pos + slice.size)
{
slices.erase(slices.begin() + i); // Covered by our allocation - test2
i--;
continue;
}
// ---[##############]--------
// ^----------^
if(type == slice.type)
return; // test3
slice.size = slice.pos + slice.size - last; // test3
slice.pos = last;
break; // Insert our slice
}
// ----------------------[#######]----
// ^----------^
// Our allocation comes before this allocation
if(last <= slice.pos) // And will not reach this allocation.
{
// ------------------[#######]----
// ^----------^
if(last == slice.pos)
break; // test13
// ------------------[#######]---- test5
// ^------^
if(slice.pos > last)
break; // test16
}
// ---------------[#######]----
// ^----------^
// Our allocation comes before this allocation
if(ipos < slice.pos)
{
// ---------------[#######]----
// ^----------^
if(last < slice.pos + slice.size)
{
if(type != slice.type)
{
// Shrink current allocation. test7
slice.size = slice.pos + slice.size - last;
slice.pos = last;
break; // Insert our slice
} else {
// Glow current allocation. test8
slice.size = slice.pos + slice.size - last + isize;
slice.pos = ipos;
return;
} //if-else
} //if
// ---------------[#######]----
// ^---------------^
if(last >= slice.pos + slice.size)
{
// ---------------[#######]----
// ^---------------^
if(last == slice.pos + slice.size)
{
slices.erase(slices.begin() + i); // Covered by our allocation - test6
break; // Insert our slice
}
// ---------------[#######]---- - test9, test10
// ^------------------^
slices.erase(slices.begin() + i); // Covered by our allocation.
i--;
continue;
} //if
} //if
// ---[######]----------------
// ^----^
// Our allocation passed completely previous allocation
if(ipos >= slice.pos + slice.size)
// Slice is not affected by our allocation, continue search next slice.
continue; // test1
// ---[#######]--------------------
// ^----------^
// Our allocation passed partially previous allocation
if(ipos > slice.pos)
{
// ---[############]-----------
// ^--------^
// Our allocation ends with current allocation in same place
if(last == slice.pos + slice.size)
{
if(type == slice.type)
return; // Nothing changed. test12
slice.size = ipos - slice.pos; // test4
i++;
break; // Insert our slice
} //if
// ---[############]-----------
// ^-----^
// Our allocation is completely within current allocation
if(last < slice.pos + slice.size)
{
if(type == slice.type)
return; // Same kind, nothing new. - test11
// We have some chopped one slice into two - test1
slices.insert(slices.begin() + i, Slice(slice.type,slice.pos, ipos - slice.pos));
i++;
Slice& slice = slices[i];
slice.size = slice.pos + slice.size - last;
slice.pos = last;
break; // Insert our slice
} //if
// ---[############]-----------
// ^---------------^
// Our allocation goes beyond current allocation
if(type == slice.type)
{
isize += (ipos - slice.pos); // test7
ipos = slice.pos; // Will recombine our slice into bigger slice.
slices.erase(slices.begin() + i);
i--;
continue;
}
// Different type.
slice.size = (ipos - slice.pos); // Make current slice smaller one, continue scan test6
continue;
}
} //for
// Simply add slice at that area range.
slices.insert(slices.begin() + i, Slice(type, ipos, isize));
} //addSlice
int64 FreeSpace::getTotalSlicesSize(char type)
{
int64 total = 0;
for(int i = 0; i < slices.size(); i++)
{
Slice& slice = slices[i];
if(slice.type == type)
total += slice.size;
}
return total;
}
void FreeSpace::printMap(void)
{
int64 totsize = 0;
printf("Type Start addr End addr Size\n");
for(int i = 0; i < slices.size(); i++)
{
Slice& slice = slices[i];
totsize += slice.size;
printf("%c %08lld %08lld %08lld", slice.type, slice.pos, slice.pos + slice.size - 1, slice.size);
if(i+1 == slices.size())
printf(" (%lld)", totsize);
printf("\n");
}
}
void FreeSpace::Clear(void)
{
slices.clear();
}
void FreeSpace::RunTest(const char* name, Slice* ptests, int nTests)
{
Clear();
if(bDoDebug)
printf("****************** %s ******************\n", name);
for(int i = 0 ; i < nTests; i++)
{
specifySlice(ptests[i].type, ptests[i].pos, ptests[i].size);
if(bDoDebug)
printMap();
}
}
void FreeSpace::CheckMap(const char* name, Slice* ptests, int nTests, int* testCounters)
{
bool bPassed = true;
if(slices.size() != nTests)
bPassed = false;
else
for(int i = 0 ; i < nTests; i++)
{
if(
ptests[i].pos != slices[i].pos ||
ptests[i].size != slices[i].size ||
ptests[i].type != slices[i].type)
{
bPassed = false;
break;
}
}
testCounters[ bPassed ? 0: 1 ]++;
if(bPassed)
return;
CStringA found;
CStringA expected;
for(int i = 0 ; i < slices.size(); i++)
{
found.AppendFormat("Slice('%c', %lld, %lld)", slices[i].type, slices[i].pos, slices[i].size);
if(i+1 != slices.size())
found += ",";
}
for(int i = 0 ; i < nTests; i++)
{
expected.AppendFormat("Slice('%c', %lld, %lld)", ptests[i].type, ptests[i].pos, ptests[i].size);
if(i+1 != slices.size())
expected += ",";
}
if(bDoDebug)
{
printf("Test '%s' failed - expected:\n", name);
printf(" %s\n", expected.GetBuffer());
printf("found:\n");
printf(" %s\n", found.GetBuffer());
}
}
#define RUNTEST(testid, ...) \
Slice testid[] = { ##__VA_ARGS__ }; \
RunTest(#testid, testid, sizeof(testid)/sizeof(testid[0]));
#define CHECKTEST(testid, ...) \
Slice chk##testid[] = { ##__VA_ARGS__ }; \
CheckMap(#testid, chk##testid, sizeof(chk##testid)/sizeof(chk##testid[0]), testCounters);
//
// Runs class self test, returns false if fails.
//
bool FreeSpace::RunSelfTest(void)
{
int nTestPassed = 0;
int testCounters[3] = { 0, 0, 0 };
/*
Slice test1[] = {
Slice('f', 0, 10000),
Slice('a', 0, 10000),
Slice('f', 900, 100)
};
RunTest("test1", test1, sizeof(test1)/sizeof(test1[0]));
*/
RUNTEST(test1, Slice('f', 0, 10000), Slice('a', 1000, 1000), Slice('a', 1000, 1000), Slice('f', 1000, 1000));
CHECKTEST(test1, Slice('f', 0, 10000));
RUNTEST(test2, Slice('f', 0, 10000), Slice('a', 1000, 1000), Slice('f', 1000, 2000));
CHECKTEST(test2, Slice('f', 0, 10000));
RUNTEST(test3, Slice('f', 0, 10000), Slice('a', 1000, 1000), Slice('a', 1000, 100), Slice('f', 1000, 500));
CHECKTEST(test3, Slice('f', 0, 1500), Slice('a', 1500, 500), Slice('f', 2000, 8000));
RUNTEST(test4, Slice('f', 0, 10000), Slice('a', 1000, 1000), Slice('a', 500, 500));
CHECKTEST(test4, Slice('f', 0, 500),Slice('a', 500, 1500),Slice('f', 2000, 8000));
RUNTEST(test5, Slice('f', 0, 10000), Slice('a', 1000, 1000), Slice('a', 500, 100));
CHECKTEST(test5, Slice('f', 0, 500),Slice('a', 500, 100),Slice('f', 600, 400),Slice('a', 1000, 1000),Slice('f', 2000, 8000));
RUNTEST(test6, Slice('f', 0, 10000), Slice('a', 1000, 1000), Slice('a', 500, 1500));
CHECKTEST(test6, Slice('f', 0, 500),Slice('a', 500, 1500),Slice('f', 2000, 8000));
RUNTEST(test7, Slice('f', 0, 10000), Slice('a', 1000, 2000), Slice('f', 500, 1000));
CHECKTEST(test7, Slice('f', 0, 1500),Slice('a', 1500, 1500),Slice('f', 3000, 7000));
RUNTEST(test8, Slice('f', 0, 10000), Slice('a', 1000, 2000), Slice('a', 500, 1000));
CHECKTEST(test8, Slice('f', 0, 500),Slice('a', 500, 2500),Slice('f', 3000, 7000));
RUNTEST(test9, Slice('f', 0, 10000), Slice('a', 1000, 2000), Slice('a', 500, 4000));
CHECKTEST(test9, Slice('f', 0, 500),Slice('a', 500, 4000),Slice('f', 4500, 5500));
RUNTEST(test10, Slice('f', 0, 10000), Slice('a', 1000, 2000), Slice('f', 500, 4000));
CHECKTEST(test10, Slice('f', 0, 10000));
RUNTEST(test11, Slice('f', 0, 10000), Slice('f', 1000, 1000));
CHECKTEST(test11, Slice('f', 0, 10000));
RUNTEST(test12, Slice('f', 0, 10000), Slice('f', 9000, 1000));
CHECKTEST(test12, Slice('f', 0, 10000));
RUNTEST(test13, Slice('f', 1000, 1000), Slice('f', 500, 500));
CHECKTEST(test13, Slice('f', 500, 1500));
RUNTEST(test14, Slice('f', 1000, 1000), Slice('a', 500, 500));
CHECKTEST(test14, Slice('a', 500, 500),Slice('f', 1000, 1000));
RUNTEST(test15, Slice('f', 1000, 1000), Slice('f', 100, 100));
CHECKTEST(test15, Slice('f', 100, 100),Slice('f', 1000, 1000));
RUNTEST(test16, Slice('f', 1000, 1000), Slice('a', 100, 100));
CHECKTEST(test16, Slice('a', 100, 100),Slice('f', 1000, 1000));
if(bDoDebug)
{
if(testCounters[1] == 0)
printf("\n Success: All %d tests passed\n\n", testCounters[0]);
else
printf("\n %d test(s) passed, %d test(s) FAILED\n\n", testCounters[0], testCounters[1]);
}
return testCounters[1] == 0;
} //RunSelfTest
Этот класс, однако, имеет зависимость от MFC, он может быть отрезан при необходимости. (Например, заменить CStringA с станд :: строка.
Этот класс будет, скорее всего, имеет самое низкое потребление памяти, так как он работает с диапазонами индекса.
Что наиболее вероятно, отсутствует здесь отображение индекса к реальному объекту (или типа в моем случае) - но эта функция может быть легко сделано для петли на срезах как-то вроде этого:..
int indexRemain = index;
FreeSpace& freespace = ...;
for(size_t i = 0; i < freespace.slices.size(); i++)
{
if(freespace.slices[i].size > indexRemain)
return freespace.slices[i].type;
indexRemain -= freespace.slices[i].size;
}
Почему бы не попробовать 'unordered_map' и если производительность приемлема, то используйте это? – NathanOliver
как написано: «Недавно я прочитал, что unorderd_map будет иметь некоторые накладные расходы». – IceFire
'std :: map' или' std :: unordered_map' соответствовал бы счету, но без какого-либо кода и что-то, чтобы сравнить его [возможно, не удалось] (http://stackoverflow.com/q/2196995/1460794), чтобы между ними. – wally