Linear regulators like the 7805 are inefficient, and more so when the input voltage is higher. It works as a variable resistor, which varies its value to keep the output voltage constant, here 5V. That means that the current consumed by your 5V circuit also flows through this variable resistor. If your circuit dissipates 1A then the power dissipation in the 7805 will be
\$ P = \Delta V \cdot I = (9V - 5V) \cdot 1A = 4W \$
4W in a single component is rather much, the 5W in your circuit will probably be distributed over several components. It means that the 7805 will need a heatsink, and that's most often a bad sign: too much power dissipation. This will be worse with higher input voltages, and the efficiency of the regulation can be calculated as
\$ \eta = \dfrac{P_{OUT}}{P_{IN}} = \dfrac{V_{OUT} \cdot I_{OUT}}{V_{IN} \cdot I_{IN}} = \dfrac{V_{OUT}}{V_{IN}}\$
since \$I_{OUT} = I_{IN}\$.
So in this case \$\eta = \dfrac{5V}{9V} = 0.56 \$ or 56%. With higher input voltages this efficiency will even get worse.
The solution is a switching regulator, or switcher for short. There are different types of switcher depending on the \$V_{IN}/V_{OUT}\$ ratio. If \$V_{OUT}\$ is less than \$V_{IN}\$ you use a buck converter.
While even an ideal linear regulator has a low efficiency, an ideal switcher has a 100% efficiency, and actual efficiency can be predicted by the properties of used components. For instance there's a voltage drop over the diode, and resistance of the coil. A well designed switcher may have an efficiency as high as 95%, like for the given 5V/9V ratio. Different voltage ratios may result in somewhat lower efficiencies. Anyway, 95% efficient means that the power dissipated in the regulator is
\$ P_{SWITCHER} = \left(\dfrac{1}{\eta} - 1\right) \cdot P_{OUT} = \left(\dfrac{1}{0.95} - 1\right) \cdot 5W = 0.26W \$
which is low enough not to need a heatsink. As a matter of fact the switching regulator itself may be in a SOT23 package, with the other components, like coil and diode SMDs as well.
Best Answer
There are a number of boost regulators on the market designed to allow circuit operation from a single ~1.5V battery cell. This is one example.