Memory allocation

[avillageofbigheads]

As part of learning to use the Standard Template list, I wrote a simple program.

The idea behind the program is to take 'n' number of words and then arrange them in a order.

Instead of the using the default "Sort" operation. I'm trying to arrange the words in a sequence as the user enters the name.

For example.

If the user specifies he wants to enter 4 names.

He starts with name 1: Hillary

Name 2: Donald

After you enter name 2 . it will show you the sorted list so far. which is

Donald
Hillary


Then the user is prompted for name 3.

Name 3: Pussygrabber

At this time, the list is further sorted and the new list looks like,

Donald
Hillary
Pussygrabber

The user is prompted for name 4:

Name 4: Warcriminal

Now before it starts the sorting operation, it throws up an error

" StandardTemplatelibrary(1550,0x1001243c0) malloc: *** mach_vm_map(size=140734799806464) failed (error code=3)
*** error: can't allocate region
*** set a breakpoint in malloc_error_break to debug
libc++abi.dylib: terminating with uncaught exception of type std::bad_alloc: std::bad_alloc"

Can't figure what I have done wrong in the program. Hoping someone can point out something silly that I must have missed.

#include <iostream>
#include <list>
#include <string>
#include <stdio.h>

using namespace std;

int main(int argc, const char * argv[]) {
   
//    list<int> list_of_ints;
//    list<double> list_of_doubles;
    list<string> list_of_strings;

    int n;
    string s0, s1, s2;
    
    char t1, t2;
    
    cout << "Enter the number of strings you would like to store: " ;
    cin >> n;
    
    list<string>::iterator iter = list_of_strings.begin();
    
    for (int i = 0; i < n; i++) {
      
        cout << "Enter name " << i + 1 << " :" ;
        cin >> s1;
        
        if (i == 0 ) {
            s0 = *iter ;
            list_of_strings.insert(iter, s1);
            iter++;
            }
        else{
            
            *iter += s0;
            t1 = s1[0];
            
            for (int j = 0; j< i; j++) {
                
                s2 = *iter ;
                t2 = s2[0];
                
                if (t1 < t2) {
                    break;
                } else {
                    iter++;
                }
            }
            
            t2 = s2[0];
            if (t1 < t2) {
                list_of_strings.insert(iter, s1);
                
                iter = list_of_strings.begin();
                while (iter != list_of_strings.end()) {
                    cout << *iter << endl;
                    iter++;
                    
                }
                
            } else {
                list_of_strings.push_back(s1);
                
                iter = list_of_strings.begin();
                while (iter != list_of_strings.end()) {
                    cout << *iter << endl;
                    iter++;
                }
            }
        }
    }
    
//    list_of_strings.sort();
    
    return 0;
}

[JLBorges]

#include <iostream>
#include <string>
#include <list>

int main() {

    std::list<std::string> list_of_strings ;

    std::size_t n ;
    std::cout << "Enter the number of strings you would like to store: " ;
    std::cin >> n;

    for( std::size_t i = 0 ; i < n ; ++i ) {

        std::string name ;
        std::cout << "\nenter name " << i+1 << ": " ;
        std::cin >> name ;

        /* auto */ std::list<std::string>::iterator iter = list_of_strings.begin() ;
        // move the iterator to the position in the list where the name should be inserted
        // as it is moved along print the strings being skipped
        while( iter != list_of_strings.end() && *iter < name ) {

                std::cout << *iter << '\n' ;
                ++iter ;
        }

        list_of_strings.insert( iter, name ) ; // insert in the list at that position
        // note: list, so iter which 'points' to the next element is not invalidated by insert

        std::cout << name << '\n' ; // print the name just inserted

        // print the rest of the list
        for( ; iter != list_of_strings.end() ; ++iter ) std::cout << *iter << '\n' ;
    }
}

[Moschops]

If you run your code under a debugger, it will show you that the problem is in line 37, where s0 can hold a garbage value, having been set to garbage on line 31, where iter is beyond the end of the list. You've got a list of size zero, but you're trying to read a value from it, so s0 contains some dangerous garbage value.

[keskiverto]

What you have looks rather complex. I would guess that the position iterator's behaviour is part of your problem. See http://www.cplusplus.com/reference/list/list/insert/

What I would do is first find the correct position and then add to that position:

while ( std::cin >> s1 and i < n ) {
  // find position
  auto pos = std::lower_bound( list_of_strings.begin(), list_of_strings.end(), s1 );
  // add
  if ( list_of_strings.end() == pos ) list_of_strings.push_back( s1 );
  else list_of_strings.insert( pos, s1 );

  ++i;
}

http://www.cplusplus.com/reference/algorithm/lower_bound/

[JLBorges]

Re. the multiple pass through list version: the if-at-end-then-push_back else-insert construct is unnecessary.

list_of_strings.insert( pos, s1 ); is well defined (equivalent to push_back) when pos == list_of_strings.end()

[keskiverto]

My bad, the http://www.cplusplus.com/reference/list/list/insert/ did not state that explicitly, unlike the http://en.cppreference.com/w/cpp/container/list/insert

Edited out.

[avillageofbigheads]

Yes. I realize i have a long way to go. Yes. my program is complex. I guess i'll have to take more time to change the way I think and approach the problem.

But I do appreciate all the help and advice. I see my mistake.

Thank you.