I assume that there must be some amount of code that doesn't modify the object in common. You might be able to extract that into a constant method and reuse that to implement both the private and public function.
E.g (the helper function goes through size_t to avoid problems with constness if an iterator is to be returned directly):
Code:
class X
{
std::vector<int> v;
public:
typedef std::vector<int>::iterator iterator;
typedef std::vector<int>::const_iterator const_iterator;
X() { std::generate_n(std::back_inserter(v), 10, rand); }
const_iterator special() const { return v.begin() + do_special(); }
private:
iterator special_() { return v.begin() + do_special(); }
std::size_t do_special() const {
return std::max_element(v.begin(), v.end()) - v.begin();
}
};