matching / correspondence

[Aleks Dubinskiy]

Hi, I have the following programming dilemma:

I need a find a good way to represent matches between contents of
containers.

For example, I have 2 or more an STL deque of feature points.

deque<FeaturePoint> cont1, cont2.

some elements of cont1 map to some elements of cont2 (one-to-one), and the
sizes of the containers are not necessarily the same.
Also we can assume that the containers in question are random access (like
std::deque or std::vector)

I can think of two ways of representing matching:
1) matching addresses / pointers / iterators
This approach is convenient because the matching structure has direct
access to the containers' contents.
But unfortunately, in this scheme it is difficult to serialize / save
the matching to a file, because the addresses are volatile.
2) matching the indices
This approach makes it easy to save matches to a file, but we have to
keep track of the meaning of these indices elsewhere.
Moreover, when the containers are updated, the indices need to be kept
track of as well.

I have encountered this problem several times, and would like a nice generic
solution, which is:
a) Does not depend on the type of the container or data in it
b) Is suitable for serialization
c) Handles changes of elements within the containers gracefully

Has anyone encountered this before? Is there a cookbook solution for this
kind of problem (such as a Design Pattern)? My Gamma et. al. book is not
helping in this case

Cheers,
Aleks

 

[Denis Remezov]

Hi, I have the following programming dilemma:

I need a find a good way to represent matches between contents of
containers.

For example, I have 2 or more an STL deque of feature points.

deque<FeaturePoint> cont1, cont2.

some elements of cont1 map to some elements of cont2 (one-to-one), and the
sizes of the containers are not necessarily the same.
Also we can assume that the containers in question are random access (like
std::deque or std::vector)

I can think of two ways of representing matching:
1) matching addresses / pointers / iterators
This approach is convenient because the matching structure has direct
access to the containers' contents.
But unfortunately, in this scheme it is difficult to serialize / save
the matching to a file, because the addresses are volatile.
2) matching the indices
This approach makes it easy to save matches to a file, but we have to
keep track of the meaning of these indices elsewhere.
Moreover, when the containers are updated, the indices need to be kept
track of as well.

I have encountered this problem several times, and would like a nice generic
solution, which is:
a) Does not depend on the type of the container or data in it
b) Is suitable for serialization
c) Handles changes of elements within the containers gracefully

Has anyone encountered this before? Is there a cookbook solution for this
kind of problem (such as a Design Pattern)? My Gamma et. al. book is not
helping in this case

I have stumbled on similar problems scores of times, never finding a
particularly appealing generic solution.

Could you possibly abstract from the problem of matching the contents
of different containers and think in terms of a system of element
identifiers (ids) (in lieu of indicies) for one container? If you use
the same system for another container, then matching becomes automatic.

Now, of course, you need to bind the id system to every container type
that you are using. It comes for free for the associative containers.
For the sequence containers, generally, some form of id mapping is
required.

When I came across this last, I simply decided to write a specialised
container instead of using the std::vector and worrying about converting
ids to indicies.
Perhaps I digress, but FWIW, it looked something like this (the point
is, I'd only use a container that fit the purpose):

template <typename T>
class index_map {
public:
//...

iterator begin();
iterator end();

//return a valid iterator if element id exists, end() otherwise
iterator get(id_type id);

//replace if element id exists, otherwise create a new one with
//a given id
void set(id_type id, const value_type& v);

//generate a new id, create a new element id, return id
id_type insert(const value_type& v);

void erase(iterator it);

//... etc. etc.
};

Internally, it used a vector (could be a dynamic array) for storage.
In addition, it had a dynamic bitset to indicate which elements
of the internal array are valid elements of the index_map. erase()
clears the "use" bit - it doesn't touch the storage. Unused storage
is reused by insert (there is a linked-list of unused elements).
All operations are constant (or amortised-constant) time. To me,
the only problematic thing was the compactness of ids. The storage
is only as compact as the maximum number of elements that have
existed at any particular time.

Denis