0

I'm simulating the optimal page replacement algorithm in C++. A huge number of page requests formatted as (hex, 'w' or 'r') is to be preprocessed to set up a chain of requests for each page at different time steps.

Currently I'm doing:

    ifstream in(argv[1]);
    unordered_map<unsigned int, queue<unsigned int>> distance_map;
    unsigned int addr, distance = 0;
    char mode;
    while(in >> hex >> addr >> mode)
    {
        if(distance_map.find(addr) == distance_map.end())
           distance_map.emplace(addr, queue<unsigned int>());
        distance_map.at(addr).push(distance);
        distance++;
    }

It is now fine with a small input file, but the grader will test my program with "a lot larger" file. Hence, I want to allocate memory in heap. After searching for quite a while, I found even more questions:

  1. C++ programmers suggest that do not use a pointer to an object. That is do not use unordered_map<K, T> *map_ptr. But I don't understand why this is a generally bad thing. What's the difference between map.insert(...) and map_ptr->insert(...)?

  2. Can I use unique_ptr for every queue<unsigned int> instance that will be held? The queue is dynamically growing, so do the unsigned ints queue contains still reside in stack?

I hope some experienced C++ programmer can tell me what to do in this scenario and answer my above two questions.

MFSO1991
  • 79
  • 5
  • 4
    Where do you think `unordered_map` and `queue` are getting the memory they require if not by dynamically allocating it? Your code will handle big files as written, please don't go about dynamically allocating containers. – Praetorian Jul 11 '15 at 20:46
  • @Praetorian I thought everything not allocated by new keyword is on stack. Am I wrong about that? – MFSO1991 Jul 11 '15 at 20:53
  • @user1433675 Somewhat, but the standard containers already do the right thing internally anyways. Don't worry too much about their guts, they are ugly anyways, but usually work pretty well. Fun fact: You can even cheaply return them by value since 2011. They are that smart. – Baum mit Augen Jul 11 '15 at 20:56
  • @user1433675 Yes, that is correct (to be pedantic, you should be talking about [automatic and dynamic storage](https://stackoverflow.com/q/9181782/241631) instead of stack and heap), but internally the standard library containers will dynamically allocate memory as needed. Also, raw pointers themselves are not frowned upon, it's having raw pointers that own resources (meaning you need to `delete` or do something else to free that resource) that is a code smell because it's easy to then leak those resources. – Praetorian Jul 11 '15 at 21:00
  • @BaummitAugen Do you know where I can learn this lower level details? Any book or online notes? I read the C++ Primer, but I don't believe I saw any detail about the smartness of std containers. – MFSO1991 Jul 11 '15 at 21:01
  • @Praetorian Well almost I guess. Stuff with static storage goes in the data section, doesn't it? – Baum mit Augen Jul 11 '15 at 21:01
  • @user1433675 There is not much to gain from looking at how the containers work internally. Tons of ugly stuff needed to make some standard pedants happy. What matters is what they do, and this can be found in the [documentation](http://en.cppreference.com/w/). And with the exception of `std::array`, they all do their own memory management thing. Don't worry about it, it will work. – Baum mit Augen Jul 11 '15 at 21:02
  • @Praetorian Thanks a lot. To be honest, I haven't heard of automatic and dynamic storage before. – MFSO1991 Jul 11 '15 at 21:06
  • @BaummitAugen All that's guaranteed about objects with static storage duration is that they'll persist for the lifetime of the program, everything else is an implementation detail. – Praetorian Jul 11 '15 at 21:07
  • @Praetorian But that is exactly what we are talking about, right? The standard certainly allows many GB of stack space, and if we had this, we would not have this discussion. – Baum mit Augen Jul 11 '15 at 21:11

1 Answers1

2

All STL containers using an allocator (that are all except std::array and its derivates) store their items in dynamically allocated memory (usually implemented as heap).

Raw pointers are generally bad in C++ because they break RAII idiom and therefore are susceptible to memory leaks.

You can use unique_ptr inside containers, just be careful that the default constructor sets them to null. Generally, they are useful only for polymorphism.

StenSoft
  • 9,369
  • 25
  • 30