What's wrong with STL rotate algorithm?

This is a discussion on What's wrong with STL rotate algorithm? within the C++ Programming forums, part of the General Programming Boards category; Code: #include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int i, m, n; int *d; cin ...

  1. #1
    Registered User
    Join Date
    Apr 2005
    Posts
    77

    What's wrong with STL rotate algorithm?

    Code:
    #include <iostream>
    #include <vector>
    #include <algorithm>
    
    using namespace std;
    
    int main()
    {
    	int i, m, n;
    	int *d;
    	cin >> m;
    	cin >> n;
    	d = new int[m];
    	for (i = 0; i < m; i++)
    		cin >> d[i];
    	
    	vector<int> v(d, d+m);
    	for (vector<int>::size_type i = 0; i < v.size(); i++)
    		cout << v.at(i) << " ";
    	cout << endl;
    	rotate(v.begin(), v.begin()+n, v.end());
    		for (vector<int>::size_type i = 0; i < v.size(); i++)
    		cout << v.at(i) << " ";
    	cout << endl;
    	delete []d;
    }
    The output shows
    Code:
    debian:~# ./10039
    10 12
    4
    5
    7
    1
    2
    4
    2
    3
    9
    7
    4 5 7 1 2 4 2 3 9 7
    7 1 2 4 2 3 9 7 0 135073
    *** glibc detected *** free(): invalid next size (fast): 0x0804c038 ***
    Aborted
    What's matter about the error?

  2. #2
    Registered User
    Join Date
    Apr 2005
    Posts
    77
    if I try to change rotate part to
    Code:
    for (i = 0; i < n; i++)
      rotate(v.begin(), v.begin()+1, v.end());
    It works fine. Can I do this action in 1 line?

  3. #3
    (?<!re)tired Mario F.'s Avatar
    Join Date
    May 2006
    Location
    Portugal
    Posts
    7,412
    The problem derives from the input you are giving to n. Rotate signature is something like this:

    Code:
    std::rotate(iterator begin, iterator middle, iterator end);
    What it does is to grab the element at middle and place it at the begin. Next middle + 1 is placed and being + 1, then next + 2 is placed at begin + 2, etc... All the way untill middle becomes equal to container.end(). At that time it stops.

    Given a container with values 3, 4, 5, 6, 7, if I do rotate(begin(), begin() + 3, end()), the resulting container will become 6, 7, 3, 4, 5

    By passing it a value bigger than the size of the container you are effectively accessing memory you don't own.

    You don't need to change the rotate part, you just need to pay attention to what value you enter for n.
    The programmer’s wife tells him: “Run to the store and pick up a loaf of bread. If they have eggs, get a dozen.”
    The programmer comes home with 12 loaves of bread.


    Originally Posted by brewbuck:
    Reimplementing a large system in another language to get a 25% performance boost is nonsense. It would be cheaper to just get a computer which is 25% faster.

  4. #4
    Yes, my avatar is stolen anonytmouse's Avatar
    Join Date
    Dec 2002
    Posts
    2,544
    I think you can simulate a 'multiple rotate' by using n % m as the middle.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help about STL copy algorithm
    By Antigloss in forum C++ Programming
    Replies: 4
    Last Post: 06-18-2007, 11:06 AM
  2. Array of Vectors amd other STL questions
    By kolistivra in forum C++ Programming
    Replies: 16
    Last Post: 04-12-2007, 09:11 AM
  3. Destructors in STL?
    By sawer in forum C++ Programming
    Replies: 4
    Last Post: 08-09-2006, 09:35 AM
  4. stl containers allocation in heap or stack?
    By sawer in forum C++ Programming
    Replies: 9
    Last Post: 08-06-2006, 03:08 PM
  5. What's wrong with my Stream Cipher Encryption?
    By Davros in forum C++ Programming
    Replies: 3
    Last Post: 04-18-2002, 09:51 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21