What is more efficient?

Hey guys.

I am writing a rather large program and there is a part that I want to sort 10 entered vales from the keyboard. Would it be more efficient to use bubblesort or the sort() function using a vector / iterator?

I was thinking of somthing like this as I am leaning towards the vector:

Code:

---

std::vector<int> scores( 10, 0 );
 
std::vector<int>::iterator iter;
 
std::cout << "Enter 10 integers: ";
 
// add values to vector elements
for ( int i = 0; i < scores.size(); i++ )
{
  std::cin >> scores[ i ];
}
 
std::cout << "\n\nYou entered:\n\n";
 
for ( iter = scores.begin(); iter != scores.end(); ++iter )
{
  std::cout << *iter << std::endl;
}
 
std::cout << "\n\nSorted into order:\n\n";
 
sort ( scores.begin(), scores.end());
 
for ( iter = scores.begin(); iter != scores.end(); ++iter )
{
  std::cout << *iter << std::endl;
}

---

I am only asking as I am trying to conserve space and I know that a vector is a more robust type of array.

Thanks in advance for any input.

std::sort is better. And you're not limited to using it with a vector. Could be a raw array, too.

Do you want to conserve code-space (compiled), code-space (smaller source) or data-space?

--
Mats

Sorry I wasn't clear about that. Yes I mean code-space. ( compiled )

And thanks CornedBee that is the method I was thinking was better of the two :)

Or do you want to conserve YOUR time by using something which is already present and debugged as opposed to spending time getting your own implementation working.

Quote:

---

Originally Posted by Salem

Or do you want to conserve YOUR time by using something which is already present and debugged as opposed to spending time getting your own implementation working.

---

At least untill you know which chunks of your code are the "big hitters". I'm pretty sure either implementation will be pretty small here, so it may be better to:
1. Find some other piece of code that can be reduced in size.
2. Compile the entire project with Optimize for Size "-Os" [certainly the right switch in gcc, and I seem to remember that MS compilers use the same].

--
Mats

True. I was also thinking of "inlining" the smaller functions too that only do small job. Thing with that is, everywhere I read it says inlining a function is poor practice as it can lead to a lareger program output in size. But then again it's the compiler's choice not mine if it does indeed take any notice of the inline command.

Thanks for all advice so far guys iv taken it all on board.

Agressive use of inlining can lead to increased code-size, yes. Letting the compiler inline when it feels it's right will probably not do this too bad. The -Os switch will only inline a function if the resulting code is smaller than the code with outlined functions - so only real tiny functions.

--
Mats

Exactly. Some functions are smaller than the code needed to call them, especially in object-oriented language. Consider:

Code:

---

class foo
{
  int m_i;
public:
  int get_i() { return i; }
};

---

The body of get_i would look about like this in assembly:

Code:

---

foo@get_i@:
  mov ecx, [esp+4]
  mov eax, [ecx+0] ; offsetof(m_i) = 0
  ret

---

Of these three instructions, two are function overhead. And we haven't even established a proper stack frame. Nor have we (as I think we actually should) preserved ecx.

A call:

Code:

---

int i = foo.get_i();

---

Code:

---

  ; Save registers?
  push &foo
  call foo@get_i@
  mov [esp-4], eax ; Assuming i is at esp-4

---

Inlined, the two together become

Code:

---

  mov ecx, &foo ; Probably already there
  mov eax, [ecx+0] ; Because mem->mem is not supported
  mov [esp-4], eax

---

Three instructions instead of 6, no jump, and better predictability of register use. In fact, if foo's address is already in a register and if i has its own fixed register, the whole thing becomes a single instruction. Depending on the use of i and the aliasing of the foo object, the variable might be elided completely and the access placed there instead.

Do you need the numbers completely sorted, or are you just looking for a certain value like the median value...?

If you don't need the values completely sorted, one of the other STL sort algorithms might be better.

From item 86 of "C++ Coding Standards":

Quote:

---

In general order from cheapest to most expensive, your standard sorting algorithm options are: partition, stable_partition, nth_element, partial_sort (with its variant partial_sort_copy), sort, and stable_sort.

---

Quote:

---

Originally Posted by matsp

Agressive use of inlining can lead to increased code-size, yes. Letting the compiler inline when it feels it's right will probably not do this too bad. The -Os switch will only inline a function if the resulting code is smaller than the code with outlined functions - so only real tiny functions.

---

Or if the function is nonrecursive and only called in one place. This can happen if parts of the code of a large function are moved out into "helper functions" solely to make it easier to understand and maintain.

Quote:

---

Originally Posted by robatino

Or if the function is nonrecursive and only called in one place. This can happen if parts of the code of a large function are moved out into "helper functions" solely to make it easier to understand and maintain.

---

True - and again, the code produced by this is actually smaller than if there was an external function - because parameter passing and call itself has been removed.

--
Mats