10

My map is defined as such: map<string, LocationStruct> myLocations; where the key is a time string

I am only keeping 40 items in this map, and would like to drop off the last item in the map when i reach 40 items. I know that i can't do myLocations.erase(myLocations.end()), so how do i go about this?

I do intend for the last item in the map to be the oldest, and therefore FIFO. The data will be coming in rather quick (about 20Hz), so i'm hoping that the map can keep up with it. I do need to look up the data based on time, so i really do need it to be the key, but i am open to alternate methods of accomplishing this.

The format of the string is a very verbose "Thursday June 21 18:44:21:281", though i can pare that down to be the seconds since epoch for simplicity. It was my first go at it, and didn't think too much about the format yet.

Improve this question
6
  • Would myLocations.erase(myLocations.rbegin()) not do the job? Commented Jun 21, 2012 at 17:12
  • 2
    It sounds like, instead of a (sorted) map, you'd like some sort of fixed-length queue / priority-queue. Commented Jun 21, 2012 at 17:13
  • 1
    @Rook map<>::erase takes an iterator, and not a reverse_iterator, as its position argument. Commented Jun 21, 2012 at 17:26
  • 1
    You should strive to treat date/times as a number in your program's logic, and only use text format for input/output purposes. Commented Jun 21, 2012 at 18:49
  • 1
    Your date format is quite inconvenient. A time_t type seconds format would be significantly easier to work with. If you must use a string format for whatever reason, use a (relatively) sane and standardised system like ISO 8601, in which temporal and lexicographical sort orders would be the same. Commented Jun 24, 2012 at 9:34

6 Answers 6

Reset to default
19

The most idiomatic way would be:

myLocations.erase( std::prev( myLocations.end() ) );

If you don't ha ve C++11, use the corresponding function from your toolbox.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

That assumes the strings are sorted chonologically rather than lexicographically
@MooingDuck That's what he asked for: how to remove the last element.
The question has been updated to clarify: "I do intend for the last item in the map to be the oldest, and therefore FIFO." "The format of the string is a very verbose 'Thursday June 21 18:44:21:281'... ", given that information, this answer is wrong.
@MooingDuck You seem to be contradicting yourself. If the last item in the map is the oldest, then the above is correct. The format of the string is really irrelevant; it's up to the comparison function of the map to handle it correctly (although since he's worrying about speed, I'd index using a time stamp of some kind, rather than a string).
He was quite clear with regards to the desired sort criterion. And whether he achieves this by overloading < on LocationStruct, by explicitly specializating std::less<LocationStruct>, or by defining a separate ordering function or functional object really doesn't affect the issue.
|
8

Try this, it works:

map<string, LocationStruct>::iterator it = myLocations.end(); it--; myLocations.erase(it);
Improve this answer

1 Comment

unless myLocations has a size of zero, but it is probably an assumption that this is given
5

I assume when you say "erase last element", you mean "erase oldest element".

I wouldn't use a string for times, use a date/time type instead (like unix timestamp). Then they'll be sorted by time, instead of lexicographically, and you can myLocations.erase(myLocations.begin()), since the oldest would always be at the beginning.

Even better, use a boost::circular_buffer<std::pair<timetype, LocationStruct>>, and use std::lower_bound to find elements by time. This will automatically remove the oldest for you, and has the same logorithmic complexity on finding an element by time. It's also faster when adding data. It's pretty much win all around for your situation. If you really want to avoid boost, then a std::deque fits your needs best, and gives great performance, but if you already have a working map, then staying with a std::map is probably best.

Here's how to do the find in a deque:

typedef ???? timetype; typedef std::pair<Timetype, LocationStruct> TimeLocPair typedef std::deque<TimeLocPair> LocationContainer; typedef LocationContainer::const_iterator LocationIterator; bool compareTimeLocPair(const TimeLocPair& lhs, const TimeLocPair& rhs) {return lhs.first < rhs.first;} LocationIterator find(const LocationContainer& cont, timetype time) { TimeLocPair finder(time, LocationStruct()); LocationIterator it = std::lower_bound(cont.begin(), cont.end(), finder, compareTimeLocPair); if (it == cont.end() || it->first != time) return cont.end(); return it; }
Improve this answer

15 Comments

It depends on how the string is being stored for date It had to take care of date if say the time doesnot belong to same day , Which i have mentioned in my answer
@Ritesh: That is what I intended, but as per your confusion, I have clarified the words and provided a sample type.
@Jason, if you can't or don't want to use Boost, a std::deque will work as a substitute for boost::circular_buffer. Just delete elements at the end when the FIFO reaches the maximum size. Also, be aware that boost::circular_buffer is a header-only library and I doubt it will increase the size of your executable that much. Instantiating a boost::circular_buffer template will probably add as much bloat as instantiating a std::deque.
To help you decide, here is the Rationale section of circular_buffer's documentation: boost.org/doc/libs/release/libs/circular_buffer/doc/…
@MooingDuck: I suppose switching to a deque could be considered premature optimization if he already has it almost working with map. But deep inside, it bothers me that a map is used to implement a FIFO data structure instead of a deque. :-)
|
2

Well, a quick check on g++ 4.4 suggests that this works just fine:

myLocations.erase(myLocations.rbegin()->first);

though I must confess I don't know why it doesn't like accepting only the iterator itself.

Improve this answer

12 Comments

That passes the key of the last element, and a key is a valid thing to pass to erase. This is slow though, compared to simply passing an iterator to the last element.
Because rbegin returns a reverse iterator
Yes, I am aware of that. Hence why I actually said "I don't know why it doesn't like accepting only the iterator itself".
There's no overload of erase() that takes reverse_iterator, that's why.
@K-ballo: is there any technical reason why a reverse-iterator is not an appropriate thing to pass to erase, though?
|
0

Since you are Storing the time as key String . The last element (earliest by time in a day considering time from 00:00 to 24:00) will be a lower bound element and hence You can fetch the iterator like this 

 `map<string, LocationStruct>::iterator it;` it=myLocations.lower_bound ('00:00'); myLocations.erase ( it, it+1);

But if it belongs to different dates then you need to even consider the day and manupilate your code accordingly . As you mentioned data is coming quick enough you dont need to take the date into consideration . But The safe way here would be take the entire date in terms of second and remove the lowest one as mentioned above . That would take care even if frequency of new data arriving is pretty slow.

Improve this answer

3 Comments

still doesnt handle 23:59 followed by 00:01
@MooingDuck That is Why i mentioned The safe way here would be take the entire date in terms of second and remove the lowest one as mentioned above
rereading your answer, you are correct, but the sentance before seems to contradict that advice. If you could clarify your wording (and comment so I notice), I'll remove the downvote.
0

map::erase for last element without TS bindings, simply use following:

myLocations.erase ((--myLocations.end()));
Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.