std::map to std::list leads to SIGSEGV

Question

I want to save RAM while converting a std::map to a std::list. Therefore I have to delete every element in between. But I get a SIGSEGV.

template <class U>
auto ConvertFlatSegmentsMapToList(std::map<std::string /* relative_path */, U>& differences_map, std::list<U>& differences_list) -> void {
    for (auto& i:differences_map) {
        differences_list.push_back(i.second);
        // differences_map.erase(i.first);//TODO: SIGSEGV
    }
}

How to do that?

When I clear after the for loop, I don't save RAM. i want wo copy one by one and delete in between to save RAM. — B. A. Sylla, Jun 05 '18 at 11:21
This should help so you can delete while iterating: https://stackoverflow.com/a/8234813/1142788 — yussuf, Jun 05 '18 at 11:24

einpoklum · Answer 1 · 2018-06-05T13:39:33.193

3

If you want to save memory, don't use std::map, nor std::list - use std::vector; or better yet - don't use separate strings, apply de-duplication etc.

Having said that, and to answer your question: Deleting an element from a map invalidates iterators into the map - and the ranged-for loop is actually based on iterators. So - you can't delete during your loop. Use differences_map.clear() after the loop. You should also note that individual element deletions are much more expensive time-wise than clearing the entire map.

If your memory is so constrained that you can't take having both the full map and the full list at the same time, then you are simply using the wrong data structures - since, like I said, both of these are quite wasteful. Still, if you insist, you could repeatedly insert *differences_map.begin() into the list, then delete it from the map (and every time obtain .begin() again, after iterator invalidation).

edited Jun 05 '18 at 13:39

answered Jun 05 '18 at 11:21

einpoklum

118,144
57
340
684

That is no answer to my question. You cann't use a vector in any case. I use a map becuse I need a map. But after that I need something that is smaller and is sortable. If I have a map witch 100 MB and create a list with 100 MB, than this is waste of RAM if I don't need the map any more. – B. A. Sylla Jun 05 '18 at 11:27
@B.A.Sylla: A vector is quite sortable, I'm not sure what you mean. Plus, there's more than one way to implement a map; and if your map values are small, the overheads of `std::map` are quite significant. Anyway, when you `clear()` the map it stops using all of its memory. – einpoklum Jun 05 '18 at 11:32
@einpoklum Too late! You already made a second copy of it all. – Paul Sanders Jun 05 '18 at 12:16
@PaulSanders: So? OP didn't say there's not enough memory for that. – einpoklum Jun 05 '18 at 12:19
@einpoklum See OP's first comment to his own question. Could've been worded more clearly, but that was my reading of it. – Paul Sanders Jun 05 '18 at 12:32
1

@PaulSanders: See my edit. Actually, in hind sight, this whole thing is an XY problem and we should have just coaxed OP to say what he really wants to do. – einpoklum Jun 05 '18 at 15:32
Yes, could be . – Paul Sanders Jun 05 '18 at 16:39

B. A. Sylla · Accepted Answer · 2018-06-05T11:48:47.167

As yussuf commented, you can find the solution at https://stackoverflow.com/a/8234813/1142788. I have adapted this to my example. (needs c++11 support)

template <class U>
auto ConvertFlatSegmentsMapToList(std::map<std::string /* relative_path */, U>& differences_map, std::list<U>& differences_list) -> void {
    std::clog << "differences_map: " << differences_map.size() << std::endl;    // e.g. 6
    std::clog << "differences_list: " << differences_list.size() << std::endl;  // e.g. 0

    for (auto i = differences_map.cbegin(); i != differences_map.cend(); i = differences_map.erase(i)) {
        differences_list.push_back(i->second);
    }

    std::clog << "differences_map: " << differences_map.size() << std::endl;    // e.g. 0
    std::clog << "differences_list: " << differences_list.size() << std::endl;  // e.g. 6
}

Because `std::map::erase()` returns a (valid) iterator? Neat. — Paul Sanders, Jun 05 '18 at 12:15

Paul Sanders · Answer 3 · 2018-06-25T13:05:13.367

0

You could consider storing std::shared_ptrs in your map, list or whatever. Then you can copy them around cheaply and easily without the need to copy the underlying data. You still get (more-or-less) value semantics, and should not need to manage object lifetimes manually.

edited Jun 25 '18 at 13:05

answered Jun 05 '18 at 12:34

Paul Sanders

24,133
4
26
48

This is true when speed is more important than memory. Pointers need memory. – B. A. Sylla Jun 22 '18 at 14:28
@B.A.Sylla Not enough to matter, see [live demo here](https://wandbox.org/permlink/RltdBHZCR8kXU6R7). – Paul Sanders Jun 22 '18 at 14:37

std::map to std::list leads to SIGSEGV

3 Answers3