It sound as premature optimization. Dereference a pointer is ridiculously cheap.
The obvious solution is to use pointers of course. Foo may hold a std::vector which each element points to underlying data of original order (O).
Here a solution, deducting what you need, not using pointers, using std::reference_wrapper and std::ref:
struct Foo
{
Foo(std::vector<int>& _data) : dataFull(_data)
{ ; }
void add(int index)
{
assert(index < dataFull.size());
if(index < references.size())
{
// replace
references[index] = std::ref(dataFull[index]);
}
else
{
// add n times, need sync with index
while(index >= references.size())
{
references.push_back(std::ref(dataFull[index]));
}
}
// mark as valid index
indexes.push_back(index);
// sort for can find with binary_search
std::sort(indexes.begin(), indexes.end());
}
int* get(int index)
{
if(std::binary_search(indexes.begin(), indexes.end(), index))
{
return &references[index].get();
}
else
{
return NULL;
}
}
protected:
std::vector<int>& dataFull;
std::vector<std::reference_wrapper<int> > references;
std::vector<int> indexes;
};
int main()
{
const int size = 1000000;
std::vector<int> O;
O.resize(1000000, 0);
Foo f_1(O);
f_1.add(1);
f_1.add(2);
f_1.add(3);
Foo f_2(O);
f_2.add(1);
f_2.add(4);
f_2.add(16);
Foo f_3(O);
f_3.add(100);
f_3.add(101);
f_3.add(102);
// index 1 is changed, it must affect to all "Foo" that use this index (f_1 and f_2)
O[1] = 666;
// checking if it changed
assert( *f_1.get(1) == 666 );
assert( *f_2.get(1) == 666 );
assert( f_3.get(1) == NULL );
return 0;
}
EDIT:
Performance is same that if you use pointer, but std::reference_wrapper can be integrated best in templated code because you have T& and don't need have code for T* and T&.
Have indexes in other vector, only is useful if your struct is ordered by multiple criteria.
I show a example with a vector, where T is a struct complex with two fields. I can reorder this vector with 2 criterias, without touch the original.
template <typename T>
struct Index
{
typedef typename bool(*Comparator)(const T&, const T&);
Index(std::vector<T>& _data, Comparator _comp)
: dataFull(_data)
, comp(_comp)
{
for(unsigned int i = 0; i < dataFull.size(); ++i)
{
add(i);
}
commit();
}
void commit()
{
std::sort(references.begin(), references.end(), comp);
}
std::vector<std::reference_wrapper<T> >& getReference() {return references;}
protected:
void add(int index)
{
assert(index < dataFull.size());
references.push_back(std::ref(dataFull[index]));
}
protected:
std::vector<T>& dataFull;
std::vector<std::reference_wrapper<T> > references;
Comparator comp;
};
int main()
{
struct ComplexData
{
int field1;
int field2;
};
// Generate vector
const int size = 10;
std::vector<ComplexData> data;
data.resize(size);
for(unsigned int i = 0; i < size; ++i)
{
ComplexData& c = data[i];
c.field1 = i;
c.field2 = size - i;
}
// Vector reordered without touch original
std::cout << "Vector data, ordered by field1" << std::endl;
{
Index<ComplexData> f_1(data,
[](const ComplexData& a, const ComplexData& b){return a.field1 < b.field1;});
auto it = f_1.getReference().begin();
auto ite = f_1.getReference().end();
for(; it != ite; ++it)
{
std::cout << "-> " << it->get().field1 << " - " << it->get().field2 << std::endl;
}
}
// Vector reordered without touch original
std::cout << "Vector data, ordered by field2" << std::endl;
{
Index<ComplexData> f_2(data,
[](const ComplexData& a, const ComplexData& b){return a.field2 < b.field2;});
auto it = f_2.getReference().begin();
auto ite = f_2.getReference().end();
for(; it != ite; ++it)
{
std::cout << "-> " << it->get().field1 << " - " << it->get().field2 << std::endl;
}
}
return 0;
}