The internals of std::vector are (more or less, it can differ from compiler to compiler, but are all approximately equivalent): 

    T *data;   // the malloced data
    size_t capacity;  // how much we malloced
    size_t allocated;  // how much is constructed (what's returned by this->size())

The clear() operation is

    for (size_t i = 0; i < allocated; ++i)
       data[i].~destructor();
    allocated = 0;

which, for a type without a destructor (including unsigned char), will have nothing to call, and is smart enough to eliminate the loop entirely, so the only operation is 'allocated = 0'.  

For something with a nontrivial destructor, though, you are correct that clear() is O(n), but for a POD type it is effectively O(1) since all it does is a single assignment.