What can be a faster method to insert or delete information into a map?
I have a map in which I store int,string.
I use it to store changes linked to a simple rows-data.
If I change line 3 I store the change for line 3
If I have an insert operation on line 3, I have to do an inverse loop into the map from the last item to item 3,giving to map.first = map.first+1. (So, the change for line 3 is now the change for line 4)
If I erase the line 3, I have to erase the map item 3, and as in the last case, to do a loop from 3 to the map.end , giving values map.first =map.first -1; (So, the change for line 4 is now the change for line 3)
I use the correct iterator position with lowerbound to locate the initial point.
Somebody can tell me a better way to do this?
I use it to store changes linked to a simple rows-data.
If I change line 3 I store the change for line 3
If I have an insert operation on line 3, I have to do an inverse loop into the map from the last item to item 3,giving to map.first = map.first+1. (So, the change for line 3 is now the change for line 4)
If I erase the line 3, I have to erase the map item 3, and as in the last case, to do a loop from 3 to the map.end , giving values map.first =map.first -1; (So, the change for line 4 is now the change for line 3)
I use the correct iterator position with lowerbound to locate the initial point.
Somebody can tell me a better way to do this?
Last edited on
That's pretty much the problem with maps (and vectors and arrays). They allow random access (i.e. jump to index i in constant time), but any deletion/addition requires "n-i" copies.
You could solve this by making a linked list: each 'datapoint' is a Node object in itself, with as members the string, the int and a pointer to the next Node object in line. Deletion can be done in instant time (set Node->next to Node->next->next), same for Addition (Set newNode->next to Node->next and Node->next to New). The downside is that simple accessing can no longer be done in constant time (i.e. no random access -> must cycle through the ->next pointers until you find the Node you needed).
So, the trade off is based on how often you access (and update a single version) and how often you delete/add data.
You could solve this by making a linked list: each 'datapoint' is a Node object in itself, with as members the string, the int and a pointer to the next Node object in line. Deletion can be done in instant time (set Node->next to Node->next->next), same for Addition (Set newNode->next to Node->next and Node->next to New). The downside is that simple accessing can no longer be done in constant time (i.e. no random access -> must cycle through the ->next pointers until you find the Node you needed).
So, the trade off is based on how often you access (and update a single version) and how often you delete/add data.
True, but I thought he'd benefit from some first-hand experience with data structures. I started using the STL containers without properly knowing how they work and it was messy.
Plus, considering the 50 topics on Linked Lists this week alone, it shouldn't be too difficult for him!
Plus, considering the 50 topics on Linked Lists this week alone, it shouldn't be too difficult for him!
Yeah you have a point I think everyone should make a linked list at some point when they're starting out, it tests whether they really understand pointers or not.
Topic archived. No new replies allowed.