You are here:

C++/Doubt regarding Vectors in C++

Advertisement


Question
QUESTION: Hi,

Am writing code for creating a non binary tree and I have used vectors for representing children. But am getting a run time exception as "vector subscript out of range" at "push_back()" statement. I haven't accessed any element from the vector in my code. I just pushed the elements on to the vector. The code is perfectly working when I give 20-30 instances of input,when I increase my number then this exception is coming. I have tried a lot for online help, and not able to find an exact solution and reason for this behavior. Kindly help me.

        Thank you.

Regards,
Vasavi

ANSWER: Your question provides little specific detail so I shall state my assumptions:

1/ You are using a compiler with a good quality C++ standard library.
2/ By "vectors" you mean specialisations of the C++ standard library std::vector class template.
3/ By 'run time exception as "vector subscript out of range"' you mean a std::out_of_range exception was thrown.
4/ I am assuming you have not provided your vector element type(s) with support for move operations and so will not confuse things with talk of move operations added by C++11 and later.

So, do you think that it is more probable that a quality, tested and well used implementation of some code such as a C++ standard library's std::vector implementation would have such an obvious problem (failing like this in push_back is _not_ an obscure corner case) or that some new, still in development, quite possibly not that well tested or widely used code such as your non binary tree code would contain bugs?

Remember to ask this to yourself when such situations crop up - it is all too easy to assume the code we wrote is perfect (doh!) and that it is some problem with the tools or libraries etc. we are using. That is not to say such tools, libraries etc. are perfect - just that you should not suspect them straight away! And if, after further analysis and testing,  you really suspect it is a problem with a tool or third party code then check to see if there is firstly an accessible set of bug reports for the product and if so then search to see if your problem is one that is known about and logged. If not consider submitting a bug report.

If you wish to see if your C++ standard library implementation of std::vector does have a problem with push_back then try a simple test, maybe something like so:

       #include <vector>
       #include <cassert>

       int main()
       {
         const int NumberOfElements(10000);
         std::vector<int> vi;
         for (int i=0; i!=NumberOfElements; ++i)
         {
         vi.push_back(i);
         }
         assert(vi.size()==unsigned(NumberOfElements));
       }

If the above program when built and run produces no errors, in fact no output at all, then it worked and a std::vector<int> can cope with having 10000 (or whatever you set NumberOfElements to) elements pushed back to it.

So if it is not std::vector<T>::push_back - where T is the type of elements in your vector(s) then it must be a problem in your code.

So how could this be?
The first thing to do is look for places in your code you are accessing your vectors by an index - probably using the vector's at operation as it is defined to be range checked and throws a std::out_of_range exception for bad index values, or where you have added explicit range checks in your code.

Next is to understand where any such calls might be accessed by push_back. For this we need to examine how std::vector and the push_back operation work. std::vector specialisation instances store their elements in contiguous memory - i.e. as an array. They also grow dynamically as more elements are added. They also have to perform push_back operations in effectively constant time (the C++11 standard says that element insertion operations' complexity are linear in number of elements added and distance to end of the vector - which are fixed values of 1 and 0 respectively for push_back). In fact this has to be "amortized constant" time because of what happens if there is no more capacity to store more elements.

So first off, if there is capacity for the new element a copy of the object passed to push_back is constructed in the unused raw memory end of the vector - use of the element type's copy constructor #1.

If there is no capacity available then a larger block of memory is allocated - typically 1.5x or 2x the current block's size, all the existing elements are copied - one at a time - from the old memory block to the new - use of the element's type copy constructor #2, then the new element is copy-constructed at the free raw memory at the end of elements in the new block, and the old block deleted.

So, without having seen your code at all, and with no further details, I would initially suspect your copy constructor - or operations is relies on - has a bug.

Hope this helps.


---------- FOLLOW-UP ----------

QUESTION: Hi,

Thanks for your reply. I am guessing there is some bug in my code which am not able to find out. I am posting a part my code where am getting the exception. Can you please look at the code.

void insert_tree(vector<pair<int,int>> input,node &par)
{
  int data;
  
  if(input.size()>=1)
     data = input[0].first;
  
  int flag=-1;
  node n;
  
  int size = par.children.size();
  
  for(int i=0;i<par.children.size();i++)
  {
     if(par.children[i].data == data)
     {
        par.children[i].freq++;
        flag = i;
        break;
     }
  }


  if(flag == -1)
  {
     n.data = data;
     n.level = par.level +1;
     n.freq = 1;
     n.link = 0;
     
     n.parent.reserve(3);
     par.children.reserve(30);
     
     n.parent.push_back(par);
     par.children.push_back(n);  //Am getting an error at this point after calling insert_tree for 15 times. Working good before that
        
  }
  
  if(input.size()>1)
  {
     
     input.erase(input.begin()+0);
     
     if(flag != -1)
     {
        insert_tree(input,par.children[flag]);
     }
     else
     {
        insert_tree(input,par.children.back());
     }

  }
}

Structure of node is :

struct node
{
  int data;
  int freq;
  vector<node> parent;
  vector<node> children;
  int link;
};


         Thank you so much.

Regards,
Vasavi.

Answer
Did you read my instructions to questioners?

If so did you see the part about posting code in questions:

   "5/ POSTING CODE IN QUESTIONS:
    I will reject questions requiring me to wade through quantities of code to answer your question.
    Instead please provide  short, self contained, correct (compilable), example code showing the
    problem. Note the guidelines at http://www.parashift.com/c++-faq-lite/posting-code.html, and
    http://sscce.org/ - although 20Kb examples may be a bit large for AllExperts questions in most cases."

Thanks for the shortness of code posted but it is not self contained!
In this case creating a simple section of code which includes a main that I can copy and paste into an editor, save, build and execute - and MAKE SURE YOU BUILD AND RUN THE POSTED CODE BEFORE POSTING IT TO ME AND IT PERFORMS AS EXPECTED. Preferably with a simplified version of insert_tree that is the simplest you can get it to demonstrate the problem.

Also some hints as to what you used to build and run your code might help a little - for example are you using an old compiler and C++ library such as MSVC 6 - circa 1998 or a modern variant using C++11 or C++14 features.

However, even with only taking a fairly quick look at your code I noticed a few things.

Firstly - do you understand what a tree data structure is?
See http://en.wikipedia.org/wiki/Tree_(data_structure) for example. Notice the second to last paragraph under the section "Recursive":

   "This data structure defines a directed graph,[b] and for it to be a tree one must add a
    condition on its global structure (its topology), namely that at most one reference
    can point to any given node (a node has at most a single parent), and no node in the
    tree point to the root. In fact, every node (other than the root) must have exactly one
    parent, and the root must have no parents."

Does your 'tree' fulfil this requirement? Note: your node structure contains a collection of (supposedly - see below) back references to 'parents' - plural. I assume the intent is to have 'trees' with nodes having 0,1, or more parents. That is it is not a tree data structure.

Second, do you understand what the ramification of this type is:

   vector<node>

?

What type of objects are stored in such a vector instance?

 a) References (or pointers) to nodes
 b) (Copies of) whole node objects.

If you are used to languages like Java or C# then perhaps you would think a). However the STL containers in C++ are VALUE BASED - that is they store whole objects as VALUES and not references to objects. They do this by copying (or moving if possible in C++11 and after) objects, as I mentioned in my previous answer.

Given this information what do you think might be the effect of storing copies of nodes - both child nodes and parent nodes - in the node vectors? Do you think this would be a sane thing to do? Please take time to work through some worked examples - remembering that every time you use push_back a copy of a node is made, and this will cause copies of the vectors of nodes to be made, causing copying of the nodes they contain...

So do you think any child node can refer to its actual (original) parent node(s) or only copies of any such node(s)? And if they are copies what state do you think such copies might have - would they track changes made to the real parent node or are they only snapshots of the state when a copy was made? Perform similar considerations for the children nodes case.

Consider these two lines:

   n.parent.push_back(par);
   par.children.push_back(n);

Does the parent node object pushed back to n end up containing a child node object representing n?
No - a COPY of par is made in the first line - at which point par has no element for this n node added to its children. Then in the second line par has a copy of n added as a child but this child has a copy of par that has no child node representing it. That is:

   par.children.back().parent.back().children does not contain (a copy of) n

Where:
   par.children.back()  should be a copy of n representing the state n was in at the second line, copy_n
   copy_n.parent.back() would be a copy of the copy of par pushed back to n in the first line,
         with no child for n, copy_par
   copy_par.children    are the copied children nodes of the copy of the copy of par at line 1

Assuming for a moment you could fix all these other problems with using copies of nodes rather than references to nodes you might like to consider just how many copies are produced. The following code was built and run on Linux using g++ 4.7.3 with the command line:

   g++ -o main --std=c++0x -Wall --pedantic main.cpp

from a file called main.cpp (used for scratch code like this) producing an executable called main:

#include <vector>
#include <cassert>
#include <iostream>

namespace
{
 unsigned long long node_count{0ULL};
 struct node
 {
     std::vector<node> parent;
     std::vector<node> children;

   // default construct: rely on member initialisation bump node count up
   node()
   {
       ++node_count;
   }

   // copy construct: copy other's vector members and bump node count up
   node( node const & other )
   : parent(other.parent)
   , children(other.children)
   {
     ++node_count;
   }

   // copy assignment: copy rhs and swap vector members with this
   node & operator=(node rhs)
   {
     parent.swap(rhs.parent);
     children.swap(rhs.children);
     return *this;
   }

   // destroy node: bump node count down.
   ~node()
   {
     --node_count;
   }
 };

}

void print_status(const char * prefix="")
{
 std::cout << prefix << "Node count: "<< node_count << "\n";
}

void print_status(unsigned i, const char * prefix="")
{
 std::cout << prefix <<  " node insert no.: "<< i << ";  ";
 print_status();
}

void create_root_with_n_children_posted_method(unsigned n)
{
   node r;

   for (unsigned i=0; i!=n; ++i)
   {
       print_status(i, "Before");
       node c;
       c.parent.push_back(r);
       r.children.push_back(c);
       print_status(i, " After");
   }
}

void create_root_with_n_children_adjusted_method(unsigned n)
{
   node r;

   for (unsigned i=0; i!=n; ++i)
   {
       print_status(i, "Before");
       r.children.push_back(node());

     // ensure copy of child node has copy of r as parent
       r.children.back().parent.push_back(r);
       print_status(i, " After");
   }
}

int main()
{
   const unsigned NumberOfNodes(20);
   print_status("Before create_root_with_n_children_posted_method: "); // should be 0
   create_root_with_n_children_posted_method(NumberOfNodes);
   print_status(" After create_root_with_n_children_posted_method: "); // should be 0
   print_status("\n Before create_root_with_n_children_adjusted_method: "); // should be 0
   create_root_with_n_children_adjusted_method(NumberOfNodes);
   print_status(" After create_root_with_n_children_adjusted_method: "); // should be 0
}

It uses a simplified version of your node struct - but with explicit default construction, copy construction and assignment (probably not required at the moment) and destructor to track the number of node objects in existence.

I then added two simple functions that create a root node and add a number of children to the root, with the node count displayed before and after each iteration. The first function uses the method from your code shown in the 2 lines I mentioned earlier:

   n.parent.push_back(par);
   par.children.push_back(n);

The second function adjusts this logic to add a default (empty) child node to the root parent then adds a root node copy to the child parent vector directly.

The two functions are called from main and passed the value of the constant NumberOfNodes, currently set to 20, at which point iterations start to get noticeably slow in my Linux VM. You can play with this value to see what effect it has.

The code should be available at:

   http://coliru.stacked-crooked.com/a/bbaf6b7861492fea

which should allow you to compile, link and run it there on the site - click the Edit button at the bottom right, then the Compile, link and run button that should appear. (Hope this works - it is the first time I have tried it!)

Hope these hints set you on the right path.

C++

All Answers


Answers by Expert:


Ask Experts

Volunteer


Ralph McArdell

Expertise

I am a software developer with more than 15 years C++ experience and over 25 years experience developing a wide variety of applications for Windows NT/2000/XP, UNIX, Linux and other platforms. I can help with basic to advanced C++, C (although I do not write just-C much if at all these days so maybe ask in the C section about purely C matters), software development and many platform specific and system development problems.

Experience

My career started in the mid 1980s working as a batch process operator for the now defunct Inner London Education Authority, working on Prime mini computers. I then moved into the role of Programmer / Analyst, also on the Primes, then into technical support and finally into the micro computing section, using a variety of 16 and 8 bit machines. Following the demise of the ILEA I worked for a small company, now gone, called Hodos. I worked on a part task train simulator using C and the Intel DVI (Digital Video Interactive) - the hardware based predecessor to Indeo. Other projects included a CGI based train simulator (different goals to the first), and various other projects in C and Visual Basic (er, version 1 that is). When Hodos went into receivership I went freelance and finally managed to start working in C++. I initially had contracts working on train simulators (surprise) and multimedia - I worked on many of the Dorling Kindersley CD-ROM titles and wrote the screensaver games for the Wallace and Gromit Cracking Animator CD. My more recent contracts have been more traditionally IT based, working predominately in C++ on MS Windows NT, 2000. XP, Linux and UN*X. These projects have had wide ranging additional skill sets including system analysis and design, databases and SQL in various guises, C#, client server and remoting, cross porting applications between platforms and various client development processes. I have an interest in the development of the C++ core language and libraries and try to keep up with at least some of the papers on the ISO C++ Standard Committee site at http://www.open-std.org/jtc1/sc22/wg21/.

Education/Credentials

©2016 About.com. All rights reserved.