[C++] Paired array and map: removing elements

[erotavlas]

Hi,

I have a problem with array and map. Suppose I have an array of int of fixed size. Each new element is added to array after the last filled element. While if I remove an element from a given position of the array, then I will move all the following elements one position back. As example: an array of M elements filled up to N element and with M-N empty elements.
array a1|a2 ... aN|0|0
add aN+1 -> a1|a2 ... aN|aN+1|0
remove aj -> a1|a2|...aj-1|aj+1..aN|0|0|0
I have also a map in which the key is the address of each element in the array. Now suppose that I want to remove an element from the array, then I have to update the map. I cannot simply erase the element of the map since that after erasing an element from the array also the address need to be changed.
My idea is to remove all the elements in the map that are successive w.r.t. the removed element and then to add again the elements with the correct key i.e. address. This is not efficient.
Do you have a clever idea?
Thank you

[tath]

Do you have a clever idea?

Yeah - use a list, either your own implementation or existing one http://www.cplusplus.com/reference/list/list/?kw=list.

What is this map for?

address of each element in the array

why would you need that for?

PS. you are very bad in describing your problem. Instead of wall of text use pseudo code.

[andywestken]

Why do you need an array and a map?

Assuming you do need both, why do you key the map by the element address rather than its value?

Given you implementations, your solution is the one required (as all the addresses will change). But it does sound rather clumsy!?

Andy

[Rechard3]

i think a structure that uses normal arrays will always be inefficient in this domain.
maybe a better approach is to use a structure that is:

- each structure instance is only one element long.
- each structure instance contains a pointer to another instance (which will be the next ring in the chain).
- each instance can contain a pointer to the previous instance in the chain.

i'm not really good with data structures, but i think a doubly-linked-list satisfies these conditions.
this structure allows you to chain multiple instances together with bi-directional iterators.
when you want to delete an instance from the middle of the chain, you can just manipulate pointers on both sides of the instance, EXCLUDING it from the chain, then you can delete it safely.

this approach denies random access on the chain, you are restricted to sequential access, but you can have bi-directional iterators.

i hope to see an even better idea.